Implement Queue using Stacks

Implement Queue using Stacks is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

- void push(int x) Pushes element x to the back of the queue.

- int pop() Removes the element from the front of the queue and returns it.

- int peek() Returns the element at the front of the queue.

- boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

- You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

- Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Example 1:

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

Constraints:

- 1 <= x <= 9

- At most 100 calls will be made to push, pop, peek, and empty.

- All the calls to pop and peek are valid.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Topics and companies

Topics: Stack, Design, Queue.

Reported in interviews at Amazon, Microsoft, Apple, Facebook, Citrix, Morgan Stanley.

How to practise Implement Queue using Stacks on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in Amortized O(1) per operation. Each element is pushed and popped at most once from each stack, so n operations take O(n) total time. time and O(n), where n is the number of elements in the queue. Both stacks together store all elements. space.

Open Implement Queue using Stacks in the code editor, or read the Implement Queue using Stacks editorial for a worked solution with its approach and complexity analysis.

Where Implement Queue using Stacks sits in the DSA pattern sheet

Problems related to Implement Queue using Stacks

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

Preparing this workspace.