_{References used for this section: A}

**Elementary Data Structures**

Sets form the basis of both Mathematics and Computer Science. In Mathematics, we usually deal **static** (or frozen) sets. In other words, sets that don’t change much after their definition. In computer science, it is also common to deal with **dynamic sets**. A dynamic set is a set which allows the insertion and deletion of elements.

Just like static sets have operations like union, intersection etc., dynamic sets have additional operations. The operations on a dynamic set are divided into two categories:

- Queries – only return information from the set.
- Modifying Operations – change the set.

Here are some common dynamic set operations:

= the set. = the key value. = pointer to an element in the set.

**Queries**

Search (S, k): returns a pointer to an element in such that , or if contains no such element.

Minimum(S): Let be a totally ordered set. This returns a pointer to the element in with the smallest key.

Maximum(S): Let be a totally ordered set. This returns a pointer to the element in $latex $$ with the largest key.

Successor(S, x): Let be a totally ordered set. This returns a pointer to the element that is the next largest to the one pointed to by , or if points to the largest element.

Predecessor(S, x): Let be a totally ordered set. This returns a pointer to the element that is the next smallest to the one pointed to by , or if points to the smallest element.

**Dynamic Operations**

Insert(S, x): Adds the element pointed to by to the set , assuming the element already has the attributes necessary to be a part of .

Delete(S, x): Removes the element pointed to by from the set .

**Two Important Dynamic Sets**

Stack: A stack has a prespecified delete operation. It implements what is called the *last-in first-out* (or *LIFO* for short) policy. The first element that gets deleted is the last element that was inserted into the stack.

Queue: A queue also has a prespecified delete operation. It implements the *first-in first-out* (or *FIFO* for short) policy. The first element that gets deleted is the first element that was inserted into a queue.

**Implementing a Stack**

Here’s a figure I got from wikipedia that makes it easy to understand how a stack works:

A stack of at most elements can be implemented using the following:

- An array .
- An attribute of the array, which stores the index of the most recently inserted element.

Stack Operations:

To implement a stack, you need the following three operations:

A query to check if the stack is empty.

STACK-EMPTY(S) if S.top == 0 return TRUE else return FALSE

The insert operation, which in this case is called *push*. A dynamic operation.

PUSH(S, x) S.top = S.top + 1 S[S.top] = x

The delete operation, which in this case is called *pop*. A dynamic operation.

POP(S) if STACK-EMPTY(S) error &quot;underflow&quot; else S.top = S.top - 1 return S[S.top + 1]

Notes:

- When , the stack is empty.
- The stack
*underflows*when we try to pop an empty stack - The stack
*overflows*if exceeds the value of .

**Implementing a Queue**

Here’s a figure I got from wikipedia that makes it easy to understand how a queue works:

A stack of at most elements can be implemented using the following:

- An array .
- An attribute of the array that indexes the head of the queue.
- An attribute of the array that indexes the tail of the queue.

Queue Operations:

To implement a queue, you need the following two dynamic operations.

The insert operation, called *enqueue* in this case.

ENQUEUE(Q, x) Q[Q.tail] = x if Q.tail == Q.length Q.tail = 1 else Q.tail = Q.tail + 1

and the delete operation, called *dequeue*.

DEQUEUE(Q) x = Q[Q.head] if Q.head == Q.length Q.head = 1 else Q.head = Q.head + 1 return x

To understand this better, refer to figure 10.2 in Section 10.1 of *Introduction to Algorithms* 3rd Edition by Cormen et al.