How to Design/Implement a Queue using Two Stacks?

A Queue implements First In First Out while a Stack is First In Last Out. It is possible to implement a queue using two stacks. When an item is to be inserted into the queue, we always push it to the first stack, and when we pop one element from the queue, we implement as popping it from another stack. For example,

Initial States:
Stack A: []
Stack B: []

Enqueue Numbers 1, 2, 3
Stack A: [1, 2, 3]
Stack B: []

Pop Two Elements – First
Stack A: []
Stack B: [3 2 1] — popping all elements from Stack A and pushing them to Stack B

Pop Two Elements – Then
Stack A: []
Stack B: [3] — 1 and 2 dequeued.

Push another Element:
Stack A: [4]
Stack B: [3]

Pop another Element:
Stack A: [4]
Stack B: [] — we have elements in Stack B, so just pop it.

C++ Implementation of Two-Stacks-Queue

The Two-Stacks-Queue in C++ can be implemented via the following (using a template for generic type):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

template <typename T>
class TwoStackQueue
{
public:
    TwoStackQueue() = default;
    void push(T a)
    {
        A.push(a);
    }
    T pop()
    {
        if (B.empty())
        {
            if (A.empty())
            {
                return (T)nullptr;
            }
            transfer();
        }
        T v = B.top();
        B.pop();
        return v;
    }
private:
    std::stack<T> A;
    std::stack<T> B;
 
    void transfer() // transfer all elements from Stack A to Stack B
    {
        while (!A.empty())
        {
            T v = A.top();
            A.pop();
            B.push(v);
        }
    }
};

template <typename T>
class TwoStackQueue
{
public:
	TwoStackQueue() = default;
	void push(T a)
	{
		A.push(a);
	}
	T pop()
	{
		if (B.empty())
		{
			if (A.empty())
			{
				return (T)nullptr;
			}
			transfer();
		}
		T v = B.top();
		B.pop();
		return v;
	}
private:
	std::stack<T> A;
	std::stack<T> B;

	void transfer() // transfer all elements from Stack A to Stack B
	{
		while (!A.empty())
		{
			T v = A.top();
			A.pop();
			B.push(v);
		}
	}
};

Example usages:

1
2
3
4
5
6
7
8
9
10
11

TwoStackQueue<int> Q;
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
std::cout << Q.pop() << std::endl;
std::cout << Q.pop() << std::endl;
Q.push(5);
Q.push(6);
std::cout << Q.pop() << std::endl;
std::cout << Q.pop() << std::endl;

TwoStackQueue<int> Q;
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
std::cout << Q.pop() << std::endl;
std::cout << Q.pop() << std::endl;
Q.push(5);
Q.push(6);
std::cout << Q.pop() << std::endl;
std::cout << Q.pop() << std::endl;

The enqueue operation takes O(1) complexity and when popping elements from the queue, it takes O(1) if stack B has elements, otherwise it takes O(N) complexity to transfer elements from Stack A to Stack B.

first-in-last-out-stack

–EOF (The Ultimate Computing & Technology Blog) —