This week in our data structure series.
We are tackling the stack.
Table of Contents
What is a stack?
A stack is a linear data structure that stores items in Last-In/First-Out (LIFO) manner. In a stack, insertion, and deletion happen at the same end called "top of the stack".
It's similar to a pile of plates or a deck of cards. For example, in a pile of plates you can:
- Put a new plate on the top
- Remove the top plate
If you want to remove the plate at the bottom, then your gonna have to remove all the plates on the top. Hence why it's called Last-In/First-Out.
Methods
At the end of the day, a stack is an abstract data type, meaning that it can be implemented in many different ways but they all must comply with the same common functionality.
- Push: add an item to the stack
- Pop: remove the top-most item in the stack
- isEmpty: checks if the stack is empty
- isFull: checks if the stack is full
- Peek: gets the top-most element without removing it
Implementation
As we said above, stacks can be implemented mainly in two ways:
- Array
- Linked-List
But keep in mind that a stack implemented using arrays are fixed stacks. Meaning they have a fixed size, however, because linked-list is not sequential, this gives them the advantage of being able to make a dynamic or limitless stack.
PS. You can bypass the array restriction by using a dynamic array.
We will now go through both implementations.
Array
For the sake of simplicity, we will use a fixed-sized array.
class Stack:
items = [];
def __init__(self):
self.items = []
def push(self, element):
self.items.append(element)
def pop(self):
if len(self.items) == 0:
print('Can not pop form an empty list')
self.items.pop();
print('Last item has been poped from the list')
def isEmpty(self):
print(len(self.items) == 0)
def peek(self):
if len(self.items) == 0:
print('Stack is Empty')
print(self.items[len(self.items) - 1]) ;
Linked List
class Node:
# Class to create nodes of linked list
# constructor initializes node automatically
def __init__(self,data):
self.data = data
self.next = None
class Stack:
# head is default NULL
def __init__(self):
self.head = None
# Checks if stack is empty
def isempty(self):
if self.head == None:
return True
else:
return False
# Method to add data to the stack
# adds to the start of the stack
def push(self,data):
if self.head == None:
self.head=Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
# Remove element that is the current head (start of the stack)
def pop(self):
if self.isempty():
return None
else:
# Removes the head node and makes
#the preceeding one the new head
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
# Returns the head node data
def peek(self):
if self.isempty():
return None
else:
return self.head.data
Complexity
Push
Because we have direct access to the beginning of our array or linked-list, we can directly append to the list. Making it a time complexity of O(1)
Pop
The same thing with the push, we simply remove from the top-most item, which we have direct access to the top of the stack. Making it a time complexity of O(1)
Peek
We have access to the top of the stack, so it's also O(1)
Search
To search we are gonna have to go through each item sequentially, making it a O(n)
Real Life Use-Cases
1. Back/Forward Button In Web Browsers
A stack is used in back and forward buttons of web-browsers.
- As we move from one page to another those pages are placed on a stack
- URL's of a website get stored on a stack
- Current page is placed on the top of the stack
- When we press the back button that the elements start poppingΒ up and display the result in reverse order.
- In this way stack is used in the forward and backward button of a web browser
PS. This is method is also used in tech editors for the undo/redo mechanism.
2. In compilers
Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9)
by converting the expression to prefix or postfix form.
3. To reverse a word
Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.
Conclusion
In summary:
- A stack is a linear data structure that stores items in Last-In/First-Out (LIFO) manner.
- In a stack, insertion, and deletion happen at the same end called "top of the stack".
- The three main functions of the stack are
push
,pull
, andpeek
.
I hope you got something out of this post, and if you have any questions feel free to leave them down below.
Top comments (0)