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?

1. A pointer called TOP is used to keep track of the top element in the stack.

2. When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1.

3. On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP.

4. On popping an element, we return the element pointed to by TOP and reduce its value.

5. Before pushing, we check if the stack is already full

6. 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 well

Using 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 operation

Using 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 form

  • Explanation: https://bradfieldcs.com/algos/stacks/infix-prefix-and-postfix-expressions/
• Bracket Balancing - Check if brackets are balanced

  Example:

  • (), (()), ()(), (((()))) → Balanced

  • )), ((), ((((()), ()()) → Not Balanced

  • Explanation: https://bradfieldcs.com/algos/stacks/balanced-parentheses/
• Changing the bases, for example, decimal to binary - Convert decimal integer to binary

  • Explanation: https://bradfieldcs.com/algos/stacks/converting-number-bases/
• 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

Stack in Python | What is Python Stack and how to Implement it | EdurekaEdureka

Using the Stack Data Structure in Python | Engineering Education (EngEd) Program | SectionEngineering Education (EngEd) Program | Section

How to Implement a Python Stack – Real Pythonrealpython