Practice › Stack & Queue
Implement Queue using Stacks
Easy · Stack & Queue · Asked at Amazon, Microsoft, Bloomberg, TCS, Infosys
Build a FIFO queue using only two stacks and process the operations:
push x— add x to the backpop— remove the front element and print it (print-1if the queue is empty)peek— print the front element (-1if empty)empty— printtrueorfalse
Input
First line: q. Next q lines: one operation each.
Output
One line for every pop, peek and empty.
Constraints
- 1 ≤ q ≤ 10^5
- 0 ≤ x ≤ 10^9
Push onto an "in" stack. To pop/peek, if the "out" stack is empty, move everything from "in" to "out" — every element moves at most once, so each operation is amortised O(1).
Example 1
Input
5 push 1 push 2 peek pop empty
Output
1 1 false
Example 2
Input
3 pop empty peek
Output
-1 true -1
Hints
- A stack reverses order. Reversing twice restores it.
- Push into an "in" stack. For pop/peek, if the "out" stack is empty, pour all of "in" into "out"; the top of "out" is the front of the queue.
Approach
Two stacks. push goes to in. pop/peek use out; only when out is empty do we move every element from in to out, which reverses them into queue order. Each element is moved at most once, so any sequence of q operations costs O(q). The queue is empty when both stacks are empty.
Complexity: Amortised O(1) per operation · O(q) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
stack<long long> in, out;
void shift() {
if (out.empty())
while (!in.empty()) out.push(in.top()), in.pop();
}
int main() {
int q;
cin >> q;
string op;
while (q--) {
cin >> op;
if (op == "push") {
long long x;
cin >> x;
in.push(x);
} else if (op == "empty") {
cout << (in.empty() && out.empty() ? "true" : "false") << "\n";
} else {
shift();
if (out.empty()) cout << -1 << "\n";
else {
cout << out.top() << "\n";
if (op == "pop") out.pop();
}
}
}
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
q = int(data[0])
i = 1
inp, outp, res = [], [], []
for _ in range(q):
op = data[i]
i += 1
if op == "push":
inp.append(int(data[i]))
i += 1
elif op == "empty":
res.append("true" if not inp and not outp else "false")
else:
if not outp:
while inp:
outp.append(inp.pop())
if not outp:
res.append(-1)
else:
res.append(outp[-1])
if op == "pop":
outp.pop()
print("\n".join(map(str, res)))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
Deque<Long> in = new ArrayDeque<>(), out = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
String op = sc.next();
if (op.equals("push")) in.push(sc.nextLong());
else if (op.equals("empty")) sb.append(in.isEmpty() && out.isEmpty() ? "true" : "false").append('\n');
else {
if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
if (out.isEmpty()) sb.append(-1).append('\n');
else {
sb.append(out.peek()).append('\n');
if (op.equals("pop")) out.pop();
}
}
}
System.out.print(sb);
}
}Solve Implement Queue using Stacks online · All practice problems