Stacks & Queues: Array & Linked List Implementations

Defining Stacks and Queues

At their core, Stacks and Queues are simple, linear data structures that restrict how elements can be added and removed. This restriction gives them their unique properties and makes them suitable for specific types of problems.

As you just saw, the defining characteristics are:

• Stack: Operates on a Last-In, First-Out (LIFO) principle. The last element added is the first one to be removed.
• Queue: Operates on a First-In, First-Out (FIFO) principle. The first element added is the first one to be removed.

The Stack ADT: Implementations and Analysis

A stack supports three primary operations:

• push(element): Adds an element to the top of the stack.
• pop(): Removes and returns the element from the top of the stack.
• peek() (or top()): Returns the top element without removing it.
• isEmpty(): A helper function to check if the stack is empty.

Let's explore the two common ways to implement a stack.

1. Array-Based Implementation

The most straightforward way to build a stack is using an array (either static or dynamic) and an integer variable, often called top, to keep track of the index of the top element.

• Initialization: The array is created, and top is initialized to -1, indicating an empty stack.
• Push: To push an element, we first increment top, then place the new element at array[top]. We must check for overflow before pushing if the array is full.
• Pop: To pop, we retrieve the element at array[top], then decrement top. We must check for underflow before popping if the stack is empty (top == -1).
• Peek: Simply returns array[top] without changing top.

Complexity Analysis (Array-based Stack):

• push, pop, peek, isEmpty are all $O(1)$ operations. They involve simple index manipulation and array access.
• Caveat: If you use a dynamic array that needs resizing, a push operation that triggers a resize will take $O(n)$ time. However, as we saw in the last lesson, the amortized cost of push remains $O(1)$.
• Drawback: The primary limitation is either the fixed capacity of a static array or the occasional expensive resizing cost of a dynamic array.

2. Linked List-Based Implementation

A stack can also be elegantly implemented using a singly linked list. We only need a single pointer, top, which will point to the head of the list.

• Push: This is equivalent to inserting a new node at the beginning of the linked list.
  1. Create a new node.
  2. Set its next pointer to the current top.
  3. Update top to point to the new node.
• Pop: This is equivalent to deleting the head of the linked list.
  1. Check for underflow (top == null).
  2. Store the data from the top node.
  3. Update top to point to top.next.
  4. Return the stored data.

Complexity Analysis (Linked List-based Stack):

• push, pop, peek, isEmpty are all worst-case $O(1)$ operations.
• Advantage: This implementation offers true dynamic resizing without any amortized costs. The stack can grow and shrink one element at a time, smoothly.

The Queue ADT: Implementations and Analysis

A queue's operations reflect its FIFO nature:

• enqueue(element): Adds an element to the rear of the queue.
• dequeue(): Removes and returns the element from the front of the queue.
• peek() (or front()): Returns the front element without removing it.
• isEmpty(): Checks if the queue is empty.

1. Linked List-Based Implementation

This is often the most intuitive way to implement a queue. We use a singly linked list but maintain two pointers: front (pointing to the head) and rear (pointing to the tail).

• Enqueue: Add a new node at the end of the list.
  1. Create a new node.
  2. If the queue is empty, set both front and rear to the new node.
  3. Otherwise, set rear.next to the new node and update rear to be the new node.
• Dequeue: Remove the node from the head of the list.
  1. Check for underflow.
  2. Store the data from the front node.
  3. Update front to front.next.
  4. If the queue is now empty, update rear to null as well.

Complexity Analysis (Linked List-based Queue):

• Thanks to the rear pointer, enqueue is $O(1)$. dequeue, peek, and isEmpty are also $O(1)$.
• This is a highly efficient and flexible implementation.

2. Array-Based Implementation (The Circular Queue)

A naive array implementation of a queue is problematic. If we use indices front and rear, both would move in one direction. After several dequeues, the front of the array would become unused, wasted space.

The solution is a Circular Array (or Ring Buffer). We treat the array as if the end connects back to the beginning. This is achieved using the modulo operator.

