L1. Introduction to Stack and Queue | Implementation using Data Structures

This comprehensive foundational guide introduces stacks and queues, explores their core operational mechanisms (LIFO vs. FIFO), details their native memory implementations using arrays and linked lists, and demonstrates advanced algorithmic conversions of implementing a stack using queues and a queue using stacks.

1. Why Do We Need Stacks and Queues?

Linear data structures like arrays and linked lists allow unrestricted access and modification at any arbitrary index. However, many real-world computational problems require controlled, restricted access patterns where elements must be processed strictly in specific chronological sequences (such as undo operations, browser history, function call management, and task scheduling).

• The Stack Paradigm: Models vertical stacking where access is restricted strictly to the top element.
• The Queue Paradigm: Models waiting lines where elements enter at the rear and exit from the front.

2. Core Mental Model & Analogies

Real-Life Analogy: The Stack

Real-Life Analogy: Think of a vertical stack of plates in a cafeteria. You can only add a new plate to the very top (push) and you can only remove the top plate (pop). If you want the bottom plate, you must remove every plate above it first. This is the physical manifestation of LIFO (Last In, First Out).

Real-Life Analogy: The Queue

Real-Life Analogy: Think of a ticketing counter line or a queue at a coffee shop. New customers join at the back (push/enqueue), and the person at the front is served and leaves first (pop/dequeue). This is the physical manifestation of FIFO (First In, First Out).

3. Stack Data Structure: Mechanics & Operations

A Stack is a container-based data structure that holds a collection of data of any type (integers, strings, custom objects) governed strictly by the LIFO (Last In, First Out) principle.

Standard Stack Interface

1. push(value): Inserts an element onto the top of the stack.
2. pop(): Removes the topmost element from the stack.
3. top() (or peek()): Retrieves the topmost element without removing it.
4. size(): Returns the total count of elements currently in the stack.

Step-by-Step Stack Flow Walkthrough

Let us trace the operations: push(2), push(3), push(4), push(1), pop(), top(), top(), pop(), pop(), push(5), top(), size().

4. Queue Data Structure: Mechanics & Operations

A Queue is a linear data structure that holds a collection of data governed strictly by the FIFO (First In, First Out) principle.

Standard Queue Interface

1. push(value): Inserts an element at the rear (end) of the queue.
2. pop(): Removes the element from the front (start) of the queue.
3. top() (or front()): Retrieves the front element without removing it.
4. size(): Returns the total count of elements in the queue.

Step-by-Step Queue Flow Walkthrough

Let us trace the operations: push(2), push(1), push(3), push(4), pop(), top(), pop(), top(), push(7), top(), size().

5. Built-In Libraries vs. Low-Level Implementation

In production environments, competitive programming, and software engineering, you should never write custom stack or queue implementations from scratch unless specifically requested. Every standard language provides robust built-in libraries:

However, technical interviewers frequently ask: "How are these data structures implemented under the hood within the standard library?" Let's explore array and linked list implementations.

6. Implementing Stack Using Arrays

To implement a stack using a fixed-size array, we maintain a pointer/index called top initialized to -1.

Array Stack Implementation Logic

• push(x): Increment top by 1 (top++), then store x at array[top].
• pop(): Decrement top by 1 (top--). (Physical deletion is unnecessary; the top pointer controls valid scope).
• top(): Return array[top].
• size(): Return top + 1.

C++ Code Implementation (Stack using Array)

class StackUsingArray {
    int* arr;
    int topIndex;
    int capacity;

public:
    StackUsingArray(int size = 10) {
        capacity = size;
        arr = new int[capacity];
        topIndex = -1;
    }

    void push(int x) {
        if (topIndex >= capacity - 1) {
            cout << "Stack Overflow Error!\n";
            return;
        }
        arr[++topIndex] = x;
    }

    void pop() {
        if (topIndex == -1) {
            cout << "Stack Underflow Error!\n";
            return;
        }
        topIndex--;
    }

    int top() {
        if (topIndex == -1) {
            cout << "Stack is Empty!\n";
            return -1;
        }
        return arr[topIndex];
    }

