Stack and Queue are two of the most important linear data structures used in programming and technical interviews.
A Stack follows the Last In First Out (LIFO) principle, where the last inserted element is removed first. A Queue follows the First In First Out (FIFO) principle, where the first inserted element is removed first.
Interviewers frequently ask Stack and Queue questions because they test problem-solving skills, understanding of data structures, and knowledge of real-world applications.
This article focuses on discussing Stack and Queue interview questions.

Table of Contents

---

 

Implement Stack Using Array

Create a stack using an array and perform the following operations:

1. Push
2. Pop
3. Peek
4. Display

// C++ program to implement stack using array
#include iostream
using namespace std;

class Stack 
{
    int arr[100];
    int top;

public:
    Stack() 
    {
        top = -1;
    }

    void push(int value) 
    {
        if(top == 99) 
        {
            cout  "Stack Overflow\n";
            return;
        }
        arr[++top] = value;
    }

    void pop() 
    {
        if(top == -1) 
        {
            cout  "Stack Underflow\n";
            return;
        }
        top--;
    }

    void peek() 
    {
        if(top == -1) 
        {
            cout  "Stack Empty\n";
            return;
        }
        cout  "Top Element: "  arr[top]  endl;
    }

    void display() 
    {
        for(int i = top; i = 0; i--)
            cout  arr[i]  " ";
        cout  endl;
    }
};

int main()
{
    Stack s;

    s.push(10);
    s.push(20);
    s.push(30);

    s.display();
    s.pop();
    s.display();
    s.peek();
    return 0;
}

Output:

30 20 10
20 10
Top Element: 20

Explanation:
The stack stores elements in an array.

1. Push inserts an element at the top.
2. Pop removes the top element.
3. Peek returns the current top element.
4. Display prints all elements from top to bottom.

Since Stack follows LIFO, 30 is removed first when pop is called.
Time Complexity:

1. Push: O(1)
2. Pop: O(1)
3. Peek: O(1)
4. Display: O(1)

Reverse a String Using Stack

Reverse a given string using Stack operations.
Example:

Input:
Hello
Output:
olleH

// C++ program to reverse a string using stack
#include iostream
#include stack
using namespace std;

int main() {

    string str = "Hello";

    stackchar st;

    for(char ch : str)
        st.push(ch);

    while(!st.empty()) {
        cout  st.top();
        st.pop();
    }

    return 0;
}

Output:

olleH

Explanation
Each character is pushed into the stack. Since Stack follows LIFO:

1. Push: H e l l o
2. Pop : o l l e H

The popped characters form the reversed string.
Time Complexity:

1. Push all characters: O(n)
2. Pop all characters: O(n)

Check Balanced Parentheses

Determine whether an expression contains balanced brackets.
Example:

{[()]}
Output:
Balanced

c

// C++ program to check balanced parantheses
#include iostream
#include stack
using namespace std;

bool isBalanced(string exp) {

    stackchar st;

    for(char ch : exp) {

        if(ch == '(' || ch == '{' || ch == '[')
            st.push(ch);

        else {

            if(st.empty())
                return false;

            if((ch == ')' && st.top() != '(') ||
               (ch == '}' && st.top() != '{') ||
               (ch == ']' && st.top() != '['))
                return false;

            st.pop();
        }
    }

    return st.empty();
}

int main() {

    string exp = "{[()]}";

    if(isBalanced(exp))
        cout  "Balanced";
    else
        cout  "Not Balanced";

    return 0;
}

Output:

Balanced

Explanation:
Opening brackets are pushed into the stack. Whenever a closing bracket appears:

1. Compare it with the stack top.
2. If they match, remove the opening bracket.
3. Otherwise the expression is invalid.

At the end, the stack must be empty for a balanced expression.
Time Complexity:

1. Traversal: O(n)
2. Stack Operations: O(1)

Implement Queue Using Array

Implement a queue using an array and perform:

1. Enqueue
2. Dequeue
3. Display

// C++ program to implement queue using array
#include iostream
using namespace std;

class Queue {

    int arr[100];
    int front, rear;

public:

    Queue() {
        front = rear = -1;
    }

