Implement Queue using Stacks

Introduction

The FIFO (First In First Out) principle, which dictates that insertion takes place from the back and deletion takes place from the front, is followed by the queue, a linear data structure. A linear data structure called a stack implements the LIFO (Last In First Out) principle, which states that insertion and deletion must always start at the top of the stack.

Problem Statement

Here, you must use stacks to implement a first-in, first-out queue. All functions, including push, pop, and peek, ought to be supported by the queue.

Examples

Input

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

Output

[null, null, null, 1, 1, false]

Explanation

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Let's first clarify the fundamental distinction between Stack and Queue before moving on to the solution.

The data structure for the stack is Last in First Out. Only the top of the stack is used for push and pop operations (). Push, pop, and peek operations are supported.

First In First Out (Queue) is a data structure. Two endpoints of the queue are used for push and pop operations. Enqueue, Dequeue, and Peek operations are supported.

You can see that in order to implement the queue, we would need two stacks: one for the en queue operation and one for the de queue action.

Approach: Making enqueue operation costly

As was mentioned above, we are aware that the queue operates according to a FIFO order, meaning that the element that enters first exits first. As a result, we must come up with a method involving stacks that ensures the element being pushed stays at the top. As a result, we will apply the same to a second stack.

Algorithm

For enqueue

Initialize the S1 and S2 stacks.
Insert the element into S2 if S1 is empty.
Otherwise, move all of the components from S1 to S2.
Put the required component into S1 by pushing it there.
Return all of the components from S2 to S1.

For dequeue

Return -1 if stack S1 is bare.
Return the stack's top element if not.

C++ Code

struct Queue {
stack < int > s1, s2;

void enQueue(int x) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
s1.push(x);
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}
int deQueue() {
if (s1.empty()) {
cout << "Q is Empty";
exit(0);
}
int x = s1.top();
s1.pop();
return x;
}
};

write your code here: Coding Playground

Time Complexity: O(1) for pop, O(N) for enqueue operations

Space Complexity: O(N)