Stacks and Queues

Welcome back to the Digilent Blog! When we were working in C, we learned about the data structure called a “linked list”. Now, we’re going to go over two new data structures — stacks and queues. In this post, we’re going to make classes for stacks and queues to help show some of the capabilities of OOP (object-oriented programming)!

 

Stacks
stack

A stack is a last-in first-out (LIFO) data structure. LIFO means that the last value that was added to the stack will be the first value out. If we look at stacks as a visual representation, they’re pretty easy. You can put stuff on top of the stack, and only take stuff off the stack.

 

There are a couple functions that we use in a stack: push, pop, peek, isEmpty, and printStack. If you understand how a normal linked list works, stacks should be a lot easier!

 

1. Push. Always adds a new node to the top of the stack.
push

 

2. Pop. Removes the top element of the stack.
pop

 

3. Peek. Shows us the value of the top element, but does not modify or remove it.
peek
4. isEmpty. Checks if stack is empty, returns a bool.

isEmpty

 

5. printStack.
print

 

In C++ fashion, we created a class that encapsulates all the functions and variables of our stack. If you want to play with the code, check out the header.h, stack.cpp, and main.cpp files!

 

Queues
queue
Queues are a first-in first-out (FIFO) data structure. A line at a grocery store is a good representation of a queue, with the first customer in line being the first one to get served (ideally), with the next in line being served next.

 

Just like a stack, queues have function that allow us to push, pop, peek, print, and check if the queue is empty. Most of the functions are the same for stacks and queues, so we aren’t going to go over everything, but pop and peek are different, so we’re going to check out those two functions.

 

1. Pop. The main difference between the stack pop and the queue pop is that the latter will only remove the last item in queue.
qpop
If you check out the blog post about linked lists, the queue pop function is more similar to the delete from there than the stack pop.

 

2. Peek. Peek checks out our last value in the queue.
qpeek

 

Here’s the code files for queue! main.cpp, header.cpp, and queue.cpp. Queues and stacks are just two data structures. If you remember from last week, we also  learned about binary search trees, a data structure that has O(log N) searching, inserting, and deleting time complexity!

Be the 1st to vote.

About Josh

I love Coding!

View all posts by Josh →

2 Comments on “Stacks and Queues”

  1. Hey Josh,
    Most students are confused between the queues and stack as they are somewhat similar.
    Its a good effort that you have highlighted this topic and in a simply way you nailed the topic.
    And no doubt that eachone will understands this.

Leave a Reply

Your email address will not be published. Required fields are marked *