Stack | Data Structure

Introduction

‘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.

Concept

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.

Coding

We can implement Stack using Array or Linked List. Now let’s see the code implementation of Stack both ways in Python.

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.