Introduction

Stacks and Queues are fundamental linear data structures that follow specific patterns for data insertion and deletion. A Stack follows Last-In-First-Out (LIFO) principle, while a Queue follows First-In-First-Out (FIFO) principle.

Stack Implementation

1. Array-based Implementation


class Stack {
    private:
        int top;
        int capacity;
        int* array;
    
    public:
        Stack(int size) {
            capacity = size;
            top = -1;
            array = new int[capacity];
        }
        
        bool push(int value) {
            if (top >= capacity - 1) return false;
            array[++top] = value;
            return true;
        }
        
        int pop() {
            if (top < 0) return -1;
            return array[top--];
        }
        
        int peek() {
            if (top < 0) return -1;
            return array[top];
        }
        
        bool isEmpty() {
            return top < 0;
        }
};

2. Linked List Implementation


class Node {
public:
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

class LinkedStack {
private:
    Node* top;
    
public:
    LinkedStack() : top(nullptr) {}
    
    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
    }
    
    int pop() {
        if (!top) return -1;
        int value = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return value;
    }
};

Stack Applications

1. Balancing Parentheses


bool areParenthesesBalanced(string expr) {
    stack s;
    
    for (char c : expr) {
        if (c == '(' || c == '{' || c == '[')
            s.push(c);
        else {
            if (s.empty()) return false;
            
            char top = s.top();
            if ((c == ')' && top == '(') ||
                (c == '}' && top == '{') ||
                (c == ']' && top == '['))
                s.pop();
            else
                return false;
        }
    }
    return s.empty();
}

2. Next Greater Element


vector nextGreaterElements(vector& nums) {
    int n = nums.size();
    vector result(n, -1);
    stack s;
    
    for (int i = 0; i < n * 2; i++) {
        while (!s.empty() && nums[s.top()] < nums[i % n]) {
            result[s.top()] = nums[i % n];
            s.pop();
        }
        if (i < n) s.push(i);
    }
    return result;
}

3. Min Stack


class MinStack {
private:
    stack mainStack;
    stack minStack;

public:
    void push(int val) {
        mainStack.push(val);
        if (minStack.empty() || val <= minStack.top())
            minStack.push(val);
    }
    
    void pop() {
        if (mainStack.top() == minStack.top())
            minStack.pop();
        mainStack.pop();
    }
    
    int top() {
        return mainStack.top();
    }
    
    int getMin() {
        return minStack.top();
    }
};

Queue Implementation and Variants

1. Circular Queue


class CircularQueue {
private:
    int* arr;
    int front, rear;
    int capacity;
    
public:
    CircularQueue(int size) {
        capacity = size;
        arr = new int[capacity];
        front = rear = -1;
    }
    
    bool enqueue(int value) {
        if ((front == 0 && rear == capacity-1) || 
            (rear == (front-1)%(capacity-1)))
            return false;
            
        if (front == -1) {
            front = rear = 0;
            arr[rear] = value;
        }
        else {
            rear = (rear + 1) % capacity;
            arr[rear] = value;
        }
        return true;
    }
    
    int dequeue() {
        if (front == -1) return -1;
        
        int value = arr[front];
        if (front == rear)
            front = rear = -1;
        else
            front = (front + 1) % capacity;
            
        return value;
    }
};

2. Priority Queue


class PriorityQueue {
private:
    vector heap;
    
    void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[parent] > heap[index]) {
                swap(heap[parent], heap[index]);
                index = parent;
            } else break;
        }
    }
    
    void heapifyDown(int index) {
        int size = heap.size();
        while (true) {
            int smallest = index;
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            
            if (left < size && heap[left] < heap[smallest])
                smallest = left;
            if (right < size && heap[right] < heap[smallest])
                smallest = right;
                
            if (smallest == index) break;
            
            swap(heap[index], heap[smallest]);
            index = smallest;
        }
    }
    
public:
    void push(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }
    
    int pop() {
        if (heap.empty()) return -1;
        
        int result = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        
        if (!heap.empty())
            heapifyDown(0);
            
        return result;
    }
};

3. Double-Ended Queue (Deque)


class Deque {
private:
    vector arr;
    int front, rear;
    int size;
    
public:
    Deque(int n) {
        arr.resize(n);
        front = -1;
        rear = 0;
        size = n;
    }
    
    bool pushFront(int value) {
        if (isFull()) return false;
        
        if (front == -1) {
            front = 0;
            rear = 0;
        }
        else if (front == 0)
            front = size - 1;
        else
            front--;
            
        arr[front] = value;
        return true;
    }
    
