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.

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 Python Programming and apply those skills and knowledge in the real world.

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.

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

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—

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 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:

Now, a 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 into an Underflow condition causing no effect.

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 is a built-in structure that can be used as 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:

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.

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:

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

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:

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

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():

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.

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’ve learnt in this article so far:

Stacks are simple data structures that allows 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 may also join the certification course on Python.

Research & References of How to Implement a Python Stack|A&C Accounting And Tax Services
Source

Share on Facebook

Tweet

Follow us