stackqueuedata-structuresamazon-interview-questionsmicrosoft-interview-questionsfacebook-interview-questions

**Difficulty:** Easy, **Asked-in:** Facebook, Microsoft, Amazon, Adobe, Goldman Sachs, Morgan Stanley, Walmart, Flipkart

**Key takeaway:** An excellent problem to visualize the use case of stack and queue operations in problem-solving.

Write a program to implement a queue using stacks. The implemented queue should support standard operations like enqueue(x), dequeue(), and front().

- void enqueue(int x): insert element x to the back of the queue.
- int dequeue(): remove the element on the front of the queue and returns it.
- int front(): return the element on the front of the queue.

**Problem Notes**

- Stack is a last-in-first-out (
**LIFO)**data structure, in which elements are added and removed from the same end, called top. In contrast, the queue is a first-in-first-out (**FIFO)**data structure, in which elements are added only from one side (back) and removed from the other (front). - We must use
**only**standard stack operations like push(x), pop(), top(), size(), and isEmpty().

- Using two stacks: dequeue O(1) and enqueue O(n)
- Using two stacks: enqueue O(1) and dequeue O(1) amortized

A queue is first-in-first-out, but a stack is last-in-first-out. If we push and pop elements to the stack, the output will be in reverse order of a queue. Let's understand it via an example!

- Suppose we first push 1, 2, 3, 4, and 5 into the stack, and pop it back. So popped output will be 5, 4, 3, 2, and 1. Here 5 is the newly entered element that will come first and 1 is the oldest entered element that will come last.
- Suppose we first enqueue 1, 2, 3, 4, and 5 into the queue, and dequeue all the elements. So the dequeued output will be 1, 2, 3, 4, and 5. Here 5 is the newly entered element that will come last and 1 is the oldest entered element that will come first.

So one idea would be to invert the order of elements in the stack to get the output in the order of the queue. For this, we can keep the new element to the bottom of the stack, or in other words, we keep the oldest element to the top of the stack. Let's visualize!

Based on the above strategy, suppose we push 1, 2, 3, 4, and 5 into the stack then the newly arrived element will always go to the bottom of the stack. So the final order of the elements in the stack will be 5, 4, 3, 2, and 1, where 5 is at the bottom of the stack and 1 is at the top of the stack. So if we pop elements then they will come out in queue order: 1, 2, 3, 4, and 5.

So here is the step by step solution idea:

**Dequeue operation idea**

To perform the dequeue operation, we simply remove the top of the stack which is the oldest element in the stack.

**Enqueue operation idea**

- For the enqueue operation, we need to insert the new element to the bottom of the stack. For this, we first remove the existing elements and store them somewhere else by maintaining the order. So the idea would be simple: we need to use another auxiliary stack!
- So we first transfer the existing stack element to the auxiliary stack and insert the newly arrived element on the top of the auxiliary stack.
- We again transfer all the elements of the auxiliary stack to the main stack. After this process, the newest element will go to the bottom of the main stack, and it will come last during the dequeue operation.

Our queue model will consist of two stacks: one stack for the dequeue operation and two stacks for the enqueue operation. Suppose we are using **mainStack** and **tempStack** to simulate the queue process. Note: here we are assuming that the size of stacks is unlimited.

**Implementation of the dequeue operation**

- If mainStack is empty then we through an error "Queue is Empty!" and return.
- We pop the top element from mainStack and return it as an output.
- We also decrement the queue size by 1.

```
int deQueue()
{
if (mainStack.empty())
{
print("Queue is Empty!")
return INT_MIN
}
int stackTop = mainStack.pop()
queueSize = queueSize - 1
return stackTop
}
```

- We are doing a constant number of stack operations. Time complexity = O(1)
- We are not using extra space. Space complexity = O(1)

**Implementation of the enqueue operation**

- If mainStack is not empty, we pop each element from the mainStack and push it to the tempStack.
- Now, we push x onto the top of the tempStack.
- Finally, we push every element back to the mainStack from the tempStack.
- During this process, we also increment the value of queue size by 1.

```
void enQueue(int x)
{
int stackTop
while (!mainStack.empty())
{
stackTop = mainStack.pop()
tempStack.push(stackTop)
}
tempStack.push(x)
queueSize = queueSize + 1
while (!tempStack.empty())
{
stackTop = tempStack.pop()
mainStack.push(stackTop)
}
}
```

- Each element except the newly arrived element is pushed and popped twice and the last inserted element is popped and pushed once. The total number of stack operations = 4n + 2 operations, where n is the queue size. Time complexity = O(n)
- We are not using O(n) extra space for tempStack. Space complexity = O(n)

**Note:** It's an exercise for you to design an effcient algorithm for the front() operation.

**Class-based pseudocode implementation**

```
class QueueUsingStack
{
int queueSize
stack mainStack, tempStack
public:
QueueUsingStack()
{
queueSize = 0
}
void enQueue(int x)
{
int stackTop
while (!mainStack.empty())
{
stackTop = mainStack.pop()
tempStack.push(stackTop)
}
tempStack.push(x)
queueSize = queueSize + 1
while (!tempStack.empty())
{
stackTop = tempStack.pop()
mainStack.push(stackTop)
}
}
int deQueue()
{
if (mainStack.empty())
{
print("Queue is Empty!")
return INT_MIN
}
int stackTop = mainStack.pop()
queueSize = queueSize - 1
return stackTop
}
}
```

