Previously in this series, I discussed the data structure Queue and how to implement them. The main feature about the queue that you should remember is the FIFO principle — first in, first out.
This week, I’ll be discussing another data structure with a similar principle as the queue — the stack.
In this blog, I’ll go over the basic details of a stack. Next week, I’ll discuss how to implement a stack using an array.
Like I mentioned above, a stack is very similar to the queue. It’s another ordered list of elements, but this time with a “LIFO” principle.
“LIFO” stands for “Last In, First Out” — the last element that is inserted into the stack will also be the first element that is removed from the queue.
Imagine you’re in middle school, borrowing a textbook for a class assignment. Everyone takes a book starting from the top of the pile. When finished with the assignment, everyone also puts the book down on top of one another. The following day, you have to use the textbook again for another assignment. The first book that’s removed from the pile will be the last book placed at the top of the pile. It would make no sense to take a book from the middle of the pile, nor would it make sense to place a book back into the middle of the pile, or even the bottom of the pile.
Stacks have three main operations: inserting an element at the end of the list (push), removing an element at the end of the list (pop), and returning the last element of the list (peek).
Advantages + Disadvantages
The great thing about stacks is that you can use them when you need to reverse a list. By popping off each element into a new stack, the last element of the previous stack will now be the first element of the new stack.
You could also easily “undo” something by popping off the last element. Stacks are also dynamic in size and known to take little space, leading to its low runtime (just like the queue).
The main disadvantage is that elements are “destroyed” once popped off, and they’re not very flexible (considering you can only remove element at a time and work with the last element of the stack at all times).
Next week, I’ll discuss how to implement a stack using an array, as well as the three main operations that stacks use.