• Structure: An array, front and rear indices, and a size or capacity.
• Enqueue: An element is added at array[rear]. The rear index is then updated: rear = (rear + 1) % capacity.
• Dequeue: An element is taken from array[front]. The front index is updated: front = (front + 1) % capacity.
• Edge Cases: The conditions for empty and full are subtle.
  • Empty: A common convention is front == rear.
  • Full: To distinguish a full queue from an empty one, we can either keep a count variable, or sacrifice one array slot and define "full" as (rear + 1) % capacity == front.

A circular queue uses front and rear indices that wrap around the array. When rear reaches the end, it wraps to index 0, effectively reusing space at the beginning of the array.

Complexity Analysis (Circular Array-based Queue):

• All operations (enqueue, dequeue, peek, isEmpty) are $O(1)$.
• Advantage: Excellent memory locality, which can lead to better performance in practice due to CPU caching.
• Drawback: Fixed capacity.

Application: Infix to Postfix Conversion

A classic application of stacks, and a favorite in GATE, is the conversion of arithmetic expressions. Humans write expressions in infix notation (A + B), but for a computer, postfix notation (A B +), also known as Reverse Polish Notation (RPN), is much easier to parse.

Algorithm: Infix to Postfix

We use a stack to hold operators and parentheses. The goal is to process the infix expression and output a postfix one, respecting operator precedence.

Let's define precedence: *, / have higher precedence than +, -.

The algorithm is as follows:

1. Initialize an empty stack and an empty result string.
2. Scan the infix expression from left to right, token by token.
3. If the token is an operand (e.g., A, B, 5): Append it directly to the result.
4. If the token is an opening parenthesis (: Push it onto the stack.
5. If the token is a closing parenthesis ): Pop operators from the stack and append them to the result until an opening parenthesis ( is found. Pop and discard the (.
6. If the token is an operator:
   • While the stack is not empty, its top is not (, AND the precedence of the current operator is less than or equal to the precedence of the operator on top of the stack:
     • Pop the operator from the stack and append it to the result.
   • Push the current operator onto the stack.
7. After scanning the whole expression, pop any remaining operators from the stack and append them to the result.

Example Walkthrough: A + B * C - D

The final postfix expression is A B C * + D -.

Algorithm: Postfix Evaluation

Evaluating a postfix expression is even more straightforward with a stack.

1. Initialize an empty stack.
2. Scan the postfix expression from left to right.
3. If the token is an operand: Push it onto the stack.
4. If the token is an operator:
   • Pop two operands from the stack (let's call them op2 then op1).
   • Compute op1 operator op2.
   • Push the result back onto the stack.
5. After the scan, the final result is the single value left on the stack.

Conclusion

In this lesson, we demystified Stacks (LIFO) and Queues (FIFO). You learned how to implement both ADTs using two different underlying data structures—arrays and linked lists—and critically analyzed the trade-offs of each.

Key Takeaways:

• Stack: A LIFO structure. Both array and linked-list implementations provide $O(1)$ time for all core operations (push, pop, peek).
• Queue: A FIFO structure. The linked-list implementation (with front and rear pointers) and the circular array implementation both provide $O(1)$ time for enqueue and dequeue.
• Array vs. Linked List: The primary trade-off is fixed size and cache-friendliness (arrays) versus dynamic size and pointer overhead (linked lists). For GATE, you must be comfortable with the mechanics of both.
• Circular Queue: This is the standard and efficient way to implement a queue with an array, avoiding wasted space by allowing indices to wrap around.
• Expression Evaluation: Stacks are perfectly suited for parsing and evaluating expressions, a common application tested in competitive exams.

In our previous lesson, we touched on linked lists as a concept. In the next lesson, we will dive deep into Linked Lists themselves, exploring their variations (singly, doubly, circular), mastering complex pointer manipulations for operations like reversal, and learning Floyd's algorithm for cycle detection.