Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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:

Input

First line: q. Next q lines: one operation each.

Output

One line for every pop, peek and empty.

Constraints

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

  1. A stack reverses order. Reversing twice restores it.
  2. 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