This week in our data structure series.
We are tackling the 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.
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
As we said above, stacks can be implemented mainly in two ways:
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.
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]) ;
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
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
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
We have access to the top of the stack, so it's also
To search we are gonna have to go through each item sequentially, making it a
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.
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.
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.
- 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
I hope you got something out of this post, and if you have any questions feel free to leave them down below.