Stack Algorithms: Push and Pop
Definition
A stack is a last in, first out (LIFO) data structure. It can be stored in an array with a pointer, top, that holds the index of the item most recently added.
pseudocode
// stack has indexes 0 to maxSize - 1; top = -1 when the stack is empty
procedure push(item):
if top == maxSize - 1 then
print("Stack is full")
else
top = top + 1
stack[top] = item
end if
end procedure
function pop():
if top == -1 then
print("Stack is empty")
return null
else
item = stack[top]
top = top - 1
return item
end if
end functionQueue Algorithms: Enqueue and Dequeue
Definition
A queue is a first in, first out (FIFO) data structure. It can be stored in an array with two pointers: front holds the index of the next item to leave and rear holds the index of the item most recently added.
pseudocode
// queue has indexes 0 to maxSize - 1; front = 0 and rear = -1 when the queue is empty
procedure enqueue(item):
if rear == maxSize - 1 then
print("Queue is full")
else
rear = rear + 1
queue[rear] = item
end if
end procedure
function dequeue():
if front > rear then
print("Queue is empty")
return null
else
item = queue[front]
front = front + 1
return item
end if
end functionWorked Example
Tracing the Pointers
The same data passed through a queue leaves in the order in which it arrived:
| Operation | Stack (bottom to top) | top | Returned |
|---|---|---|---|
| push(5) | 5 | 0 | Nothing |
| push(8) | 5, 8 | 1 | Nothing |
| pop() | 5 | 0 | 8 |
| push(3) | 5, 3 | 1 | Nothing |
| Operation | Queue (front to rear) | front | rear | Returned |
|---|---|---|---|---|
| enqueue(5) | 5 | 0 | 0 | Nothing |
| enqueue(8) | 5, 8 | 0 | 1 | Nothing |
| dequeue() | 8 | 1 | 1 | 5 |
| enqueue(3) | 8, 3 | 1 | 2 | Nothing |
Key Point
Push, pop, enqueue and dequeue each take the same time however many items are stored, so all four are O(1).
In the queue above, space at the front of the array is never used again. A circular queue solves this by letting the pointers wrap round to index 0, using rear = (rear + 1) MOD maxSize.
In the queue above, space at the front of the array is never used again. A circular queue solves this by letting the pointers wrap round to index 0, using rear = (rear + 1) MOD maxSize.
Linked List Algorithms
Definition
A linked list stores each item in a node together with a pointer to the next node. headPointer holds the position of the first node, the pointer of the last node is NULL, and freeListPointer holds the position of the first unused node.
pseudocode
// Traverse the list to search for an item
function search(toFind):
currentNode = headPointer
while currentNode != NULL:
if linkedList[currentNode].data == toFind then
return currentNode
end if
currentNode = linkedList[currentNode].pointer
end while
return -1
end function| Operation | Steps |
|---|---|
| Traverse | Start at headPointer, process the node, then follow its pointer to the next node; stop when the pointer is NULL |
| Add an item | Store the data in the node that freeListPointer points to and move freeListPointer on to the next free node; follow the pointers from headPointer to find where the item belongs; set the new node's pointer to the node that will follow it; change the pointer of the node before it to point to the new node |
| Remove an item | Follow the pointers from headPointer to find the node; change the pointer of the node before it to the node after it, so that the list passes over the removed node; add the removed node to the free list |
Worked Example
Adding "Dog" to an Ordered Linked List
Before: headPointer = 1 and freeListPointer = 3. Following the pointers gives Ant, Cat, Fox.
"Dog" is stored at index 3, the first free node, and freeListPointer moves on to 4. Dog belongs between Cat and Fox, so Dog's pointer is set to 2 and Cat's pointer is changed from 2 to 3.
After: headPointer = 1 and freeListPointer = 4. Following the pointers gives Ant, Cat, Dog, Fox. No data was moved: only pointers changed.
Before: headPointer = 1 and freeListPointer = 3. Following the pointers gives Ant, Cat, Fox.
| Index | Data | Pointer |
|---|---|---|
| 0 | Cat | 2 |
| 1 | Ant | 0 |
| 2 | Fox | NULL |
| 3 | (free) | 4 |
| 4 | (free) | NULL |
| Index | Data | Pointer |
|---|---|---|
| 0 | Cat | 3 |
| 1 | Ant | 0 |
| 2 | Fox | NULL |
| 3 | Dog | 2 |
| 4 | (free) | NULL |