Stacks & Queues

#computerscience #100daysofcode

Stacks and queues are some pretty neat data structures in my opinion. In some ways they are similar. They are both linear data structures after all. But, there are certainly some key differences. Let’s learn a bit more about stacks and queues, shall we?

What is a Stack?

Let me show you what a stack is. Actually, you probably already know what it is. You just don’t know it yet. Let me describe a common scene in my life that I think that you might be able to relate to.

Hello internet! How are you doing today? Time to get some work done. First let me check my email. Hmm, ok, here is one from that Nigerian prince that I’ve been chatting with, let’s see how he is doing. (opens email) (reads email) Ah, ok, looks like the money that I loaned him is really helping him out. Good. Now let me get back to my other emails. (hits back button)

Ah, here is one about I how I can get my hair line back to where it used to be. (opens email) (reads email) (orders special cream) Ah, good, glad I found this email. My dating life hasn’t been so good lately. This should help. (hits back button)

Ok, here is another one. Learn these 5 easy workouts that Ryan Reynolds does to get shredded. (opens email) Hmm what is this link at the bottom? (clicks link) Smart scientists prove that moon is made of cheese! (clicks another link) (clicks another link) (clicks another link) (clicks another link) Holy smokes! Where am I?! (hits back button) (hits back button) (hits back button) (hits back button) (hits back button) (hits back button) Phew, all right, let’s keep going. Learn these 5 hacks that doctors don’t . . .

In the above scenario we have just witnessed the concept of a stack being used. Can you guess where? That’s right: the back button! Your browser keeps a history of the websites that you visit. As you go from website to website you are also able to go “back” as well. However, you are only able to go back to the immediately previous website. In a nutshell, this is what a stack is. Let me explain.

Think of a stack as several books that are placed one on top of the other. The book that is on top is the only one that can be immediately accessed. If you want to get to a book at the bottom then you have to remove every book that is on top to get there. If you add another book to the stack then that book is now on top and is the one that can be immediately accessed.

The very first book that is put into the stack is the one that has to be taken out last. Similarly, a book that is put in last will have to be taken out first. This is called: Last In First Out (LIFO).

The following figure shows a stack with arbitrary numbers stored as data:

Some Key Terms

Let us become familiar with some key terms for stacks that are used in Java:

push: Inserts an element at the top
pop: Removes an element from the top and returns it
isFull: Returns true if stack is full and false otherwise
isEmpty: Returns true if stack is empty and false otherwise
top: Returns the element at the top

Let us look at some illustrations to help show the push and pop functionalities of a stack. Some arbitrary numbers have been stored into each element of the stack.

The following figure illustrates the push functionality:

The following figure illustrates the pop functionality:

Stack Overflow

You are probably still wondering what a stack overflow is though. Well to put it simply as possible, it is when one too many elements are added to the stack. This happens when the data that is being pushed onto the stack exceeds the memory that has been allocated for the stack.

If you recall in my post about linked lists and arrays I talked about some key differences between the two data structures. The main difference is that an array has a set size while a linked list does not. Both linked lists and arrays can be used when constructing a stack. Although, there really hasn’t yet been a general consensus on which implementation is more efficient. If an array is used as a stack then there is always the possibility of the array size being exceed. While linked lists do not have a fixed size they do require some extra memory to store their pointers.

With an array as the stack, if the stack ends up reaching the capacity of the array then the data can be copied into a bigger array that can hold more data. Although, it should be noted that ultimately it is the use case of the stack that decides whether a linked list or array should be used. Check out this Stack Overflow post for reference.

What is a Queue?

To be honest, I think that the easiest way to understand a queue is to envision a line (or queue) of people. Let’s say that they are at the movies. If someone enters the line then they must enter at the back. That is, of course, assuming that they are a civilized human being and understand how lines work. Additionally, let’s say that it is time for the folks at the very front of the line to get their tickets. Then they would leave the line and go get their tickets. In a nutshell, this is how a queue data structure works.

Queues implement the FIFO method, which is short for First In First Out. According to FIFO, the first element inserted is the one that comes out first.

The following figure shows a queue with arbitrary numbers stored as data:

Some Key Terms

Let us become familiar with some key terms for queues that are used in Java:

enqueue: Inserts elements at the end of the queue
dequeue: Removes an element from the start of the queue
top: Returns the first element of the queue
isEmpty: Checks if the queue is empty
isFull: Checks if the queue is full

Let us look at an illustration to help show the queue and dequeue functionalities of a queue. Some arbitrary numbers have been stored into each element of the queue.

Much like stacks, whether an array or linked list is chosen when implementing a queue ultimately depends on the use case. The same trade-offs that were discussed for stacks apply to queues as well.

It should be noted that there are three different types of queues. The type of queue that has been discussed so far is the linear queue. There is also the circular queue and the priority queue as well.