I will start this post today and will finish it tomorrow. Today I received the 4K monitor that I ordered last week from Dell. The box looks like it is for a regular flat screen TV. My wife and I moved it downstairs. I will open the box over the weekend. Hopefully the new computer will arrive before the end of the weekend.
Tomorrow came and went. My wife had a dentist appointment, we had to stop by my son’s place and finally we stopped at the grocery store. When we got home it was past 06:00 PM. We go to sleep shortly after 07:00 PM so we sat down in the living room and chatted.
Today we had pizza for lunch / dinner. We try to have a pizza day once a month. I like pizza but it is not good for my waist.
This post deals with the implementation of stacks and queues. I tried generating the sample code on my own. When done with the implementation I mapped it somewhat to chapter 3 Stacks and Queues in the “Cracking the Coding Interview” by Gayle Laakmann McDowell.
The next post will deal with the first question regarding queue and stacks.
main <<< stack.isEMpty: true main <<< stack.push: 0 main <<< stack.push: 1 main <<< stack.push: 2 main <<< stack.push: 3 main <<< stack.push: 4 main <<< stack.push: 5 main <<< stack.push: 6 main <<< stack.isEMpty: false main <<< stack: [ 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 ] main <<<< stack.pop: 6 main <<<< stack.pop: 5 main <<<< stack.pop: 4 main <<<< stack.pop: 3 main <<<< stack.pop: 2 main <<<< stack.pop: 1 main <<<< stack.pop: 0 main <<< stack.isEMpty: true main <<< stack: [ ] main <<< queue.isEmpty: true main <<< queue.add: 0 main <<< queue.add: 1 main <<< queue.add: 2 main <<< queue.add: 3 main <<< queue.add: 4 main <<< queue.add: 5 main <<< queue.add: 6 main <<< queue.isEmpty: false main <<< queue: [ 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 ] main <<< queue.remove: 0 main <<< queue.remove: 1 main <<< queue.remove: 2 main <<< queue.remove: 3 main <<< queue.remove: 4 main <<< queue.remove: 5 main <<< queue.remove: 6 main <<< queue.isEmpty: true main <<< queue: [ ]
Let’s start with the screen capture of the Eclipse IDE running the test scaffolding used to test the operation of the stacks and queues.
package john.stack;
/*
*
*/
public class Solution {
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** instantiate a stack ****
MyStack<Integer> stack = new MyStack<Integer>();
// **** display if stack is empty ****
System.out.println("main <<< stack.isEMpty: " + stack.isEmpty());
// **** loop pushing values into the stack ****
for (int i = 0; i < 7; i++) {
stack.push(i);
System.out.println("main <<< stack.push: " + i);
}
// **** display if stack is empty ****
System.out.println("main <<< stack.isEMpty: " + stack.isEmpty());
// **** display the contents of the stack ****
System.out.println("main <<< stack: " + stack.toString());
// **** loop popping the stack ****
while (!stack.isEmpty())
System.out.println("main <<<< stack.pop: " + stack.pop());
// **** display if the stack is empty ****
System.out.println("main <<< stack.isEMpty: " + stack.isEmpty());
// **** display the contents of the stack ****
System.out.println("main <<< stack: " + stack.toString());
System.out.println();
// **** instantiate a queue ****
MyQueue<Integer> queue = new MyQueue<Integer>();
// **** display if the queue is empty ****
System.out.println("main <<< queue.isEmpty: " + queue.isEmpty());
// **** loop adding elements into the queue ****
for (int i = 0; i < 7; i++) {
queue.add(i);
System.out.println("main <<< queue.add: " + i);
}
// **** display if the queue is empty ****
System.out.println("main <<< queue.isEmpty: " + queue.isEmpty());
// **** display the contents of the queue ****
System.out.println("main <<< queue: " + queue.toString());
// **** loop removing elements from the queue ****
while (!queue.isEmpty()) {
System.out.println("main <<< queue.remove: " + queue.remove());
}
// **** display if the queue is empty ****
System.out.println("main <<< queue.isEmpty: " + queue.isEmpty());
// **** display the contents of the queue ****
System.out.println("main <<< queue: " + queue.toString());
}
}
The code starts by instantiating a stack. It then displays if the stack is empty. At this point we have not pushed elements so it should be empty.
We then loop pushing elements into the stack. When done we display is the stack is empty. At this point the stack should have 7 elements so it is not empty.
We then display the contents of the stack.
While the stack is not empty, we pop the top element from the stack. When done we display if the stack is empty. In this case it is empty.
To complete the test we display the contents of the stack. Since the stack is empty there are no elements to display.
We repeat a similar process using our queue implementation.
package john.stack;
/*
* Node used to build a stack.
*/
public class StackNode<T> {
// **** members ****
private T data;
private StackNode<T> next;
/*
* Constructor.
*/
public StackNode(T data) {
this.data = data;
this.next = null;
}
/*
* Get data.
*/
public T getData() {
return data;
}
/*
* Get next.
*/
public StackNode<T> getNext() {
return this.next;
}
/*
* Set next.
*/
public void setNext(StackNode<T> node) {
this.next = node;
}
}
The StackNode data structure contains to members. We decided to make them private.
The constructor is followed by some getters and setters. Not sure if I made used them all in the stack implementation.
package john.stack;
/*
*
*/
import java.util.EmptyStackException;
/*
*
*/
public class MyStack<T> {
// **** private ****
private StackNode<T> top;
/*
* Push specified data into stack.
*/
public void push(T data) {
// **** allocate new item for the stack ****
StackNode<T> item = new StackNode<T>(data);
// **** set next in the item ****
item.setNext(top);
// **** update the top of the stack ****
top = item;
}
/*
* Pop element from stack.
*/
public T pop() {
// **** check if stack is empty ****
if (top == null)
throw new EmptyStackException();
// **** get the top item ****
T item = top.getData();
// **** update the top ****
top = top.getNext();
// **** return the item ****
return item;
}
/*
* Peek top element in stack.
*/
public T peek() {
// **** check if stack is empty ****
if (top == null)
throw new EmptyStackException();
// **** return the value at the top of the stack ****
return top.getData();
}
/*
* Check if stack is empty.
*/
public boolean isEmpty() {
return top == null;
}
/*
* Return a string with the contents of the stack.
*/
public String toString() {
// **** check if stack is empty ****
if (top == null)
return "[ ]";
// **** ****
StringBuilder sb = new StringBuilder("[ ");
// **** ****
StackNode<T> t = top;
// **** traverse the stack ****
while (t != null) {
// *** ****
if (t.getNext() != null)
sb.append(t.getData() + " -> ");
else
sb.append(t.getData());
// **** ****
t = t.getNext();
}
// **** ****
sb.append(" ]");
// **** ****
return sb.toString();
}
}
We start by representing the stack with the top private variable.
The methods for the different operations follow: push, pop, peek, isEmpty and I decided to add toString.
Now let’s take a look at the queue implementation.
package john.stack;
/*
* Node used to build a queue.
*/
public class QueueNode<T> {
// **** members ****
private T data;
private QueueNode<T> next;
/*
* Constructor.
*/
public QueueNode(T data) {
this.data = data;
this.next = null;
}
/*
* Get next element.
*/
public QueueNode<T> getNext() {
return this.next;
}
/*
* Set next element.
*/
public void setNext(QueueNode<T> node) {
this.next = node;
}
/*
* Get the data from the node.
*/
public T getData() {
return this.data;
}
}
There is a strong similarity between the node implementations for the queue and stack. As a matter of fact we could have only used one implementation and perhaps named the class Node.
package john.stack;
/*
*
*/
public class MyQueue<T> {
// **** ****
private QueueNode<T> first = null;
private QueueNode<T> last = null;
/*
* Add element to the queue.
*/
public void add(T item) {
// **** allocate a node ****
QueueNode<T> node = new QueueNode<T>(item);
// **** the queue is empty ****
if ((first == null) && (last == null)) {
this.first = node;
this.last = node;
}
// **** the queue is not empty ****
else {
last.setNext(node);
this.last = node;
}
}
/*
* Check if queue is empty.
*/
public boolean isEmpty() {
// **** ****
if ((first == null) && (last == null))
return true;
else
return false;
}
/*
* Remove the first element from the queue.
*/
public T remove() {
QueueNode<T> node = null;
// **** check if last element in the queue ****
if ((first != null) && (last != null) && (first == last)) {
node = last;
this.first = null;
this.last = null;
}
// **** remove first element from the queue ****
else {
node = first;
first = first.getNext();
}
// **** ****
return node.getData();
}
/*
* Return a string holding the values in the queue.
*/
public String toString() {
// **** for performance ****
StringBuilder sb = new StringBuilder("[ ");
// **** traverse the queue ****
QueueNode<T> p = this.first;
while (p != null) {
// **** display the value of this element ****
if (p.getNext() != null)
sb.append(p.getData() + " -> ");
else
sb.append(p.getData() + " ");
// **** move to the next element ****
p = p.getNext();
}
// **** close the list ****
sb.append("]");
// **** ****
return sb.toString();
}
}
The queue is represented by two private variables first and last. Note that stacks are FILO and queues are FIFO.
For the queue we have implemented: add, isEmpty, remove and I also added the toString method.
I will stop this blog at this time. It seems like it takes me about an hour to get the post on WordPress done.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa
Loved that code, John! I shall return.
Charlie G.