Implement a Queue Using Stacks

99.2k
0

Design a queue data structure using stack operations only. A queue follows FIFO order, meaning First In First Out, while a stack follows LIFO order, meaning Last In First Out.

The queue must support adding a value at the back, removing the front value, reading the front value, and checking whether the queue is empty. Stack operations available for the design are push to top, pop from top, read top, size check, and empty check. If pop or peek is performed on an empty queue, -1 must be returned.

Example 1

Input: Operations = push(10), push(20), peek(), push(30), pop(), pop(), peek(), pop(), empty()
Output: 10, 10, 20, 30, 30, true
Explanation: Values 10 and 20 enter before the first front lookup. Value 30 enters after peek(), but values 10 and 20 still leave first. Value 30 becomes the front only after both older values leave.

Example 2

Input: Operations = push(10), pop(), empty()
Output: 10, true
Explanation: The only queued value is removed, so the queue becomes empty.

Brute Force Approach

A queue removes the oldest value first, while a stack removes the newest value first. Keeping the queue front at the top of mainStack solves the difference.

During push(), all existing values move to helperStack. The new value enters mainStack, and all older values move back. The oldest value then remains at the top.

This approach makes pop() and peek() easy, but push() takes O(N) time.

Operation Flow

push(value):

  • Move all values from mainStack to helperStack.

  • Push the new value into mainStack.

  • Move all values back to mainStack.

pop():

  • Return -1 when mainStack is empty.

  • Remove and return the top value.

peek():

  • Return -1 when mainStack is empty.

  • Return the top value without removal.

empty():

  • Return whether mainStack is empty.

Algorithm

  • Two stacks named mainStack and helperStack are maintained so the front of the queue stays on top of mainStack.

  • During push, all values from mainStack are moved to helperStack so the new value can be placed below older values.

  • The new value is pushed into mainStack because the value belongs at the back of the queue.

  • All values from helperStack are moved back to mainStack so the oldest value returns to the top.

  • During pop, an empty mainStack returns -1 so invalid removal is handled safely.

  • During peek, an empty mainStack returns -1 so invalid front lookup is handled safely.

  • The empty operation checks only mainStack because all queue values are restored into mainStack after every push.

Dry Run

Queue using stack Approach 1

Queue using stack Approach 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
stack<int> mainStack;
stack<int> helperStack;
public:
// Adds a value at the back of the queue.
void push(int x) {
// Existing values are moved away first.
// The new value must sit below older values.
while (!mainStack.empty()) {
helperStack.push(mainStack.top());
mainStack.pop();
}
mainStack.push(x);
// Older values are restored above the new value.
// The queue front returns to the stack top.
while (!helperStack.empty()) {
mainStack.push(helperStack.top());
helperStack.pop();
}
}
// Removes and returns the front value.
int pop() {
// An empty main stack means no queue value exists.
if (mainStack.empty()) {
return -1;
}
int frontValue = mainStack.top();
mainStack.pop();
return frontValue;
}
// Returns the front value without removal.
int peek() {
// An empty main stack means no front value exists.
if (mainStack.empty()) {
return -1;
}
return mainStack.top();
}
// Checks whether the queue has no values.
bool empty() {
return mainStack.empty();
}
};
// Driver code
int main() {
Solution obj;
obj.push(1);
obj.push(2);
cout << obj.peek() << " ";
cout << obj.pop() << " ";
cout << boolalpha << obj.empty();
return 0;
}

Complexity Analysis

Time Complexity: O(N) for push(), because all existing values move to helperStack and then back to mainStack. pop(), peek(), and empty() take O(1) time because the queue front always remains at the top of mainStack.

Space Complexity: O(N), mainStack and helperStack can each require space for up to N values. Counting both stack capacities gives O(N) + O(N) = O(2*N). Removing the constant factor simplifies the total to O(N).

Optimal Approach

Moving all values during every push() is unnecessary. New values stay in inputStack until peek() or pop() needs the queue front.This method uses lazy transfer, meaning values move from inputStack to outputStack only when outputStack becomes empty.

The transfer reverses the order and places the oldest value on top. Each value moves only once, so the average time per operation is O(1).

