You actually already know what a Stack and a Queue are – you just don’t know it. Or, maybe you do! As my good friend, Sandeep would say:

A Stack is a Pringles box

A Queue is a lineup.

Let’s break both of these up into two sections.

## The Stack

A stack is a data structure that operates on a ‘First In, Last Out’ basis. You can think of it as an array (or more accurately, an ArrayList if you come from Java) with only two methods: **pushOn()** and **popOff()**

The only element that is ever visible on a Stack is the top element (again, think of the Pringles box). Once a new element is pushed on, the previous top element is pushed down while the new element becomes visible. Likewise, when the top element is popped off, the element below it becomes visible. Let’s look at this visually, and then in code:

| element 5 | | element 4 | | element 3 | | element 2 | | element 1 | -----------

Only the 5th element is visible here. The rest are hidden below in a `Stack` formation! The idea here is that you’re restricted by only being able to add and remove to the top of the Stack only. The bottom remains out of your control. Let’s build one with the required methods!

To do this, we’re going to use our old LinkedList class, that we called `Link`.

public class Stack { // first item in the stack Link top; void pushOn(int item){ // create the new item to push on Link newItem = new Link(item); // set the new item's next Link // to be equal to the current top Link newItem.next = top; // set the top item as the new item top = newItem; } Object pop(){ // if the top exists if(top != null){ // set the item to equal top.data int item = top.data; // set the top item to be // the item directly after it // (i.e. top.next) top = top.next; //return the item return item; } // return null if the top is null return null; } int peek(){ // return the top item's data return top.data; } void printStack(Stack stack){ while(!stack.isEmpty()){ System.out.println(stack.peek()); stack.top = stack.top.next; } } }

And that’s it! We built a Stack.

## The Queue

As Sandeep said earlier, a Queue is just a lineup. Instead of the top item being the one that is visible, a Queue makes the bottom one accessible instead. It’s a ‘First In, First Out’ system – just line a line in the grocery store. Let’s visualize this:

——————————————–

Item 5 > Item 4 > Item 3 > Item 2 > Item 1 (this item was the first to be pushed on)

——————————————–

As you can see, item one was the first one pushed onto the Queue, and is also the first one to be accessible as well. Queue’s support **pushOn** as well as **popOff**, just like Stacks!

Let’s build one:

public class Queue { // the first item is the visible one Link first, last; void pushOn(int item){ // check if the Queue is empty if(first == null){ // if so, set the last item to the new one last = new Link(item); // set the first equal to the last since // there is only one and we need to be able to see it first = last; } else { // if not, set the item after the last one // to be our new item last.next = new Link(item); // and then reassign the last item to be that new one last = last.next; } } void popOff(){ // if the first item isn't null - aka the Queue isn't empty if(first != null){ // get the first item Link item = first; // set the first item to be equal to the second first = first.next; } } }

That’s all there is to it! Super easy, right? Let’s grab a problem from ‘Cracking the Coding Interview’ and put this knowledge to work.

Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.

Let’s dive in. First, we know that we need to iterate through the Stack until it is empty. This gives us the chance to put recursion to work, where our base case is when the unsorted Stack is empty.

Stack sort(Stack unsorted){ // create a new stack that we will fill // with sorted items Stack sorted = new Stack(); // create temp to hold the data // while we pop() elements int temp = 0; // iterate while unsorted isn't empty while(!unsorted.isEmpty()){ // start by removing the top // element and placing it into temp temp = unsorted.pop(); // iterate while sorted isn't empty AND // temp is less that the top sorted element while(!sorted.isEmpty() && temp < sorted.peek()){ unsorted.push(sorted.pop()); } // push the temp onto the sorted stack // this is where the first push occurs sorted.push(temp); } // return the sorted stack return sorted; }

Confused a bit? That’s okay, we’ll go over it.

Let’s start with an imaginary Stack:

| 2 | | 3 | | 1 | ---

So, we start with two Stacks – one is **unsorted** and not empty, while the other is the **sorted** Stack and IS empty. We start by removing the top element in the **unsorted** Stack, and pushing it onto the **sorted** Stack (in this case, we push the 2 onto the sorted stack). Now we have two stacks that look like this:

| 3 | | 2 | | 1 | --- ---

After that, we pop another element off of the **unsorted** Stack, in this case 3, and check to see if 3 is less than the top element of the **sorted** Stack. It’s not, therefore, push the 3 onto the **sorted** Stack. Now our Stacks look like this:

| 1 | | 3 | --- | 2 | ---

But now we run into a problem. You see, when we check if 1 < 3, the condition checks out. Therefore, we push the 3 back onto the **unsorted** Stack, while removing it from the **sorted** Stack. Remember, the **unsorted** Stack is empty because we removed the 1 and stored it in temp. Now our Stacks look like this:

| | | 3 | --- | 2 | --- temp = 1

We pus the 3 and the 2 back onto the unsorted Stack, and then push the 1 onto the **sorted** stack. Afterwards, we push the 2, followed by the 3 back onto the **sorted** Stack as well and BAM! Our **sorted** Stack is well, sorted!

| 3 | | 2 | | 1 | ---

## Leave a Reply