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)!
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!
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.
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.
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!