If you’re a programmer or studying computer science, understanding how the stack data structure works is essential. This is a very versatile and commonly used structure, often used to store and manage data that you need to process in a particular order. Some of these ideas can seem complicated at first, so we’re going to break down exactly what a stack is, how it works and its advantages and disadvantages, with examples to illustrate.
What is a Stack?
When you see the word “stack”, you may be imagining a pile of books or even pancakes on a plate. It turns out, these are rather good analogies for understanding the concept. In computer science, stacks operate much by the same principles as a stack of books. We can stack several books on top of each other, but when it comes to removing a book, we tend to remove the top book first. That is if we want to avoid any unfortunate accidents. This is the principle by which stack structures work and is known as the “Last-In-First-Out” or LIFO principle. Whatever element is placed in the stack last will be the first to be removed, similar to books or pancakes. This differs from queues, which use the “First-In-First-Out” principle, much like real-life queues.
How is the Stack Data Structure Used?
When using stacks, some operations are used more than others. These are:
- push() – This is equivalent to inserting an element into the top of the stack.
- pop() – This can be seen as deleting an element from the stack, which will also be from the top.
- isFull() – This tells us whether the stack is full.
- isEmpty() – This indicates whether the stack is empty or non-empty.
- peek() – Peek returns the element at a specified position.
- count() – Count simply tells us the number of elements within the stack.
- change() – This allows us to modify the element at a given position.
- display() – This prints the elements in the stack to the console.
We can illustrate all of these basic functions with an example. For this, we’ve used Python. Here is the code:
class Stack:
def __init__(self, max_size):
self.max_size = max_size
self.stack = []
def push(self, item):
if len(self.stack) < self.max_size:
self.stack.append(item)
print(f"Pushed item: {item}")
else:
print("Stack is full. Cannot push item.")
def pop(self):
if not self.is_empty():
item = self.stack.pop()
print(f"Popped item: {item}")
else:
print("Stack is empty. Cannot pop item.")
def is_full(self):
return len(self.stack) == self.max_size
def is_empty(self):
return len(self.stack) == 0
def peek(self):
if not self.is_empty():
return self.stack[-1]
else:
print("Stack is empty. No item to peek.")
def count(self):
return len(self.stack)
def change(self, index, new_item):
if index >= 0 and index < len(self.stack):
self.stack[index] = new_item
print(f"Changed item at index {index} to: {new_item}")
else:
print("Invalid index.")
def display(self):
print("Stack contents:")
for item in self.stack[::-1]:
print(item)
my_stack = Stack(5)
my_stack.push(10)
my_stack.push(20)
my_stack.push(30)
my_stack.push(40)
my_stack.push(50)
my_stack.push(60)
my_stack.display()
print("Peeked item:", my_stack.peek())
my_stack.change(1, 25)
my_stack.pop()
my_stack.pop()
my_stack.pop()
my_stack.pop()
my_stack.pop()
my_stack.display()Explanation of the code
There’s a lot going on here, so let’s break it down. First, we define the class “Stack”, and the constructor method which takes the “max_size” parameter.
We then define the “push” method, which adds elements to the stack as long as it isn’t full.
The “pop” method is next, which returns an equivalent error message if the stack is already empty.
The “is_full” and “is_empty” methods are then defined, which indicate the stack is full or empty if it’s equivalent to the max size or 0 respectively.
The “peek” method then checks if the stack is empty, and returns the top element if not.
After this, “count” returns the number of elements in the stack.
Then, we perform some modifications by defining the “change” method. This checks whether the index is in the stack range, and replaces this with “new_item”.
We then define the “display” method to print the stack contents, iterating over the stack in reverse.
Lastly, we create a stack with a maximum size of 5 and push multiple integers onto the stack until it’s full. We then print the contents, print the peeked element, change the element at index 1, and remove all the elements using “pop”. This result is also printed, showing that the stack is now empty. The input and output for this can be seen in the image below.
©History-Computer.com
©History-Computer.com
Why are Stacks Used? What Are the Pros and Cons?
The stack data structure is often used when we need to access and edit elements in a precise order. They allow for easy undo/redo actions since we can easily pop and push elements as required. Lining up functions is also a common use, as we can keep track of which have been executed and which haven’t. Stacks also provide an easy way to keep track of memory allocation.
Overall, stacks are fairly easy to use and fast to access, which makes them popular for solving problems in computer science. However, they do come with some limitations. Stacks have a finite size, so we may potentially lose data if we try to add too many elements to a full stack (known as overflow). Likewise, if too many are removed, we can run into underflow problems. Unlike arrays, we also don’t have permission to randomly access stack elements, since we can only access the topmost element. If we want to access an element somewhere down a stack, we have to first remove all the elements above it. As you can expect, this is a rather cumbersome and undesirable operation.
What Are Some Real-Life Applications of the Stack Data Structure?
Stacks aren’t just applicable to computer science. Many real-world scenarios make use of the stack data structure. These include:
- Browsers – When we store our search history on a browser, this is done using stacks. Every time we go to a webpage, the URL of the page is pushed onto a stack. When we backtrack to a previous page, the previous URL is displayed on your screen and popped from the stack.
- Calls – Similarly to browsers, we usually have a call history on our mobile devices. A stack is used here so that we can access the most recent call.
- Word processing – Whenever we want to undo an action, such as deleting or typing, stacks are used to do this. Just like URLs are pushed and popped, so are the actions we take when using a word processor.
- Calculators – Maybe not an everyday use for most, but calculators do use stacks. Since it’s crucial to perform mathematical operations in the correct order, a calculator uses a stack to prioritize their operations.
What is a Multi-Stack?
Instead of a stack of books, we can think of a multi-stack as a filing cabinet. The cabinet itself is the multi-stack, whereas each compartment within the cabinet is an individual stack. We can push and pop files in each compartment without affecting the integrity of the whole cabinet. This is the same principle that multi-stacks work by. The memory is stored in separate regions and is often managed more efficiently by using a multi-stack. As such, multi-stacks are used for memory management, and also resource management, where we need to manage several operations.
What is the Complexity of a Stack?
The time complexity of stack operations depends on which operations we’re talking about. Generally, push, pop, and peek are constant-time operations, meaning they don’t depend on the stack size. Count can also be constant-time if we’re keeping track of count while we’re performing push and pop functions. These time complexities are based on the typical stack implementation, which operates by the LIFO principle. Generally, the space complexity is linearly proportional to the stack size. It’s good to note that this only refers to the memory used to store the stack elements, and not to the memory used for the program itself.
Stack Data Structure: Wrapping Up
To conclude, stacks are extremely useful data structures in virtually all programming languages. As such, understanding how they work is helpful, whether you’re in education or working as a programmer. Using the LIFO principle, stacks help maintain the order of elements in a simple manner. Stacks can make storage more efficient, as long as they’re used correctly, but overflow and underflow problems are possible. There are many real-world uses of stacks, such as call and browser history, and undo/redo operations in various programs.
The image featured at the top of this post is ©Gorodenkoff/Shutterstock.com.
