How to Implement a Python Stack

Read it in 15 Mins

Last updated on
08th Jun, 2022
Published
14th Aug, 2019
Views
9,278
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 of the programming languages including the operating systems are dependent on stack to function. 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. 

The name Stack data structure totally resembles a pile of objects, stack of papers, or a tower of blocks, where adding and removing of 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 and learn more about introduction to python programming and apply those skills and knowledge in the real world. 

In addition, read about Self in Python for more details.

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 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 in a similar fashion as 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 as 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 the other. If you wish to add a plate or remove one, 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, in order 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 top element of stack.
  • isEmpty: Returns true if stack is empty, else false.

Applications of Stack

Stacks are considered as 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 are 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 Backtracking like finding paths to a maze or exhaustive searching.
  • It is used in Algorithms like Tower of Hanoi, tree traversals, histogram problems and also in graph algorithms like Topological Sorting.

We recommend programmers with beginner and intermediate proficiency to learn advanced python in order to dive deeper into 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 which 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 have a clear understanding of 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, a 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 into an Underflow condition causing no effect.

Implementing Stack in Python

Python gives you a lot of options for implementing a Python stack. You can do so by using lists, tuples or by using third-party modules or packages. However, there are some basic implementations of Python stack that will fulfil 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, yet 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 in your stack.

Using Array

It is quite easy to implement stack using Python Lists. However, you can implement stack using arrays as well 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 Top
      • If yes, append data to stack and increase top by 1
      • If no, print stack full message
  4. Pop operation:
    • Check if Top is greater than 0:
      • If yes, pop the last element from the list and decrement top by 1
      • If no, print stack empty message
  5. Size operation: The size of the Stack is the value of the Top pointer.
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 of the deque class which is a double-ended queue that supports inserting and removing elements from either ends.

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 of 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.

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, there are other deque class methods that 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 that is specially designed to be fully thread-free.

Adding and removing elements are performed in this class are 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.

deque: An excellent choice for implementing a Python Stack

If you’re not interested in handling explicit locking and unlocking and also not looking for parallel processing support, then 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 working.

Operations like indexing and slicing work very well with lists because it is built upon contiguous blocks of memory. 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 the ends of the list. In this type of linked list, each memory has its own memory block. Thus, combining all these reasons, deque is a much better choice than list when implementing stacks in Python.

Conclusion

Let us sum up what we have learnt 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 depending 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.