For enquiries call:

Phone

+1-469-442-0620

Aage ki Socho

HomeBlogProgrammingHow to Implement a Python Stack

How to Implement a Python Stack

Published
05th Sep, 2023
Views
view count loader
Read it in
15 Mins
In this article
    How to Implement a Python Stack

    Whether you want to reverse a string or create a language-processing application, stacks are very useful. It can be used to solve a wide variety of problems. In fact, most programming languages, including operating systems, are dependent on the stack to function. 

    The name Stack data structure totally resembles a pile of objects, a stack of papers, or a tower of blocks, where adding and removing items occur only at the top of the pile. It is similar to removing a quarter in the middle of a stack of coins without destroying the entire thing. In this article, we will understand stack operations and look into the various ways to implement stack in Python. You may also get certified, learn more about introduction to Python Programming, and apply those skills and knowledge in the real world. 

    So how do we implement a Python Stack? Let us take a closer look. To brush up your skills on sys.argv command line argument, click here. 

    What is a Stack?

    A Stack is an abstract linear data type that serves as a collection of objects. Unlike queues, they use the Last In First Out or LIFO  technique to insert and delete elements. The insert and delete operations are referred to as push and pop in the stack.

    Stacks and Queues are both linear collections of items. However, in a queue, the least recently added item is removed first, following the First In First Out or FIFO  manner. On the other hand, in a stack, the most recently added item is removed in the beginning following the LIFO

    Stack stores the data elements similar to a bunch of plates that are kept one above the other in a kitchen. It allows operations (push or pop) only from one end, often called a top. You can add or remove elements only from the top of the stack.

    A real-life example of a stack is a pile of heavy and precious plates; all kept on top of each other. If you wish to add or remove a plate, you can do that only from the top. However, if you want to remove a lower plate from the stack, you have to remove the topmost plates one by one to remove the desired one. Other examples are a deck of cards or a pile of books etc.

    What are the Basic Operations Performed in Stack?

    The basic operations performed in Stack are Push, POP and Peek
    Basic Operations performed in Stack - Push, POP, Peek
     
     

    The basic operations which are performed in the stack are mentioned below:

    • Push: Adds an item in the stack. Once the stack is full, it is said to be in an Overflow condition.
    • Pop: Removes an item from the stack. It follows a reversed order to pop items, similar to the way when items are pushed. It is said to be an Underflow condition.
    • Peek or Top: Returns the top element of the stack.
    • isEmpty: Returns true if the stack is empty, else false.

    Applications of Stack

    Stacks are considered the backbone of Data Structures. Most of the algorithms and applications are implemented using stacks.

    Some of the key applications of stacks are —

    • They are used to reverse a string. Each of the characters is pushed in and then popped off, which results in a reversed string.
    • It is used in Expression Evaluation and Expression Conversion (infix to postfix, infix to prefix, postfix to infix, prefix to infix).
    • It is used for forward and backward features in web browsers.
    • It is used for recursive parsing in Natural Language Processing.
    • It is used in syntax parsing and parenthesis checking.
    • It is used for Backtrackings like finding paths to a maze or exhaustive searching.
    • It is used in Algorithms like the Tower of Hanoi, tree traversals, histogram problems, and also in graph algorithms like Topological Sorting.

    We recommend programmers with beginner and intermediate proficiency learn advanced Python in order to dive deeper into the Python stack.  

    Understanding Stack Operations

    There are mainly two types of primitive stack operations:

    • Push: It is performed to insert and store an element in the stack. However, when you try to insert an element in a stack that is full, the Overflow condition occurs.
    • Pop: It is used to remove an element from the stack. However, when the stack is empty, the Underflow condition occurs.

    Push

    Let’s consider editing a Python file using the undo feature in your editor so you can clearly understand the stack operations. At first, a new function called Insert is added. The push operation adds the Insert function into the stack:

    Insert function into the stack using push operation
     

    Now, the word Delete is removed from any of the comments. This word also gets added to the stack:

    adding delete word to the stack by push operation

    The Delete is added to the top of the stack. Finally, let us indent a Comment to align things appropriately, which is also inserted into the stack:

    Indenting "comment" to the stack using Push operation

    Note that the commands entered are all stored in the stack, just like a pile, with each command on top of the other. This operation of adding new elements into the stack is called push.

    Pop

    Now to perform the pop operations, let us make use of the undo feature. When we first hit the undo, it removes the top-most element of the stack (here, which is Comment):

    First undo removes the top-most element of the stack

    The editor removes the indented Comment and the stack is now left with two commands. When the next undo is hit again, the next command is removed from the stack:

    The next undo will remove the next command from the stack, which is called POP operation

    Now Delete is also removed, and the stack is left with only one operation. When the undo is hit again, the last element remaining in the stack is also popped off, and the stack becomes empty as it was in the first place:

    The last undo will remove the last element of the stack and the stack becomes empty. This removal of elements from a stack is called POP operation

    Since the stack is now empty, if we again hit undo, it will result in an Underflow condition causing no effect.

    Implementing Stack in Python

    Now we'll learn how to implement a python stack. Python gives you a lot of options for implementing a Python stack. You can do so by using lists, and tuples or by using third-party modules or packages. However, there are some basic implementations of Python stack that will fulfill most of your needs.

    Some of those implementations are as follows:

    • list
    • collections.deque
    • queue.LifoQueue

    Using List

    List is a built-in structure that can be used as a stack in Python. We use lists often to write Python programs. They are implemented as internal dynamic arrays in Python, which means whenever elements are added or removed, the storage area is resized every time accordingly.

    You can use .append() to add elements and .pop() to remove them:

    >>> my_first_stack = []
    >>> my_first_stack.append('Alex')
    >>> my_first_stack.append('Bob')
    >>> my_first_stack.append('Charlie')
    >>> my_first_stack
    ['Alex', 'Bob', 'Charlie']
    >>> my_first_stack.pop()
    'Charlie'
    >>> my_first_stack.pop()
    'Bob'
    >>> my_first_stack.pop()
    'Alex'
    >>> my_first_stack.pop()
    Traceback (most recent call last):
      File "<#pyshell>", line 1, in <module>
    IndexError: pop from empty list

    Notice that an IndexError is raised. This is because .pop() is called on an empty stack.

    Though lists work very efficiently in implementing stacks, it comes with some drawbacks. There might be situations where your stack might grow bigger than the current block of memory it holds. Since lists are used for faster access to random elements, in such situations, speed issues occur. Python starts allocating memory implicitly, which leads to longer .append() calls.

    Speed issues also occur when you use .insert() to add elements to your stack.

    Using Array

    It is quite easy to implement a stack using Python Lists. However, you can also implement stack using arrays if you assume that lists are like arrays. You can follow the algorithm mentioned below to understand how it works.

    Algorithm:

    1. Declare a list and an integer MaxSize, and denote the maximum size of the Stack
    2. Initially, set the Top to 0.
    3. Push operation:
      • Check if the MaxSize of the Stack is greater than the Top
        • If yes, append data to stack and increase the top by 1
        • If no, print stack full message
    4. Pop operation:
      • Check if the Top is greater than 0:
        • If yes, pop the last element from the list and decrement the top by 1
        • If no, print stack empty message
    5. Size operation: The Stack's size is the Top pointer's value.
    class Stack:
        #Constructor
        def __init__(self):
            self.stack = list()
            self.maxSize = 8
            self.top = 0
        #Adds element to the Stack
        def push(self,data):
            if self.top>=self.maxSize:
                return ("Stack Full!")
            self.stack.append(data)
            self.top += 1
            return True
        #Removes element from the stack
        def pop(self):
            if self.top<=0:
                return ("Stack Empty!")
            item = self.stack.pop()
            self.top -= 1
            return item
           
        #Size of the stack
        def size(self):
            return self.top
    
    s = Stack()
    print(s.push(1))#prints True
    print(s.push(2))#prints True
    print(s.push(3))#prints True
    print(s.push(4))#prints True
    print(s.push(5))#prints True
    print(s.push(6))#prints True
    print(s.push(7))#prints True
    print(s.push(8))#prints True
    print(s.push(9))#prints Stack Full!
    print(s.size())#prints 8      
    print(s.pop())#prints 8
    print(s.pop())#prints 7
    print(s.pop())#prints 6
    print(s.pop())#prints 5
    print(s.pop())#prints 4
    print(s.pop())#prints 3
    print(s.pop())#prints 2
    print(s.pop())#prints 1
    print(s.pop())#prints Stack Empty!

    Note: Element 9 was not added, and hence size remains 8.

    Using collections.deque

    Python contains a module named collections. This comprises the deque class, which is a double-ended queue that supports inserting and removing elements from either end.

    The method of deque is similar to the lists:

    >>> from collections import deque
    >>> my_first_stack = deque()
    >>> my_first_stack.append('Alex')
    >>> my_first_stack.append('Bob')
    >>> my_first_stack.append('Charlie')
    >>> my_first_stack
    deque(['Alex', 'Bob', 'Charlie'])
    >>> my_first_stack.pop()
    'Charlie'
    >>> my_first_stack.pop()
    'Bob'
    >>> my_first_stack.pop()
    'Alex'
    >>> myStack.pop()
    Traceback (most recent call last):
      File "<#pyshell>", line 1, in <module>
    IndexError: pop from an empty deque

    The objects of the deque class have a consistent performance because they are implemented in the form of doubly linked lists.

    Using queue.LifoQueue

    The Python Standard Library comprises another class called queue.LifoQueue class to implement stack. It supports multiple simultaneous producers and consumers.

    Python Threading is used for executing multiple tasks, and function calls at the same time and independently of other codes. If your program involves threads, it is recommended not to use list and deque because they behave very differently in such cases.

    The list is not thread-safe. On the other hand, though .append() and .pop() are atomic in nature, it is nearly impossible to build a Python stack using deque that is fully thread-safe. This is because of the reason that in a threaded environment, other deque class methods are neither atomic nor they are thread-safe and might lead to race conditions.

    So the last option we’re left with is the queue.LifoQueue class is specially designed to be fully thread-free.

    Adding and removing elements are performed in this class using .put() and .get():

    >>> from queue import LifoQueue
    >>> my_first_stack = LifoQueue()
    >>>my_first_stack.put('Alex')
    >>>my_first_stack.put('Bob')
    >>>my_first_stack.put('Charlie')
    >>> my_first_stack
    <queue.LifoQueue object at 0x0000026E4C69DFD0>
    >>> my_first_stack.get()
    'Charlie'
    >>> my_first_stack.get()
    'Bob'
    >>> my_first_stack.get()
    'Alex'
    >>> my_first_stack.get_nowait()
    Traceback (most recent call last):
      File "<pyshell#8>", line 1, in <module>
        my.get_nowait()
    _queue.Empty
    >>> my_first_stack.get()  # Waits forever

    The queue module might be helpful when you are working with multiple threads or with parallel computing. However, for general-purpose stack implementation, it is recommended to use lists or deque.

    Top Cities Where KnowledgeHut Conduct Python Certification Course Online

    Python Course in BangalorePython Course in ChennaiPython Course in Singapore
    Python Course in DelhiPython Course in DubaiPython Course in Indore
    Python Course in PunePython Course in BerlinPython Course in Trivandrum
    Python Course in NashikPython Course in MumbaiPython Certification in Melbourne
    Python Course in HyderabadPython Course in KolkataPython Course in Noida

    Deque: An Excellent Choice for Implementing a Python Stack

    Suppose you’re not interested in handling explicit locking and unlocking and also not looking for parallel processing support. In that case, your choice for choosing the right Python stack implementation narrows down to list and deque. However, they both have different implementations of data structures in their work.

    Operations like indexing and slicing work very well with lists because they are built upon contiguous memory blocks. The elements in the list are stored in a dynamic array system making it easier for Python to find any element in the memory.

    However, this type of layout system raises speed issues in situations like when the contiguous block is full; it needs to get another block which in turn increases the execution time.

    On the other hand, deque is a doubly linked list in which each entry is linked to both the previous and next entry in the list. This allows adding elements to both ends of the list. In this type of linked list, each memory has its own memory block. Thus, combining all these reasons, the deque is a much better choice than the list when implementing stacks in Python.

    Conclusion

    Let us sum up what we have learned in this article so far:

    • What is a Stack, and what are its applications.
    • What do Stack operations look like?
    • When should a data structure like Stack be used?
    • Different ways of implementing Stack in Python.
    • How to select the right implementation depends upon your problem.

    Stacks are simple data structures that allow us to store and retrieve data in a sequential fashion. They are very useful in real-world cases. Having a clear understanding of stacks would help us in solving data storage problems in an efficient manner.

    If you wish to know more about data structures and other aspects of Python, you can go through the Python tutorial. You might want to join the Knowledgehut introduction to Python Programming course on Python.

    Profile

    Priyankur Sarkar

    Data Science Enthusiast

    Priyankur Sarkar loves to play with data and get insightful results out of it, then turn those data insights and results in business growth. He is an electronics engineer with a versatile experience as an individual contributor and leading teams, and has actively worked towards building Machine Learning capabilities for organizations.

    Share This Article
    Ready to Master the Skills that Drive Your Career?

    Avail your free 1:1 mentorship session.

    Select
    Your Message (Optional)

    Upcoming Programming Batches & Dates

    NameDateFeeKnow more
    Course advisor icon
    Course Advisor
    Whatsapp/Chat icon