    void enqueue(int value) {

        if(rear == 99) {
            cout  "Queue Full\n";
            return;
        }

        if(front == -1)
            front = 0;

        arr[++rear] = value;
    }

    void dequeue() {

        if(front == -1 || front  rear) {
            cout  "Queue Empty\n";
            return;
        }

        front++;
    }

    void display() {

        for(int i = front; i = rear; i++)
            cout  arr[i]  " ";

        cout  endl;
    }
};

int main() {

    Queue q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    q.display();

    q.dequeue();

    q.display();

    return 0;
}

Output:
10 20 30
20 30
Explanation
The queue follows FIFO. The order of operations:

1. Enqueue: 10 20 30
2. Dequeue: 10 removed
3. Remaining: 20 30

The first inserted element is removed first.
Time Complexity:

1. Enqueue: O(1)
2. Dequeue: O(1)
3. Display: O(n)

Generate Binary Numbers from 1 to N Using Queue

Generate binary representations of numbers from 1 to N using a Queue.
Example:

Input:
N = 5
Output:
1
10
11
100
101

 

// C++ program to generate binary numbers
// from 1 to N using queue
#include iostream
#include queue
using namespace std;

void generateBinary(int n) 
{
    queuestring q;
    q.push("1");

    while(n--) 
    {
        string current = q.front();
        q.pop();
        cout  current  endl;
        q.push(current + "0");
        q.push(current + "1");
    }
}

int main() 
{
    generateBinary(5);
    return 0;
}

Output:

1
10
11
100
101

Explanation:
The queue stores binary numbers. The process is as follows:

1. Start → 1
2. Generate: 1, 10, 11, 100, 101

Each removed element generates two new binary numbers:

1. Current + “0”
2. Current + “1”

This uses FIFO ordering to generate binary numbers sequentially.
Time Complexity: O(n)

Next Greater Element

Given an array, find the next greater element for every element.
Example:

Input:
4 5 2 25
Output:
4 - 5
5 - 25
2 - 25
25 - -1

// C++ program to find next greater element
#include iostream
#include stack
using namespace std;

void nextGreater(int arr[], int n) 
{
    stackint st;
    st.push(arr[0]);

    for(int i = 1; i  n; i++) 
    {
        while(!st.empty() && st.top()  arr[i]) 
        {
            cout  st.top()  " - "  arr[i]  endl;
            st.pop();
        }
        st.push(arr[i]);
    }

    while(!st.empty()) {
        cout  st.top()  " - -1"  endl;
        st.pop();
    }
}

int main() {

    int arr[] = {4,5,2,25};
    int n = 4;

    nextGreater(arr,n);

    return 0;
}

Output:

4 - 5
2 - 25
5 - 25
25 - -1

Explanation:
A stack is used to keep track of elements whose next greater element has not been found. Whenever a larger element appears:

1. Remove smaller elements from the stack.
2. Assign the current element as their next greater element.

This avoids checking every element repeatedly.
Time Complexity:

1. Traversal: O(n)
2. Stack Operations: O(n)

Evaluate Postfix Expression

Evaluate a postfix expression using a stack.
Example:

Input:
231*+9-
Output:
-4

// C++ program to evaluate a postfix expression
#include iostream
#include stack
using namespace std;

int main() {

    string exp = "231*+9-";

    stackint st;

    for(char ch : exp) {

        if(isdigit(ch)) {
            st.push(ch - '0');
        }
        else {

            int val1 = st.top();
            st.pop();

            int val2 = st.top();
            st.pop();

            switch(ch) {
                case '+':
                    st.push(val2 + val1);
                    break;
                case '-':
                    st.push(val2 - val1);
                    break;
                case '*':
                    st.push(val2 * val1);
                    break;
                case '/':
                    st.push(val2 / val1);
                    break;
            }
        }
    }

    cout  st.top();

    return 0;
}

Output:

-4

Explanation:
Postfix expressions eliminate the need for brackets.

Steps:
2 3 1 * + 9 -
3 × 1 = 3
2 + 3 = 5
5 - 9 = -4

The stack stores operands and performs operations whenever an operator is encountered.
Time Complexity: O(n)