    int size() {
        return topIndex + 1;
    }

    bool isEmpty() {
        return topIndex == -1;
    }
};

• Time Complexity: $O(1)$ for push, pop, top, and size.
• Space Complexity: $O(N)$ fixed-size auxiliary array storage.

7. Implementing Queue Using Arrays (Circular Array)

Implementing a queue using a static array requires two pointers (start and end) and a currentSize tracker. To prevent array exhaustion when indices reach the end while empty slots exist at the front, we use circular array arithmetic modulo capacity.

Circular Array Queue Logic

• push(x):
  1. Check if currentSize == capacity (Overflow).
  2. If queue is empty (currentSize == 0), set start = 0, end = 0.
  3. Else, advance end circularly: end = (end + 1) % capacity.
  4. Store x at arr[end], increment currentSize.
• pop():
  1. Check if currentSize == 0 (Underflow).
  2. If currentSize == 1, reset start = -1, end = -1.
  3. Else, advance start circularly: start = (start + 1) % capacity.
  4. Decrement currentSize.

C++ Code Implementation (Queue using Circular Array)

class QueueUsingArray {
    int* arr;
    int start, end, currentSize, capacity;

public:
    QueueUsingArray(int size = 10) {
        capacity = size;
        arr = new int[capacity];
        start = -1;
        end = -1;
        currentSize = 0;
    }

    void push(int x) {
        if (currentSize == capacity) {
            cout << "Queue Overflow!\n";
            return;
        }
        if (currentSize == 0) {
            start = 0;
            end = 0;
        } else {
            end = (end + 1) % capacity;
        }
        arr[end] = x;
        currentSize++;
    }

    void pop() {
        if (currentSize == 0) {
            cout << "Queue Underflow!\n";
            return;
        }
        if (currentSize == 1) {
            start = -1;
            end = -1;
        } else {
            start = (start + 1) % capacity;
        }
        currentSize--;
    }

    int front() {
        if (currentSize == 0) {
            cout << "Queue is Empty!\n";
            return -1;
        }
        return arr[start];
    }

    int size() {
        return currentSize;
    }
};

• Time Complexity: $O(1)$ across all operations.
• Space Complexity: $O(N)$ fixed capacity.

8. Implementing Stack Using Linked List

Arrays impose static size limits. Using a Linked List provides dynamic sizing where memory is allocated on demand.

Linked List Stack Logic

• We maintain a top node pointer (initially nullptr) and a size counter.
• push(x): Create a new node with value x. Set newNode->next = top, then update top = newNode.
• pop(): Store temp = top, update top = top->next, delete temp.

C++ Code Implementation (Stack using Linked List)

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class StackUsingLinkedList {
    Node* topNode;
    int stackSize;

public:
    StackUsingLinkedList() {
        topNode = nullptr;
        stackSize = 0;
    }

    void push(int x) {
        Node* temp = new Node(x);
        temp->next = topNode;
        topNode = temp;
        stackSize++;
    }

    void pop() {
        if (topNode == nullptr) {
            cout << "Stack Underflow!\n";
            return;
        }
        Node* temp = topNode;
        topNode = topNode->next;
        delete temp;
        stackSize--;
    }

    int top() {
        if (topNode == nullptr) return -1;
        return topNode->data;
    }

    int size() {
        return stackSize;
    }
};

• Time Complexity: $O(1)$ for all operations.
• Space Complexity: $O(N)$ dynamic memory corresponding strictly to active elements.

9. Implementing Queue Using Linked List

A Queue using a linked list requires maintaining both start (front) and end (rear) pointers.

Linked List Queue Logic

• push(x): Create newNode. If queue is empty (start == nullptr), set both start and end to newNode. Otherwise, attach to end->next = newNode, then update end = newNode.
• pop(): Save temp = start. Advance start = start->next. If start becomes nullptr, set end = nullptr. Delete temp.

C++ Code Implementation (Queue using Linked List)

class QueueUsingLinkedList {
    Node* start;
    Node* end;
    int qSize;

public:
    QueueUsingLinkedList() {
        start = nullptr;
        end = nullptr;
        qSize = 0;
    }

