Stack
What is stack data structure?
Stacks are linear collections of elements and are classified as abstract data types
New elements pile upon prior elements so the top of the stack is always the last element added
FILO (First in Last out) or LIFO (Last in First out) is the way to summarise stack
Elements can be inserted and deleted only from one side of the list, called the top
The insertion of an element into a stack is called pushing
Deletion of an element from the stack is called popping
In stacks, The last element in a list is tracked with a pointer called top or peek
Why use it?
Stack data structures are useful when the order of actions is important
They ensure that a system does not move onto a new action before completing those before
Time-efficient and space-efficient implementation for a particular type of problem statements
Implementation through the queue.LifoQueue takes care of multi-threading operations
Basic Operations in Stack
Push:
Add an element to the top of a stack
Time complexity is O(1)
Pop:
Remove an element from the top of a stack
Can we remove an element in the middle of the stack immediately?
No, we cannot. We can only remove an element from the top of the stack
Time complexity is O(1)
IsEmpty:
Check if the stack is empty
Time complexity is O(1)
IsFull:
Check if the stack is full
Peek or Top:
Get the value of the top element without removing it
Time complexity is O(1)
Traverse or Search:
Accessing each element of the stack
Time complexity is O(n)
How to use it?
A pointer called TOP is used to keep track of the top element in the stack.
When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing
TOP == -1.On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP.
On popping an element, we return the element pointed to by TOP and reduce its value.
Before pushing, we check if the stack is already full
Before popping, we check if the stack is already empty
Implementation
Using lists
The list was built upon blocks of contiguous memory, meaning that the items in the list are stored right next to each other
The list is great for several operations, like indexing. Getting myList[3] is fast, as Python knows exactly where to look in memory to find it. This memory layout also allows slices to work well on lists.
The contiguous memory layout is the reason that the list might need to take more time to .append() some objects than others. If the block of contiguous memory is full, then it will need to get another block, which can take much longer than a normal .append()
class Stack:
def __init__(self, stack=[]):
self.stack = stack
def push(self, item):
self.stack.append(item)
return True
def is_empty(self) -> bool:
return not bool(self.stack)
def pop(self) -> bool:
if not self.is_empty():
self.stack = self.stack.pop()
return True
return False
def peek(self):
if not self.is_empty():
return self.stack[-1]
def size(self) -> int:
return len(self.stack)Using collection called deque
Deque is built upon a doubly linked list. In a linked list structure, each entry is stored in its own memory block and has a reference to the next entry in the list
The doubly linked list allows you to easily add nodes to either end of the list
Adding a new entry into a linked list structure only requires setting the new entry’s reference to point to the current top of the stack and then pointing the top of the stack to the new entry
Indexing and slicing is a heavy operation for deque, but stacks and queues are hardly used for it
It gives O(1) time complexity for enqueuing and dequeuing elements, but O(n) time complexity for randomly accessing elements in the middle of the queue
Because deques support adding and removing elements from either end equally well, it can be actually used for both queues and stacks
from collections import deque
my_tack = deque()
my_stack.append('a') # push element into the the stack
my_stack.append('b')
my_stack.append('c')
my_stack.pop() # pop element from the stack
len(my_stack) # get length of the stack, can be used to check is_empty as wellUsing LifoQueue
List are not thread save, should not be used in multi-threading
Deque is a little more complex. The documentation clearly states that both the .append() and .pop() operations are atomic, meaning that they won’t be interrupted by a different thread. Other methods in deque are not thread-safe
LifoQueueis designed to be fully thread-safe. All of its methods are safe to use in a threaded environment. It also adds optional time-outs to its operations which can frequently be a must-have feature in threaded programs
from queue import LifoQueue
my_stack = LifoQueue()
my_stack.put('a') # push operation
my_stack.put('b')
my_stack.put('c')
print(my_stack) # printing will show you an object
my_stack.get() # pop operationUsing LinkedList
Try it after going through the LinkedList section
class StackNode:
# Constructor to initialize a node
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self, root=None):
self.root = root
def push(self, item):
this_node = StackNode(item)
this_node.next = self.root
self.root = this_node
return True
def pop(self):
if self.root:
temp = self.root.data
self.root = self.root.next
return temp
return False
def size(self):
if self.is_empty():
return 0
this_node = self.root
size = 0
if this_node.next:
size += 1
this_node = this_node.next
return size+1
def is_empty(self):
return not bool(self.root)
Where to Use Stack Data Structure?
To reverse a word - Put all the letters in a stack and pop them out. Because of the LIFO order of the stack, you will get the letters in reverse order
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 formBracket Balancing - Check if brackets are balanced
Example:
(), (()), ()(), (((()))) → Balanced
)), ((), ((((()), ()()) → Not Balanced
Changing the bases, for example, decimal to binary - Convert decimal integer to binary
In browsers - The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack, and the previous URL is accessed
Undo Command: ctrl + z
Backtracking Procedure - Backtracking is one of the algorithm designing techniques. For that purpose, we dive into some way, if that way is not efficient, we come back to the previous state and go into some other paths. To get back from the current state, we need to store the previous state. For that purpose, we need a stack. Some examples of backtracking are finding the solution for the Knight Tour problem or N-Queen Problem etc.
Memory Management - Java, C++, Ada, FORTRAN, etc. (programming languages in which memory allocation occurs during compilation time, unlike python where it occurs during run time)
Call stack -
Programming languages use a data stack to execute code. When a function is called it is added to the call stack and removed once completed.
In recursion, a function is called inside the function. In such a situation, the current variables are pushed onto the system stack, where they wait for further execution and then the call to the inside function is made
Used in many algorithms - Tower of Hanoi, tree traversals, stock span problem, histogram problem
In Graph Algorithms - For example, Topological Sorting and Strongly Connected Components
Reference for Further Reading
Last updated
Was this helpful?