For enquiries call:
+1-469-442-0620
HomeBlogProgrammingHow 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.
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.
The basic operations which are performed in the stack are mentioned below:
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 —
We recommend programmers with beginner and intermediate proficiency learn advanced Python in order to dive deeper into the Python stack.
There are mainly two types of primitive stack operations:
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:
Now, the word Delete is removed from any of the comments. This word also gets added to the stack:
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:
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.
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):
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:
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:
Since the stack is now empty, if we again hit undo, it will result in an Underflow condition causing no effect.
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 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.
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:
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.
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.
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
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.
Let us sum up what we have learned in this article so far:
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.
| Name | Date | Fee | Know more |
|---|