Another implementation idea would be thinking in the reverse way of the above approach: we keep the newly arrived element at the top of the stack and the oldest entered element at the bottom of the stack.

**Enqueue operation idea**

For the enqueue operation, we add an element to the top of the mainStack.

**Dequeue operation idea**

- For the dequeue operation, we need to remove the bottom element of the mainStack, which will be the oldest element.
- When tempStack is empty: we pop all elements from mainStack and push them onto the tempStack, which helps us to store the elements of mainStack in reversed order. Now, the bottom element of mainStack will be positioned on top of tempStack, and we perform the pop operation on tempStack to perform the dequeue operation.
- When tempStack is not empty: there is no need to transfer the data and we just pop the top element of the tempStack. Why? Think! When teampStack is empty after the sequence of dequeue operations, we follow the same procedure: transfer data from mainStack to tempStack again.

**Implementation of the enqueue operation**

- We simply push the newly arrived element x to mainStack.
- We also increment the value of queue size by 1.

```
void enQueue(int x)
{
mainStack.push(x)
queueSize = queueSize + 1
}
```

- We are doing a constant number of stack operations. Time complexity = O(1)
- We are not using extra space. Space complexity = O(1)

**Implementation of the dequeue operation**

- If both stacks are empty then we through an error and return.
- If mainStack is not empty and tempStack is empty, we pop each element from mainStack and push it to the tempStack. Now we pop the element from tempStack and return it.
- If both stacks are not empty, then we just pop the element from tempStack and return it.
- We also decrement the value of queue size by 1.

```
int deQueue()
{
int stackTop
if (mainStack.empty() && tempStack.empty())
{
print("Queue is empty!")
return
}
if (tempStack.empty())
{
while (!mainStack.empty())
{
stackTop = mainStack.pop()
tempStack.push(stackTop)
}
}
stackTop = tempStack.pop()
queueSize = queueSize - 1
return stackTop
}
```

**Time and space complexity of dequeue operation**

In the worst-case scenario, when tempStack is empty, the algorithm pops n elements from mainStack and pushes n elements to tempStack, where n is the queue size. This gives 2n operations, which is O(n). So the worst-case time complexity of the pop operation = O(n).

The best-case scenario would occur when tempStack is not empty, and we need to perform only one pop operation. So the best-case time complexity of the pop operation = O(1).

But if we observe closely, the average case or amortized performance of the pop operation is O(1). How? Let's think!

**Amortized Analysis**

The amortized analysis gives the average performance of each operation in the worst case. In other words, when the chances of worst-case are very low compared to the best case, a traditional worst-case analysis will not give a clear picture of the time complexity. Sometimes average-case performance improves by a lot if there is a significant gap in the worst case and best case performance. Think!

However, in a sequence of pop operations, the worst case does not often occur: some pop operations will be O(1), and some will be O(n). For example, this is just like the situation of a dynamic array where logn number of insertions takes a linear time, and other insertions take a constant time.

In the above code, the number of times the pop operation is limited by the number of push operations before it. However, the pop operation could be costly only once per n times when tempStack is empty, and there is a need for data transfer between mainStack and tempStack.

Let's suppose an ideal picture: there is n number of enqueue operations followed by n number of dequeue operations. So total number of stack operations = number of stack operations for n enqueue operations + number of stack operations for first dequeue operation + number of stack operations for remaining n - 1 dequeue operation = n + 2n + n -1 = 4n - 1 ~ 4n

For 2n queue operations, code will perform 4n stack operations. So for each queue operation, on average, code will perform two stack operations i.e. O(1) average time per operation. So average or amortized case time complexity of the pop operation = O(1).

**Note:** It's an exercise for you to design an effcient algorithm for the front() operation.

**Class-based pseudocode implementation**

```
Class QueueUsingStack
{
int queueSize
stack mainStack, tempStack
public:
QueueUsingStack()
{
queueSize = 0
}
void enQueue(int x)
{
mainStack.push(x)
queueSize = queueSize + 1
}
int deQueue()
{
int stackTop
if (mainStack.empty() && tempStack.empty())
{
print("Queue is empty!")
return
}
if (tempStack.empty())
{
while (!mainStack.empty())
{
stackTop = mainStack.pop()
tempStack.push(stackTop)
}
}
stackTop = tempStack.pop()
queueSize = queueSize - 1
return stackTop
}
}
```

- How do we implement a queue using recursion and one additional stack?
- In the second approach, why there is no need to transfer the data from the mainStack to the tempStack.
- How efficiency of the above approaches depends on the frequency of enqueue and dequeue operations? Which approach should be followed if enqueue operation is very high in comparison to the dequeue operation?
- Can we think of solving this problem using some other strategies?
- Based on the complexity of enqueue or dequeue operations, what type of queue implementation would be perfect for the above implementations? Array implementation or linked list implementation?
- How do we implement front() and isEmpty() operations in all the above approaches? Can we design a strategy to get the front element in O(1) time complexity?

- Implement Stack using Queues
- Reverse a queue using another queue
- Check if the two given stacks are the same
- Min-stack problem
- Implement Stack and Queue using Deque
- Implement stack using a priority queue
- Sort a stack using a temporary stack
- Reverse a Stack using another Stack
- Find maximum in a stack

**Enjoy learning, Enjoy Algorithms**

Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.