What is a Stack?

A stack is a data structure that stores items in Last-In/First-Out manner. It is generally termed as LIFO. It is exactly opposite to a queue. A queue stores items in the pattern of First-In/First-Out (FIFO). It is easier to understand a stack with a very simple use case: the Undo option from your editor. Let’s imagine you’re editing a Python file so we can look at some of the operations you perform. First, you add a new function. This adds a new item to the undo stack:

You can see that the stack now has an Add Function operation on it. After adding the function, you delete a word from a comment. This also gets added to the undo stack:

Now, if you see carefully, the Delete Word is on the top of the stack. Next, you place Indent Comment, and you can notice that all items are lined up properly.

All the commands are kept in an undo stack. And, each command will have a new command placed on its top. Adding new commands or items while working on stacks is known as a push.

Once you decide to undo all three of these changes, you must hit the undo command. This will take the item on stack top, which is indenting the comment, and it is removed from the stack:

The undo stack will have two items when the editor undoes the indent. This method is quite opposite to push and it is known as pop.When you hit undo again, the next item is popped off the stack:

Now, the Delete Word is removed, which leaves a single operation on the stack.

In the end, once you hit Undo for the third time, the last item gets popped off the stack:

Finally, the undo stack is empty. If you hit the Undo once again, there won’t be any further impact since the stack itself is empty. Further in the next section, let’s understand what happens when you call .pop() on an empty stack.

Implementing a Python Stack

While Python stack implementation, a couple of options must be taken care of. Here, we are not touching one those aspects. However, we will understand only the basic ones which are mandatory for you to know and which also serve all your requirements. Python library consists of data structures. Instead of using third-party features or writing your own ones, you must focus on using these data structures directly available in the Python library. Let’s look at the Python stack implementations below:

• list
• deque
• LifoQueue

Using a list to Create a Python Stack

The built-in list structure that you likely use frequently in your programs can be used as a stack. Instead of .push(), you can use .append() to add new elements to the top of your stack, while .pop() removes the elements in the LIFO order:

>>>mystack = []

>>>mystack.append('a')

>>>mystack.append('b')

>>>mystack.append('c')

>>>mystack ['a','b','c']

>>>mystack.pop()
'c'
>>>mystack.pop()
'b'
>>>mystack.pop()
'a'
>>mystack.pop()

Traceback (most recent call last)

File"<console>",line 1, in <module>

IndexError: pop from empty list

The list will raise an IndexError in the final command when you call .pop() on an empty stack. the list has the advantage of being familiar. You know how it works and likely has used it in your programs already.

However, there are some shortcomings in the list when compared to some other data structures. The biggest issue is that it can run into speed issues as it grows.

The items stored in the list are done with an intention to provide quick access to random elements. This actually means that the items in the list are placed after one another in memory.

There have to be memory allocations done by Python if the stack becomes larger than the memory block which is currently holding it. You can use .append() which can take a bit longer. Another problem can also occur. If you use .insert() to add an element to your stack at a position other than the end, it can take much longer. In the next section, we will see the data structure which will help you to diminish the reallocation problems.

Creating a Python Stack with the help of collections.deque

Here, let’s understand how to create a Python stack. It is very evident that the collection module has .deque which is helpful in Python stack creation. And, .deque is also pronounced as ‘deck’ which means ‘double-ended queue’. As we did for the above list, .pop(), and .append(), the same method can be used on .deque:

>>>from collections import deque

>>>mystack  = deque()

>>>mystack = []

>>>mystack.append('a')

>>>mystack.append('b')

>>>mystack.append('c')

>>>mystack ['a','b','c']

>>>mystack.pop()
'c'
>>>mystack.pop()
'b'
>>>mystack.pop()
'a'
>>mystack.pop()

Traceback (most recent call last)

File"<console>",line 1, in <module>

IndexError: pop from empty list

This seems identical to the list example shown above. Here, you may be thinking, why actually did the Python developers even create two identical data structures?

Significance of deque and list?

As mentioned above, the list is built on contiguous memory blocks. This clearly shows the items existing in the list are placed next to one another. This helps many aspects such as indexing in the list.

As mentioned above, the list is built on contiguous memory blocks. This clearly shows the items existing in the list are placed next to one another. This helps many aspects such as indexing in the list.

Achieving myList[3] is a quick task since Python very well knows exactly how and where to search in the memory. The memory layout also enables slices to slog well on the list.

The contiguous memory layout is the reason that the list might need to take more time to .append() some objects than others. If the contiguous memory block is full, another block is obviously required, which takes more time than a normal .append():

On the other hand, .deque is built based on a doubly linked list structure. In this structure, each entry will be stored in its unique memory block. It will also have a reference to the next entry.

The doubly-linked list is also the same. The only difference being that each entry will have reference to both, next as well as to the previous entry. This easily enables the addition of nodes to either end of the list.

It’s very simple to add a new entry to a doubly-linked list. It just needs setting the new entry’s reference pointing to the current stack top and then vice versa.

Achieving myDeque[3] consumes less time than a list since Python must check all the nodes in the list. However, it is good that the operations like slicing on a stack of random indexing are done very rarely. Push and pop are the most common operation done on a stack.

The time is taken for operations like .pop() and .append() makes the deque a brilliant choice for executing a Python stack.

Related Blogs:

1. Brief Overview of Python Language
2. Python Career opportunities
3. Python Break Continue
4. Python Control Flow
5. Python Data Types
6. Python Dictionary
7. Python Exception Handling
8.  Python File
9. Python Functions
10. Python Substring
11. Hash Table and Hash Map in Python