    bool pushRear(int value) {
        if (isFull()) return false;
        
        if (front == -1) {
            front = 0;
            rear = 0;
        }
        else if (rear == size - 1)
            rear = 0;
        else
            rear++;
            
        arr[rear] = value;
        return true;
    }
    
    bool isFull() {
        return (front == 0 && rear == size-1) || 
               (front == rear + 1);
    }
};

STL Implementations


// Stack
#include 
stack s;
s.push(1);
s.pop();
s.top();
s.empty();

// Queue
#include 
queue q;
q.push(1);
q.pop();
q.front();
q.back();
q.empty();

// Priority Queue
#include 
priority_queue pq;                    // Max heap
priority_queue, greater> minpq;  // Min heap
pq.push(1);
pq.pop();
pq.top();
pq.empty();

Common Interview Questions

1. Implement Queue using Stacks

Question: How would you implement a queue using only stacks?

Answer: Use two stacks. For enqueue, push to stack1. For dequeue, if stack2 is empty, pop all elements from stack1 and push to stack2, then pop from stack2. This maintains FIFO order.

2. Sliding Window Maximum

Question: Find the maximum element in all sliding windows of size k in an array.

Answer: Use a deque to maintain indices of potential maximum elements. The front of deque always contains the maximum for current window.

3. Sort a Stack

Question: Sort a stack using only one additional stack.

Answer: Use a temporary stack. Pop elements from original stack and insert them in sorted order in temporary stack using an additional variable to hold elements temporarily.

Time Complexity Analysis

Operation	Stack	Queue	Priority Queue
Push/Enqueue	O(1)	O(1)	O(log n)
Pop/Dequeue	O(1)	O(1)	O(log n)
Peek/Top	O(1)	O(1)	O(1)
Search	O(n)	O(n)	O(n)
Space Complexity	O(n)	O(n)	O(n)

Advanced Applications

1. Expression Evaluation


int evaluatePostfix(string exp) {
    stack st;
    
    for(char c : exp) {
        if(isdigit(c)) {
            st.push(c - '0');
        }
        else {
            int val1 = st.top(); st.pop();
            int val2 = st.top(); st.pop();
            
            switch(c) {
                case '+': st.push(val2 + val1); break;
                case '-': st.push(val2 - val1); break;
                case '*': st.push(val2 * val1); break;
                case '/': st.push(val2 / val1); break;
            }
        }
    }
    return st.top();
}

2. Implementation of LRU Cache


class LRUCache {
private:
    list> cache; // key, value pairs
    unordered_map>::iterator> map;
    int capacity;
    
public:
    LRUCache(int cap) : capacity(cap) {}
    
    int get(int key) {
        if(map.find(key) == map.end())
            return -1;
            
        cache.splice(cache.begin(), cache, map[key]);
        return map[key]->second;
    }
    
    void put(int key, int value) {
        if(map.find(key) != map.end()) {
            cache.erase(map[key]);
        }
        else if(cache.size() >= capacity) {
            map.erase(cache.back().first);
            cache.pop_back();
        }
        
        cache.push_front({key, value});
        map[key] = cache.begin();
    }
};

3. Task Scheduling with Priority Queue


vector scheduleTasks(vector>& tasks) {
    priority_queue> pq;
    vector result;
    
    // Push tasks with their priorities
    for(auto task : tasks) {
        pq.push({task.second, task.first});
    }
    
    // Execute highest priority tasks first
    while(!pq.empty()) {
        result.push_back(pq.top().second);
        pq.pop();
    }
    
    return result;
}

Best Practices and Common Pitfalls

Best Practices

Always check for empty stack/queue before performing operations
Consider using STL containers for production code unless there's a specific reason not to
Use appropriate container type based on requirements (stack vs priority_queue)
Handle edge cases in implementations (overflow, underflow)
Consider thread safety when implementing custom containers

Common Pitfalls

Forgetting to check for empty container before pop/top operations
Not handling memory deallocation in custom implementations
Incorrect implementation of circular queue boundary conditions
Inefficient implementation causing unnecessary copying of elements
Not considering the space complexity in applications

Practice Problems

Easy Level

Implement Stack using Arrays
Valid Parentheses
Queue using two Stacks
Implement Stack using Queues

Medium Level

Next Greater Element
Min Stack with O(1) operations
Circular Queue Implementation
Design a Stack with Increment Operation

Hard Level

Largest Rectangle in Histogram
Sliding Window Maximum
Basic Calculator
Design a File System

#4 - Stacks and Queues - Data Structures and Algorithms using C++ | Akash Vishwakarma

Comments