4- Stacks and Queues¶
Stack (LIFO): returns the most recently inserted item first.
Queue (FIFO): returns the oldest inserted item first.
This difference significantly affects algorithms and efficiency. For example:
Stacks form the core of depth-first search (DFS).
Queues enable breadth-first search (BFS).
Stacks¶
A stack is a Last-In, First-Out (LIFO) structure.
Push: Add a new element to the top.
Pop: Remove the top element.
Example: pushing 1, 2, 3, 4, 5 → popping returns 5, 4, 3, 2, 1.
We can implement stacks with either arrays or linked lists.
Stacks as Arrays¶
A stack can be represented with an array and a variable top:
Stack {
Integer: array_size
Integer: top
Array of values: array
}
top = -1initially means the stack is empty.
Push Operation
Push(Stack: s, Type: value):
IF s.top == s.array_size – 1:
Expand the size of the array
s.top = s.top + 1
s.array[s.top] = value
Pop Operation
Pop(Stack: s):
Type: value = null
IF s.top > -1:
value = s.array[s.top]
s.top = s.top – 1
return value
Note
Both push and pop run in constant time, except when resizing the array.
Stacks as Linked Lists¶
A stack can also be represented as a linked list:
Stack {
LinkedListNode: head
}
Push Operation
Push(Stack: s, Type: value):
LinkedListNode: node = LinkedListNode(value)
node.next = s.head
s.head = node
Pop Operation
Pop(Stack: s):
Type: value = null
IF s.head != null:
value = s.head.value
s.head = s.head.next
return value
Linked lists avoid resizing issues but add pointer overhead.
Still O(1) for push and pop.
Queues¶
A queue is a First-In, First-Out (FIFO) structure.
Enqueue: Add a new element at the back.
Dequeue: Remove the element at the front.
Queues can be implemented with arrays or linked lists.
Queues as Arrays¶
A queue needs two indices: front and back.
Enqueue: Insert at
back.Dequeue: Remove from
front.
Challenge: empty space accumulates at the front. Solutions:
Shifting elements (inefficient).
Wrapping indices (circular queue).
Queues as Linked Lists¶
More efficient implementation with head and tail pointers:
Queue {
LinkedListNode: front
LinkedListNode: back
}
Enqueue Operation
Enqueue(Queue: q, Type: value):
LinkedListNode: node = LinkedListNode(value)
IF q.back == null:
q.front = node
q.back = node
ELSE:
q.back.next = node
q.back = node
Dequeue Operation
Dequeue(Queue: q):
IF q.front == null:
return null
Type: value = q.front.value
q.front = q.front.next
IF q.front == null:
q.back = null
return value
Both enqueue and dequeue run in O(1) time.
The Importance of Order¶
Stacks (LIFO): process newest items first. - Example: function calls use stacks.
Queues (FIFO): process oldest items first. - Example: network requests.
The order of access changes algorithm behavior.
Depth-First Search (DFS)¶
Uses a stack to track unexplored options.
Explores deep into one path before backtracking.
Ideal when focusing on the most recent discovery.
Breadth-First Search (BFS)¶
Uses a queue to track unexplored options.
Explores all neighbors before going deeper.
Ideal when surveying all possibilities evenly.
Why This Matters¶
Both stacks and queues:
Can be implemented with arrays or linked lists.
Support efficient O(1) insertion and removal.
But:
Stacks → newest-first behavior.
Queues → oldest-first behavior.
This ordering difference shapes algorithm performance and behavior. Swapping one data structure for another can transform a depth-first process into a breadth-first one.
Stack Clone¶
#include <iostream>
using namespace std;
// Node structure for linked list
struct Node
{
int data; // the value stored in this node
Node* next; // pointer to the next node
};
// Stack implemented with a linked list
class Stack
{
private:
Node* top; // pointer to the top of the stack
public:
// Constructor: stack starts empty
Stack()
{
top = nullptr;
}
// Destructor: free all nodes in the stack
~Stack()
{
while (!isEmpty())
{
pop(); // reuse pop() to delete nodes
}
}
// Push: add a new element to the top
void push(int value)
{
Node* newNode = new Node(); // allocate new node
newNode->data = value; // set node's data
newNode->next = top; // point it to the old top
top = newNode; // update top to new node
cout << value << " pushed onto stack." << endl;
}
// Pop: remove and return the top element
void pop()
{
if (isEmpty())
{
cout << "Stack Underflow! Nothing to pop." << endl;
return;
}
Node* temp = top; // store the top node
cout << temp->data << " popped from stack." << endl;
top = top->next; // move top down to next node
delete temp; // free memory
}
// Peek: return the top element without removing it
int peek()
{
if (isEmpty())
{
cout << "Stack is empty, nothing to peek." << endl;
return -1; // sentinel value
}
return top->data;
}
// Check if the stack is empty
bool isEmpty()
{
return (top == nullptr);
}
// Display all elements in the stack
void display()
{
if (isEmpty())
{
cout << "Stack is empty." << endl;
return;
}
cout << "Stack elements (top to bottom): ";
Node* current = top;
while (current != nullptr)
{
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};
// Driver code
int main()
{
Stack s;
s.push(10);
s.push(20);
s.push(30);
s.display(); // should print: 30 20 10
cout << "Top element is: " << s.peek() << endl;
s.pop();
s.display(); // should print: 20 10
s.push(40);
s.push(50);
s.display(); // should print: 50 40 20 10
return 0;
}