Yesterday I was talking with a coworker about the time it takes (me) to produce a post in this blog. Towards the end of the day, after a nice walk with my wife, I developed the code for this post. My inspiration came from a YouTube video by Irfan Baqui. I am a firm believer that in order to verify you understand some subject, you need to write about it. The reason for writing is that one explains the subject to the reader.
In this case I have some classes that implement queues using stacks. In the actual implementation of stacks or queues one can easily turn one into the other. Stacks are FILO (First In Last Out) data structures and Queues are FIFO (First In First Out). Think of a stack of dishes at a cafeteria. The first dish placed in a stack is the last one to come out. On the other hand, in a queue (the name British give to lines) the first person arriving to a queue expects to be serviced first.
The topic of this post is to implement a queue in a stack followed by a queue with two stacks, and finally a queue with a single stack using recursion.
First let’s take a look at a screenshot of the console in the Eclipse IDE:
isEmpty: true add: 0 add: 1 add: 2 add: 3 add: 4 q: tail --> 0 1 2 3 4 <-- head (insert here) remove: 0 remove: 1 remove: 2 remove: 3 remove: 4 remove: null isEmpty: true add: Mike add: Pete add: John add: Steve add: Rob remove: Mike add: Carmen add: Mary remove: Pete add: Jane add: Cecilia add: Deb q2s: tail --> John Steve Rob Carmen Mary Jane Cecilia Deb <-- head (insert here) remove: John remove: Steve remove: Rob remove: Carmen remove: Mary remove: Jane remove: Cecilia remove: Deb remove: null isEmpty: true add: 0 add: 1 add: 2 add: 3 add: 4 remove: 0 remove: 1 remove: 2 remove: 3 remove: 4 remove: null
The first set of output illustrates some testing on a queue implemented using a Java stack and some methods found in the Stack class. First we check that the instantiated queue is empty. Five numbers are inserted into the queue. The contents of the queue are displayed. The contents are then pulled out until the queue is empty.
One can tell that the numbers are entered in ascending order. In a stack the first element would be at the bottom. When pulled out it would be the last one. The implementation shows that the first element inserted is the first retrieved indicating a FIFO implementation.
For the second class I decided to use test for the test. Once you take a look at the implementation you will be able to see that the three classes support multiple types. This has nothing to do with the stack or queue but I just fell like implementing it that way. In the second case, the queue implemented with two stacks, we add, remove and add names. The content of the queue is shown and then we remove the elements in a FIFO order.
Last but not least, the last implementation is quite elegant. I do not have anything against implementing software using recursion, but compared with the other two implementations, it has a serious limitation if the number of elements is in the thousands. In my case, I am running on a DELL computer with 32 GBs and dual processors with multiple cores. When the number of elements in the queue approaches 4,000 the code crashes.
Now let’s take a look at the main code which I used to test the classes:
/*
* Test our queue implemented with a single stack.
* Test our queue implemented with two stacks.
* Test the queue implemented with a single stack using recursion.
*/
public static void main(String[] args) {
// final int elements = 3920;
final int elements = 5;
// **** instantiate queue ***
Que<Integer> q = new Que<Integer>();
// **** is empty ***
System.out.println("isEmpty: " + q.isEmpty());
// **** add(s) ***
for (int i = 0; i < 5; i++) {
System.out.println(" add: " + i);
q.add(i);
}
System.out.println();
// **** display the queue contents ****
System.out.println("q: " + q.toString());
System.out.println();
// **** remove all elements ***
while (!q.isEmpty()) {
System.out.println("remove: " + q.remove());
}
System.out.println();
// **** attempt to remove element when queue is empty ****
System.out.println("remove: " + q.remove());
System.out.println();
// **** instantiate queue ***
Q2S<String> q2s = new Q2S<String>();
// **** is empty ***
System.out.println("isEmpty: " + q2s.isEmpty());
// **** add(s) ****
q2s.add("Mike"); System.out.println(" add: Mike");
q2s.add("Pete"); System.out.println(" add: Pete");
q2s.add("John"); System.out.println(" add: John");
q2s.add("Steve"); System.out.println(" add: Steve");
q2s.add("Rob"); System.out.println(" add: Rob");
// **** 1 remove ***
System.out.println("remove: " + q2s.remove());
// **** 2 adds ****
q2s.add("Carmen"); System.out.println(" add: Carmen");
q2s.add("Mary"); System.out.println(" add: Mary");
// **** 1 remove ****
System.out.println("remove: " + q2s.remove());
// **** 3 adds ****
q2s.add("Jane"); System.out.println(" add: Jane");
q2s.add("Cecilia"); System.out.println(" add: Cecilia");
q2s.add("Deb"); System.out.println(" add: Deb");
System.out.println();
// **** display the queue contents ****
System.out.println("q2s: " + q2s.toString());
System.out.println();
// **** remove all elements ****
while (!q2s.isEmpty()) {
System.out.println("remove: " + q2s.remove());
}
System.out.println();
// **** attempt to remove element when queue is empty ****
System.out.println("remove: " + q2s.remove());
System.out.println();
// **** instantiate queue ***
Q<Integer> que = new Q<Integer>();
// **** is empty ***
System.out.println("isEmpty: " + que.isEmpty());
// **** add(s) NOTE: in my computer larger values e.g., 4,000 crashes the program :o( ***
for (int i = 0; i < elements; i++) {
System.out.println(" add: " + i);
que.add(i);
}
System.out.println();
// **** remove all elements ***
while (!que.isEmpty()) {
System.out.println("remove: " + que.remove());
}
System.out.println();
// **** attempt to remove element when queue is empty ****
System.out.println("remove: " + que.remove());
}
As you can see in the last test, if the number of elements inserted into the queue reaches about 4,000 the code crashes. Just as a reminder I left the constant as a reference. You never know when I will go back and attempt to increase the count or solve the issue altogether.
The entire Java code follows:
package canessa.queue.stack;
import java.util.Stack;
public class Solution {
/*
* Implement a queue using a single stack.
*/
static class Que<E> {
Stack<E> s = null;
/*
* constructor
*/
public Que () {
s = new Stack<E>();
}
/*
* add
*/
public void add (E val) {
s.push(val);
}
/*
* remove
*/
public E remove () {
if (s.isEmpty())
return null;
else return s.remove(0);
}
/*
* is empty
*/
public boolean isEmpty() {
return s.isEmpty();
}
/*
* return string with contents of queue
*/
public String toString() {
String str = "tail --> ";
for (int i = 0; i < s.size(); i++) {
str += "" + s.elementAt(i) + " ";
}
str += "<-- head (insert here)";
return str;
}
}
/*
* Implements a queue using two stacks.
* Note this needs a mutes to work reliably!!!
*/
static class Q2S <E> {
/*
* members
*/
Stack<E> in;
Stack<E> out;
/*
* constructor
*/
public Q2S () {
in = new Stack<E>();
out = new Stack<E>();
}
/*
* add
*/
public void add (E val) {
in.push(val);
}
/*
* remove
*/
public E remove () {
// **** ****
if (out.isEmpty())
moveIn2Out();
// **** ****
if (out.isEmpty())
return null;
else return out.pop();
}
/*
* is empty
*/
public boolean isEmpty () {
return in.isEmpty() && out.isEmpty();
}
/*
* move values from the in to the out stack
*/
private void moveIn2Out () {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
/*
* return string with the contents of queue
*/
public String toString () {
String str = "tail --> ";
for (int i = out.size() - 1; i >= 0; i--) {
str += "" + out.elementAt(i) + " ";
}
for (int i = 0; i < in.size(); i++) {
str += "" + in.elementAt(i) + " ";
}
str += "<-- head (insert here)";
return str;
}
}
/*
* Single stack without using Java Stack class methods
* like we did in the class Que.
*/
static class Q <E> {
/*
* member(s)
*/
Stack<E> s = null;
/*
* constructor
*/
public Q () {
this.s = new Stack<E>();
}
/*
* add element to the queue
*/
public void add (E val) {
s.push(val);
}
/*
* check if the queue is empty
*/
public boolean isEmpty () {
return s.isEmpty();
}
/*
* use recursion to get to the bottom element in the stack
* and return it and push the remaining elements into the
* same stack.
*/
private E recurse () {
// **** end recursion ****
if (s.size() == 1) {
return s.pop();
}
// **** recurse ****
E currVal = s.pop();
E result = recurse();
s.push(currVal);
// **** to be pushed into the stack or returned to caller ****
return result;
}
/*
* remove tail element from the queue
*/
public E remove () {
if (s.isEmpty())
return null;
return recurse();
}
}
/*
* Test our queue implemented with a single stack.
* Test our queue implemented with two stacks.
* Test the queue implemented with a single stack using recursion.
*/
public static void main(String[] args) {
// final int elements = 3920;
final int elements = 5;
// **** instantiate queue ***
Que<Integer> q = new Que<Integer>();
// **** is empty ***
System.out.println("isEmpty: " + q.isEmpty());
// **** add(s) ***
for (int i = 0; i < 5; i++) {
System.out.println(" add: " + i);
q.add(i);
}
System.out.println();
// **** display the queue contents ****
System.out.println("q: " + q.toString());
System.out.println();
// **** remove all elements ***
while (!q.isEmpty()) {
System.out.println("remove: " + q.remove());
}
System.out.println();
// **** attempt to remove element when queue is empty ****
System.out.println("remove: " + q.remove());
System.out.println();
// **** instantiate queue ***
Q2S<String> q2s = new Q2S<String>();
// **** is empty ***
System.out.println("isEmpty: " + q2s.isEmpty());
// **** add(s) ****
q2s.add("Mike"); System.out.println(" add: Mike");
q2s.add("Pete"); System.out.println(" add: Pete");
q2s.add("John"); System.out.println(" add: John");
q2s.add("Steve"); System.out.println(" add: Steve");
q2s.add("Rob"); System.out.println(" add: Rob");
// **** 1 remove ***
System.out.println("remove: " + q2s.remove());
// **** 2 adds ****
q2s.add("Carmen"); System.out.println(" add: Carmen");
q2s.add("Mary"); System.out.println(" add: Mary");
// **** 1 remove ****
System.out.println("remove: " + q2s.remove());
// **** 3 adds ****
q2s.add("Jane"); System.out.println(" add: Jane");
q2s.add("Cecilia"); System.out.println(" add: Cecilia");
q2s.add("Deb"); System.out.println(" add: Deb");
System.out.println();
// **** display the queue contents ****
System.out.println("q2s: " + q2s.toString());
System.out.println();
// **** remove all elements ****
while (!q2s.isEmpty()) {
System.out.println("remove: " + q2s.remove());
}
System.out.println();
// **** attempt to remove element when queue is empty ****
System.out.println("remove: " + q2s.remove());
System.out.println();
// **** instantiate queue ***
Q<Integer> que = new Q<Integer>();
// **** is empty ***
System.out.println("isEmpty: " + que.isEmpty());
// **** add(s) NOTE: in my computer larger values e.g., 4,000 crashes the program :o( ***
for (int i = 0; i < elements; i++) {
System.out.println(" add: " + i);
que.add(i);
}
System.out.println();
// **** remove all elements ***
while (!que.isEmpty()) {
System.out.println("remove: " + que.remove());
}
System.out.println();
// **** attempt to remove element when queue is empty ****
System.out.println("remove: " + que.remove());
}
}
The entire process took me about five hours. I can imagine how long it takes for people on YouTube to prepare a technical video, capture and edit it to their satisfaction. I have been thinking about starting a video blog, but with my current set of obligations it is not doable.
Hope you enjoy the post. If you have comments or questions, please leave me a note at the end of the post.
Happy software development;
John
Follow me on Twitter: @john_canessa