Implement Stack Using Two Queues

Implement stack operations using two queues in C++.

// C++ program to implement stack 
// using two queues
#include iostream
#include queue
using namespace std;

class Stack {

    queueint q1, q2;

public:

    void push(int x) {

        q2.push(x);

        while(!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }

        swap(q1,q2);
    }

    void pop() {

        if(!q1.empty())
            q1.pop();
    }

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

int main() {

    Stack s;

    s.push(10);
    s.push(20);
    s.push(30);

    cout  s.top()  endl;

    s.pop();

    cout  s.top();

    return 0;
}

Output:

30
20

Explanation:
Queues naturally follow FIFO, while stacks require LIFO. To achieve stack behavior:

1. Insert the new element into the second queue.
2. Move all existing elements behind it.
3. Swap the queues.

The newest element always remains at the front.
Time Complexity:

1. Push: O(n)
2. Top: O(1)
3. Pop: O(1)

Circular Queue Implementation

Implement a Circular Queue using an array. Unlike a normal queue, the last position connects back to the first position, improving memory utilization.

// C++ program to implement circular queue
#include iostream
using namespace std;

class CircularQueue {

    int arr[5];
    int front, rear;

public:

    CircularQueue() {
        front = rear = -1;
    }

    void enqueue(int value) {

        if((rear + 1) % 5 == front) {
            cout  "Queue Full\n";
            return;
        }

        if(front == -1)
            front = 0;

        rear = (rear + 1) % 5;
        arr[rear] = value;
    }

    void dequeue() {

        if(front == -1) {
            cout  "Queue Empty\n";
            return;
        }

        if(front == rear)
            front = rear = -1;
        else
            front = (front + 1) % 5;
    }

    void display() {

        int i = front;

        while(true) {

            cout  arr[i]  " ";

            if(i == rear)
                break;

            i = (i + 1) % 5;
        }

        cout  endl;
    }
};

int main() {

    CircularQueue q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    q.display();

    q.dequeue();

    q.display();

    return 0;
}

Output:

10 20 30
20 30

Explanation:
A circular queue reuses empty positions created after dequeue operations. The modulo operator (%) helps the rear and front pointers wrap around the array. This prevents wastage of space.
Time Complexity:

1. Enqueue: O(1)
2. Dequeue: O(1)
3. Display: O(n)

First Non-Repeating Character in a Stream

Given a stream of characters, print the first non-repeating character after processing each character.
Example:

Input:
aabc
Output:
a -1 b b

// C++ program to find first non-repeating
// in a stream
#include iostream
#include queue
using namespace std;

int main() {

    string str = "aabc";

    queuechar q;
    int freq[26] = {0};

    for(char ch : str) {

        freq[ch - 'a']++;

        q.push(ch);

        while(!q.empty() &&
              freq[q.front() - 'a']  1) {
            q.pop();
        }

        if(q.empty())
            cout  "-1 ";
        else
            cout  q.front()  " ";
    }

    return 0;
}

Output:

a -1 b b

Explanation:
A queue maintains characters that may still be non-repeating. For each character:

1. Increase frequency.
2. Add it to the queue.
3. Remove characters whose frequency becomes greater than one.
4. The front of the queue represents the first non-repeating character.

Time Complexity: O(n)

Conclusion

Stack and Queue questions are among the most frequently asked coding interview problems. These questions build a strong foundation for more advanced interview problems involving monotonic stacks, circular queues, sliding windows, expression evaluation, and graph traversal.
 

Frequently Asked Questions

1. Which Stack question is most frequently asked in interviews?

Balanced Parentheses and Next Greater Element are among the most commonly asked Stack interview questions.

2. Which Queue problem is frequently asked in coding rounds?

First Non-Repeating Character in a Stream and Circular Queue Implementation are very popular.

3. Can Stack be implemented using Queue?

Yes. A stack can be implemented using one or two queues.

4. Can Queue be implemented using Stack?

Yes. A queue can be implemented using two stacks.

5. Which STL containers are used for Stack and Queue in C++?

The C++ Standard Template Library provides:
stackint st;
queueint q;