# Algorithms Notes – Chapter 3

xkcd/399

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:

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

Here are some common dynamic set operations:

$S$ = the set. $k$ = the key value. $x$ = pointer to an element in the set.

Queries

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

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

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

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

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

Dynamic Operations

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

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

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 $n$ elements can be implemented using the following:

• An array $S[1 ... n]$.
• An attribute of the array, $S.top$ 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 &amp;quot;underflow&amp;quot;
else
S.top = S.top - 1
return S[S.top + 1]
```

Notes:

• When $S.top = 0$, the stack is empty.
• The stack underflows when we try to pop an empty stack
• The stack overflows if $S.top$ exceeds the value of $n$.

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 $n - 1$ elements can be implemented using the following:

• An array $Q[1 ... n]$.
• An attribute of the array $Q.head$ that indexes the head of the queue.
• An attribute of the array $Q.tail$ 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)