‘Stack’ is an abstract and linear data structure and one of the most basic data structures in Computer Science. It’s easy to learn. We will be going to know how Stack works and its implementation. This blog is dedicated to know about Stack data structure.
First of all, let’s think about a real-life event. Suppose I have some books in my room in a random place. If we think linearly, what problem with those books? The main problem is, it looks disorganized. If we want to find a book, it takes more time than finding from an organized books place. More importantly, this is taking more space than it needs.
So, what can we do? We can make a book stack to organize those books. See the image below.
Using this structure, I can easily organize my books. How can we make this stack? It’s simple, and we all know this. Generally, we put the last book on topmost of the stack for adding a book to a book stack. If there is not any book before, we look for an empty place and put our book. And for removing a book, we take the topmost book from the stack. That’s exactly how Stack work in computer science.
Stack In Computer Science
The above real-life procedure is also the same in Computer Science. In a computer, we store data in a stack. This is one of many ways of storing data.
In Stack, we can insert and remove data only from one side. It follows the LIFO principle, also known as Last In First Out. If we insert data into a stack, it will be added at the top of it. And if we remove data from a stack, it will be removed from the top of the stack.
These two operations have a name in the context of Stack. Inserting data into the Stack is known as push, and removing data is known as pop. We will see the implementation of those two operations/methods later. Apart from these, there is another operation. Which is peek. It returns the last added data from a stack but does not remove the data.
Now let’s see a visual representation.
Implementation using Array
class Stack: def __init__(self, max_size): self.limit = max_size self.stack = [None] * max_size self.pointer = -1 # push def push(self, data): self.pointer += 1 if self.pointer < self.limit: self.stack[self.pointer] = data else: self.pointer -= 1 print('Stack is Full') # pop def pop(self): if self.pointer > -1: data = self.stack[self.pointer] self.pointer -= 1 print(data) else: print('Stack is empty') # peek def peek(self): if self.pointer > -1: print(self.stack[self.pointer]) else: print('Stack is empty') def is_empty(self): print(self.pointer == -1) stack = Stack(5) stack.is_empty() # True stack.push(1) stack.push(3) stack.push(5) stack.push(7) stack.push(9) stack.push(0) # Stack is Full stack.peek() # 9 stack.pop() # 9 stack.peek() # 7 stack.is_empty() # False
Implementation using Linked List
class Node(): def __init__(self, data): self.data = data self.next = None class Stack(): def __init__(self): self.head = None # push def push(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node # pop def pop(self): if self.head == None: return 'Stack is empty' self.head = self.head.next # peek def peek(self): if self.head == None: return 'Stack is empty' return self.head.data def is_empty(self): return self.head == None stack = Stack() print(stack.is_empty()) # True stack.push(1) stack.push(3) stack.push(5) stack.push(7) stack.push(9) print(stack.peek()) # 9 stack.pop() print(stack.peek()) # 7 print(stack.is_empty()) # False
Every operation’s time complexity is O(1).
In python, we achieve these things using List. The list has all the methods built-in. Let’s see an example.
stack =  # push stack.append(1) stack.append(2) stack.append(3) # pop() stack.pop() print(stack) # [1, 2]
In computer science, Stack used a lot. Browser’s Back and Forward button and computer memory management use this data structure. Not only these but also there are so many other examples of uses of it.
I hope you got an overview of this data structure. If this blog helps you a bit, it means a lot to me.