Elementary Data Structures

Dynamic sets that can store and retrieve elements. Data structures are techniques for representing finite dynamic sets of elements.

Each element can contain:

a key used to identify the element
satellite data carried around but unused by the data structure
attributes that are manipulated by the data structure, e.g. pointers to other objects

Very often the keys stem from a totally ordered set, e.g. the natural numbers. This allows us to define the minimum, successor, predecessor, and (may not exist) maximum.

Operations on a dynamic set can be categorize into queries and modifications. Typical operations include:

Search(S,k): returns a pointer to element with key (i.e., x.key=k) or NIL.
Insert(S,x): adds element pointed to by to .
Delete(S,x): given a pointer to an element in removes it from .
Minimum(S), Maximum(S): returns a pointer to element resp. with smallest or largest key.
Successor(S,x), Predecessor(S,x): returns a pointer to the next smaller (or larger) than x.key.

The runtime of these operations is often measured using as the number of elements in .

For example, the runtime of these operations on an array (assuming we can have “gaps” between elements):

Search(S,k):
Insert(S,x):
Delete(S,x):
Minimum(S), Maximum(S):
Successor(S,x), Predecessor(S,x):

For example, the runtime of these operations on an sorted array:

Search(S,k): (using binary search)
Insert(S,x):
Delete(S,x):
Minimum(S), Maximum(S):
Successor(S,x), Predecessor(S,x):

Stacks

The stack is a last-in, first-out (LIFO) data structure. We can intuitively understand the stack as a box containing a vertical stack of books. We can only access the top book of the stack. The insertion is usually called push, and deletion is called pop.

Stacks can be implemented as an array with attribute : All stack operations take time .

Stacks Application (1): Bracket Balance Checking

To check whether the brackets are balanced, we can read the expression from left to right, and push each opening bracket and pop for each closing bracket.

If the type of popped bracket always matches, the brackets are balanced, otherwise unbalanced.

Stacks Application (2): Postfix Expression

To evaluate the postfix expression, we read the tokens one at a time:

if it is an operand, we push it on the stack.
if it is a binary operator, we pop twice, apply the operator, and push the result back on the stack.

Queues

The queue is a first-in, first-out (FIFO) data structure. The first element in a queue is accessible. The insertion is called enqueue, and deletion is called dequeue. Queues have a head and a tail.

Elements are added to the tail
Elements are extracted from the head

Queues can be stored in an array “wrapped around”:

Priority Queues

A priority queue is a queue that keeps a order over its elements. For example, we want to schedule jobs on a computer shared among multiple users. A max-priority queue keeps track of the jobs to be performed and their relative priorites. When a job is finished, the scheduler selects the job with highest priority from those pending. And jobs can be added to the scheduler at any time. We may find that a heap fits this job precisely.

The max-priority queue is a data structure for maintaining a set of elements with an associated element called key (the priority).

Insert(S,x,k): insert x with key k into S,
Maximum(S): return the element in with the largest key,
Extract-Max(S): removes and returns element in with the largest key,
Increase-Key(S,x,k): increases the key of to a larger value ,

Min-priority queue based on min-heap also exist, we will use them in graph algorithms, e.g. Djisktra.

Elements in the priority queue correspond to objects. For an operation such as Increase-Key we need a way to map objects to and from their position in the heap (and update it as it moves in the heap).

One way is to use handles: extra information stored in the object that allows to do the mapping. And the heap needs to contain for each element a pointer to the object.

Linked Lists

The array has many disadvantages:

We need to specify an initial size
Changing the size of an array is troublesome
Inserting and deleting elements in specific positions is difficult

So we introduce the linked list to solve these issues. In a linked list, objects are linked using pointers to the next element. Linked lists can be singly linked or doubly linked, depending whether the objects contain pointers to the previous elements.

For an element in a doubly linked list, it contains the following attributes:

x.key: the key used to identify the element
x.next: a pointer to the next element
x.prev: a pointer to the previous element

Data Structures and Algorithms (H) Lecture 8 Notes