In this post we will attempt to solve LeetCode 232 Implement Queue using Stacks. I believe this problem is similar to another I solved in this blog several years ago. If interested take a look at the post Queue implemented with Stacks.
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. 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. Constraints: o 1 <= x <= 9 o At most 100 calls will be made to push, pop, peek, and empty. o All the calls to pop and peek are valid.
The description states that we need to implement a class with a set of typical / common methods found in a Queue. If interested in this problem please visit the LeetCode site and get the current requirements. With time requirements may be slightly modified.
We will solve this problem using the Java programming language and the VSCode IDE on a Windows platform. The simplest way is to use the online IDE provided by LeetCode. I like to keep the solution close to a test scaffold and to implement it using a Test Driven Development approach. We will need to develop a simple test scaffold which IS NOT PART OF THE SOLUTION!
class MyQueue {
public MyQueue() {
}
public void push(int x) {
}
public int pop() {
}
public int peek() {
}
public boolean empty() {
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
The signature for the class in question contains a constructor and four additional methods. LeetCode illustrates how our implementation will be tested. Our test code should implement something similar.
MyQueue, push, push, peek, pop, empty 0, 1, 2, 0, 0, 0 main <<< cmds: [MyQueue, push, push, peek, pop, empty] main <<< params: [0, 1, 2, 0, 0, 0] main <<< null main <<< null main <<< null main <<< 1 main <<< 1 main <<< false MyQueue, push, push, pop, peek 0, 1, 2, 0, 0 main <<< cmds: [MyQueue, push, push, pop, peek] main <<< params: [0, 1, 2, 0, 0] main <<< null main <<< null main <<< null main <<< 1 main <<< 2
We have two test cases. Each test case has two input lines. The first provides a list of methods that need to be called and the second a list of arguments that need to be passed. Note that we use 0 to indicate that the method is not associated with an argument.
Our test scaffold seems to read the two input lines, and creates two arrays with the associated values. The contents of the arrays are displayed to make sure all is well so far.
As the different methods are being called the returned values are displayed. They seem to match the expected values.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read commands ****
String[] cmds = br.readLine().trim().split(", ");
// **** read parameters ****
int[] params = Arrays.stream(br.readLine().trim().split(", "))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< cmds: " + Arrays.toString(cmds));
System.out.println("main <<< params: " + Arrays.toString(params));
// **** initialization ****
MyQueue q = null;
// **** loop processing commands ****
for (int i = 0; i < cmds.length; i++) {
switch (cmds[i]) {
case "MyQueue":
q = new MyQueue();
System.out.println("main <<< null");
break;
case "push":
q.push(params[i]);
System.out.println("main <<< null");
break;
case "peek":
System.out.println("main <<< " + q.peek());
break;
case "pop":
System.out.println("main <<< " + q.pop());
break;
case "empty":
System.out.println("main <<< " + q.empty());
break;
}
}
}
Our test scaffold reads the two input lines, creates and populates two arrays. One holds the list of methods and the second the arguments that should be passed. The contents of the arrays are then displayed.
The variable `q` is then set to null. We are ready to loop through the commands.
As the different commands are encountered, our test code calls the associated methods implemented in the class of interest. The returning values, if any are displayed.
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 36.7 MB, less than 91.99% of Java online submissions.
*
* 21 / 21 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 36.7 MB
*/
class MyQueue {
// *** class members ****
public Stack<Integer> s1 = null;
public Stack<Integer> s2 = null;
// **** class methods ****
public MyQueue() {
this.s1 = new Stack<Integer>();
this.s2 = new Stack<Integer>();
}
public void push(int x) {
this.s1.push(x);
}
public int pop() {
// **** check if we can pop from s2 ****
if (!s2.isEmpty()) return s2.pop();
// **** check if we can move s1 to s2 and then return from s2 ****
while (!s1.isEmpty()) s2.push(s1.pop());
// **** ****
return s2.pop();
}
public int peek() {
if (s2.isEmpty()) {
// **** move values to the head of the queue ****
while (!s1.isEmpty()) s2.push(s1.pop());
// **** return the value of the head of the queue
// or 0 to indicate queue is empty ****
if (s2.isEmpty()) return 0;
else return s2.peek();
} return s2.peek();
}
public boolean empty() {
if (s2.isEmpty()) {
if (s1.isEmpty()) return true;
else return false;
} else {
return false;
}
}
}
This is our implementation of the MyQueue class. We start by defining two stacks as required.
The constructor initializes both stacks. `s1` will be the stack into which values are being pushed. When needed, our different methods will move the contents of `s1` to `s2`.
Not much to add to the implementation of `push`.
When `pop` is called, we need to retrieve the value from the head of the queue which at this time may be located in the `s2` stack or not. We check `s2` and if not empty we return the head element of the queue. If empty, we move all elements in `s1` to `s2`. We then return the top element from `s2` which happens to be the head of the queue.
The `peek` method checks if `s2` is empty. If so it attempts to move values from `s1` into `s2`. We then check if `s2` is empty and return 0 to indicate that our queue is empty, otherwise we return a copy of the top element in `s2` which happens to represent the head of the queue. Of course if initially `s2` is not empty, we return the value of the top element in `s2`.
The `empty` method checks if our queue is empty. We first check `s2` is empty. If so, we check `s1`. In this case we return the state of `s1`; otherwise we return false.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named ImplementQueueUsingStacks.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John