Operation Flow

push(value):

  • Push the value into inputStack.

pop():

  • Perform lazy transfer when outputStack is empty.

  • Return -1 when both stacks are empty.

  • Remove and return the top of outputStack.

peek():

  • Perform lazy transfer when outputStack is empty.

  • Return -1 when both stacks are empty.

  • Return the top of outputStack without removal.

empty():

  • Return true only when both stacks are empty.

Algorithm

  • Two stacks named inputStack and outputStack are maintained so new values can wait separately from values already ready for removal.

  • During push, the new value is pushed into inputStack because no queue order is needed until a front operation occurs.

  • Before pop or peek, outputStack is checked because an available top value already represents the queue front and needs no transfer.

  • During pop or peek, an empty outputStack triggers a full transfer from inputStack so stack reversal brings the oldest waiting value to the top.

  • During pop, an empty state after transfer returns -1 so invalid removal is handled safely.

  • During peek, an empty state after transfer returns -1 so invalid front lookup is handled safely.

  • The empty operation checks both stacks because values may wait in either stack.

Dry Run

queue-using-stacks-lazy-transfer-push-after-peek

queue-using-stacks-lazy-transfer-push-after-peek

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
stack<int> inputStack;
stack<int> outputStack;
// Moves values only without an outgoing front.
void shiftStacks() {
// Existing outgoing values already preserve queue order.
if (!outputStack.empty()) {
return;
}
// Incoming values are reversed.
// The oldest value reaches the outgoing top.
while (!inputStack.empty()) {
outputStack.push(inputStack.top());
inputStack.pop();
}
}
public:
// Adds a value at the back of the queue.
void push(int x) {
inputStack.push(x);
}
// Removes and returns the front value.
int pop() {
shiftStacks();
// Empty output after shifting means no value exists.
if (outputStack.empty()) {
return -1;
}
int frontValue = outputStack.top();
outputStack.pop();
return frontValue;
}
// Returns the front value without removal.
int peek() {
shiftStacks();
// Empty output after shifting means no front exists.
if (outputStack.empty()) {
return -1;
}
return outputStack.top();
}
// Checks whether the queue has no values.
bool empty() {
return inputStack.empty() && outputStack.empty();
}
};
// Driver code
int main() {
Solution obj;
obj.push(10);
obj.push(20);
cout << obj.peek() << " ";
obj.push(30);
cout << obj.pop() << " ";
cout << obj.pop() << " ";
cout << obj.peek() << " ";
cout << obj.pop() << " ";
cout << boolalpha << obj.empty();
return 0;
}

Complexity Analysis

Time Complexity: O(N), one pop or peek can take O(N) in the worst case because an empty outputStack can require N pops from inputStack and N pushes into outputStack. The transfer cost is O(N) + O(N) = O(2*N). Removing the constant factor simplifies the transfer to O(N). A pop or peek with values already in outputStack takes O(1). Across a sequence of operations, every value transfers at most once, so total transfer work for N values is O(N) and the average cost per operation is O(1). Both push and empty always take O(1).

Space Complexity: O(N), inputStack and outputStack can each require space for up to N values. Counting both stack capacities gives O(N) + O(N) = O(2*N). Removing the constant factor simplifies the total to O(N).

Interview follow-up Questions

One stack alone cannot expose the oldest value while preserving all newer values with only top-based stack operations. A second stack or the recursion call stack is needed for reversal.

Stack

Read Similar Blogs

Stack

Sum of Subarray Ranges

Given an integer array nums , define the range of a non-empty contiguous subarray as the maximum element minus the minimum element. Return the sum of the ranges of all non-empty contiguous subarray...

91.4k
Stack

Introduction to Stack

Imagine a stack of plates in a kitchen. Whenever you add a new plate, you place it on the top. When you need a plate, you also take it from the top. You never remove a plate from the middle because...

69.7k
Two PointerStackString

Reverse Every Word in a String

Given a string s , reverse every word individually. The spaces should remain in the same positions, and the order of words should not change. A word is a continuous group of non-space...

83.7k
Comments0