    void push(int x) {
        Node* newNode = new Node(x);
        if (start == nullptr) {
            start = end = newNode;
        } else {
            end->next = newNode;
            end = newNode;
        }
        qSize++;
    }

    void pop() {
        if (start == nullptr) {
            cout << "Queue Underflow!\n";
            return;
        }
        Node* temp = start;
        start = start->next;
        if (start == nullptr) {
            end = nullptr;
        }
        delete temp;
        qSize--;
    }

    int front() {
        if (start == nullptr) return -1;
        return start->data;
    }

    int size() {
        return qSize;
    }
};

• Time Complexity: $O(1)$ for all operations.
• Space Complexity: $O(N)$ dynamic memory.

10. Implementing Stack Using Queues

How can we simulate a Stack (LIFO) using only Queue (FIFO) data structures?

Method: Push-Expensive Rearrangement Strategy

We use a single Queue (q). When pushing a new element, we manipulate the queue order so that the newly inserted element always sits at the front of the queue.

Algorithm Walkthrough for push(x):

1. Get current size of queue: int s = q.size();
2. Push new element x into the queue: q.push(x);
3. Rotate existing elements behind the new element by popping and re-pushing s times:
   C++

   Copy

   for (int i = 0; i < s; i++) {
       q.push(q.front());
       q.pop();
   }
   

C++ Code Implementation

#include <queue>
using namespace std;

class StackUsingQueue {
    queue<int> q;

public:
    void push(int x) {
        int s = q.size();
        q.push(x);
        for (int i = 0; i < s; i++) {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() {
        int val = q.front();
        q.pop();
        return val;
    }

    int top() {
        return q.front();
    }

    int size() {
        return q.size();
    }
};

• Time Complexity: Push is $O(N)$, while pop, top, and size are $O(1)$.
• Space Complexity: $O(N)$.

11. Implementing Queue Using Stacks

Simulating a Queue (FIFO) using two Stacks (S1 and S2) can be approached via two distinct strategies depending on whether you want push or pop to bear the computational cost.

Approach 1: Push-Expensive (Using Two Stacks)

• push(x):
  1. Transfer all elements from S1 to S2.
  2. Push new element x onto S1.
  3. Transfer all elements back from S2 to S1.
• pop() / top(): Direct operations on S1 in $O(1)$ time.

Approach 2: Amortized O(1) Pop/Top (Optimized Strategy)

To avoid the $O(N)$ penalty on every push operation, we optimize push to $O(1)$ and delegate transfer work to pop/top only when S2 is empty.

C++ Code Implementation (Optimized Approach 2)

#include <stack>
using namespace std;

class QueueUsingTwoStacks {
    stack<int, int> s1, s2;

public:
    void push(int x) {
        s1.push(x); // O(1) push
    }

    int pop() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int val = s2.top();
        s2.pop();
        return val;
    }

    int top() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }

    int size() {
        return s1.size() + s2.size();
    }
};

• Time Complexity:
  • Push: $O(1)$
  • Pop / Top: Amortized $O(1)$ (each element is moved between stacks at most twice across its lifecycle).
• Space Complexity: $O(2N) \rightarrow O(N)$ auxiliary stack storage.

Summary and Key Takeaways

• Stack Principle: Follows LIFO (Last In, First Out) with core operations push, pop, and top.
• Queue Principle: Follows FIFO (First In, First Out) with core operations push, pop, and front.
• Array Implementation (Stack): Uses a top index starting at -1, operating in $O(1)$ time with a fixed static size.
• Array Implementation (Queue): Requires circular indexing ((index + 1) % capacity) to efficiently utilize array memory without shifting elements.
• Linked List Implementation: Eliminates static size constraints, providing true dynamic memory allocation with $O(1)$ operational complexity.
• Stack via Queue: Achieved by rotating incoming elements to keep the newest element at the front of a single queue ($O(N)$ push).
• Queue via Stack: Optimized using two stacks (S1 for pushes, S2 for pops) achieving amortized $O(1) time complexity for dequeue operations.