How to Create a Python Stack

All programming languages provide efficient data structures that allow you to logically or mathematically organize and model your data. Most of us are familiar with simpler data structures like lists (or arrays) and dictionaries (or associative arrays), but these basic array-based data structures act more as generic solutions to your programming needs and aren’t really optimized for performance on custom implementations. There’s much more than programming languages bring to the table. 

By opting for more advanced data structures like stacks, linked lists, queues, etc., you can exercise more control over the behavior of the elements in your collection. This also allows you to make a conscious choice about which data operations you prefer to optimize pertaining to your application. 

One such efficient data structure is a stack - an abstract data type that stores a collection of elements with more strictly defined insertion and deletion rules. It is analogous to a stack of pancakes, where each pancake represents a data element. You can either eat (pop) a pancake at the top or add (push) one on top of it.

It is important for people starting out to understand the fundamentals of how your data is stored and structured to be able to make good design decisions, to be aware of prospective bottlenecks and to optimize performance.

Fortunately for us, programming languages like Python provide us with reusable implementations/interfaces that allow us to program advanced data structures like stacks without having to get our hands dirty in code. These interfaces allow us to get a basic understanding of how these structures can be realized and utilized for improving efficiency and performance.

In this post, we will look at what stacks are and understand more about them by comparing them with other familiar data structures. We’ll also look at the three different ways of implementing stacks using Python and discuss the nuts and bolts of each approach and the different situations in which each of them would make the right choice for your application.

Here’s what this guide will cover. Feel free to use the links below to skip ahead in the tutorial:

• What is a Stack in Computer Programming (Arrays vs Stacks)?
• How to Implement a Stack in Python
• Conclusion: Which Method to Use?
• When is the Best Time to Use Stacks?
• Start Stacking

What is a Stack in Computer Programming? 

To understand stacks better, first, let us look at the conventional lists or arrays that we use every day.

Arrays and their operations

Arrays are the simplest data structures out there. They allow you to store your data as a list of finite number n of elements that can be referenced by a corresponding set of n consecutive numbers, usually 0,1,2,3....n. 

Arrays are generally stored as contiguous blocks in memory. They allow you to fetch any element from the list at any time. 

You can insert any element, at any position you like, and most programming languages will take care of the under the hood memory allocation for you. 

Array insert operation

You can also remove any array element, from any position you like. 

We’re so used to this conventional way of manipulating arrays that we don’t consider the mechanics of internal memory processing that make this possible.

This level of flexibility in data manipulation in arrays comes at a cost. 

As your data grows bigger and bigger, seemingly straightforward operations like inserting and deleting can take a toll on performance if you’re not intelligent about how you store your data. For example, if your application requires you to store everything, but only keep track of the last (or first) element, then an array might be overkill; you might prefer another data structure that is faster at the operations that really matter for your application.

One such example of an advanced data structure is a stack.

Stacks

Imagine a stack of plates in a plate dispenser.

You can keep adding plates to the stack, but can ideally only pick out one (from the top) at a time. This is essentially what a stack data structure looks like. The plate dispenser/container is your stack, and the plates are your data elements. 

A stack is a data structure that follows the Last In First Out (LIFO) system, i.e. the element added at the last - the topmost one, is always the first to be taken out (or fetched). 

This also means that stacks do not allow you to access any other element other than the topmost one or the last one. Another thing about stacks is that they are traditional, bounded by a predefined capacity.

Stacks vs Queues

A good way to understand how stacks work is to contrast them with the First In First Out (FIFO) system based queue structures. In queues (like in real life queues of people), early entrants are dealt with first, on a first-cum-first-serve basis. In stacks, however, the more recent elements (the latest added) are processed before. 

In queues, insertion, and deletion take place at different ends (rear and front respectively), whereas in stacks, insertion and deletion take place on the same end.

Let us look at some of the operations we can perform on stacks.

Stack operations

PUSH ⤵️

In stack’s terminology, the operation of inserting elements is referred to as a push. This is equivalent to pushing/placing a plate on the top of the stack. 

The element pushed first takes the bottom-most (last from the top) position as we stack more elements. The second element to be added takes the second-last position from the top, and so on and so forth. Below is a representation of the stack and the corresponding push operations. The top-most element of the stack is marked in green.

POP ⤴️ 

Removing or deleting an element from the stack is known as pop operation. Since you only have access to the top-most element, the popped element is always the top one. The pop operation, obviously, only makes sense when the stack is not empty.

Access to only the top element allows stack data structures to be faster at insertion (push) and deletion (pop) operations. As far as time complexities are concerned, traditionally, stacks perform insertion and deletion in O (1) time, compared to O (n) for an array or list of size n. Therefore, for applications where you might need to access the elements in reverse order, or where you’d only need to deal with the top-most items  (and not any element from the data), stacks will serve you in better stead.

Stacks are widely used in programming paradigms, for language parsing (eg. keeping track of parentheses), for evaluating mathematical expressions, for arithmetic expression conversion (eg. infix to postfix conversion), and in maintaining call stacks for run-time memory management. 

Python Stack Data Structure 

Manually implementing stacks can be difficult in programming languages like C and C++. It’s a good thing that Python ships with a variety of in-built implementations that one can reuse to implement advanced data structures like stacks and queues. 

There is no explicit ‘stack’ data structure in Python, but it does provide various different classes that we can instantiate and use as stacks. We can easily leverage these in-built classes and their methods, instead of having to code it from scratch or having to rely on third-party solutions. 

Let us look at the different ways of emulating stacks in Python. 

How to Implement a Stack in Python

Stacks can be implemented in Python in three major ways -

1. Using list
2. Using collections.deque
3. Using queue.LifoQueue

Each of these methods has its own idiosyncrasies - some are better suited than others in certain situations. Let us look at what each of them have to offer.

Using list

Built-in Python lists are the simplest data structures at our disposal. We can use append() and pop() functions to add and remove elements at the end, allowing us to use these lists as stacks. 

Let’s see this through an example.

# Using lists to implement stacks in Python

stack = []

stack.append(19)    # push
stack.append(4)     # push
stack.append(0)     # push
stack.append(22)    # push
stack.append(15)    # push

print('Elements pushed. Stack state: ', stack)

print(stack.pop(), 'popped.')     # pop
print(stack.pop(), 'popped.')     # pop

print('Current stack state: ', stack)

Output:

In the above example, we pushed a bunch of elements into our stack and popped a few out. 

It would make more sense to view the output of the stack’s state from the right-hand side to the left (the rightmost element being the top of the stack) because elements pushed later take higher positions in the stack.

If you happen to perform the pop operation on an empty stack, you’ll encounter an IndexError, as shown below.

The primary advantage of using lists is that they are familiar to most users and are easy to use. Also, these list-based stacks are decently efficient (for the most part) as they allow push and pop operations in amortized (averaged over a sequence of operations) O(1) time. Therefore, they would work reasonably well for most small-scale personal projects that are less likely to scale. Also, an added benefit is that if you were to randomly access an element from your custom stack implementation, you can do so in O(1) time.

But there are caveats in this approach that are important to keep in mind.

For large-scale systems, naive list-based stacks can turn into intermittent bottlenecks for your application. The reason for this is that, in Python, lists are stored in memory as dynamic arrays. This is done by initially pre-allocating a certain amount of memory (contiguous blocks) to accommodate for prospective expansions of your list. As your project grows, every once in a while, your lists will want to expand beyond the capacity of the memory blocks that hold them. To make room for new elements, Python will need to sporadically allocate a larger memory to your list and move the existing elements to the new location. This can make certain append() operations take more time than usual.

As a result, this approach is not very consistent and scalable.

Let us look at a more promising way of implementing stacks in Python, that can circumvent the problem of memory allocation. 

Using collections.deque

Python’s collections module provides access to more advanced data structure implementations apart from the basic list, tuple, set, and dict types.

The deque (pronounced as ‘deck’) class of the collections module can also be used to implement stacks in Python and is considered to be a better alternative. 

Deque stands for a ‘double-ended queue’ that allows you to perform insert and delete operations from both ends.

Since stacks only require us to perform operations on the top-most elements, we can easily use the relevant deque functions (append() and pop()) for our use-case. Let us understand this through an example -

 # Using collections.deque to implement stacks in Python
from collections import deque # importing deque class
 
stack = deque() # initialising deque

stack.append(19)   # push to the top
stack.append(4)    # push to the top
stack.append(0)    # push to the top
stack.append(22)   # push to the top
stack.append(15)   # push to the top
print('Elements pushed. Stack state: ', stack)

print('Popping elements')
print(stack.pop(), 'popped.') # popped
print(stack.pop(), 'popped.') # popped

print('Current stack state: ', stack)

Output:

The best thing about deques is that they provide excellent O(1) performance for push and pop operations at both ends. 

This is because, under the hood, deques are implemented as doubly-linked lists. Even though these doubly-linked lists perform poorly for randomly accessing elements, they are highly optimized for insert and delete operations at both the ends of the list (even though we need to perform operations at only one end). 

And since you’re not likely to be accessing arbitrary elements from your stack at any time, using deque is perhaps the best solution for your custom stack implementation.

Let us look at one last approach of implementing stacks in Python.

Using queue.LifoQueue

If your project requires you to leverage the various aspects of multi-threaded processing and parallel computing, it is better to use the LifoQueue class of the queue module in Python to implement your stacks. This is because lists and deques are not thread-safe and are likely to lead to race conditions in multi-threaded settings.

If you do not require multiprocessing in your project, then you can perhaps skip this section and jump to the next one.

LifoQueue stands for a LIFO (Last In First Out) queue, which is basically what a stack is. 

Unlike the append() and pop() functions used in lists and deques, LifoQueues use put() and get() to perform the same data operations. 

Besides, LifoQueues also perform various other helpful utilitarian functions like providing stack size or element count (using maxsize()), and checking whether the stack is full or empty (full() or empty()). They also allow you to specify an upper limit on your stack’s capacity during initialization.

Let us understand how this can be done using an example.

# Using queue.LifoQueue to implement stacks in Python

from queue import LifoQueue # import class


stack = LifoQueue(maxsize = 3) # initialising object with max capacity 3

print('Stack capacity:', stack.maxsize) # display stack capacity
print('Stack element count:', stack.qsize()) # qsize() shows the number of elements

stack.put(19)  # push
stack.put(4)   # push
stack.put(0)   # push

print('Elements pushed ⤵️ ')

print("Stack full:", stack.full()) # to check if the stack is full
print("Stack element count:", stack.qsize()) 

print("Stack:", stack) # printing stack object (not contents)

print(stack.get(), 'popped ⤴️ ') # pop from top
print(stack.get(), 'popped ⤴️ ') # pop from top
print(stack.get(), 'popped ⤴️ ') # pop from top


print("Empty:", stack.empty()) # to check if the stack is empty

Output:

In this example, we saw how LifoQueues can also be used to provide extra information about the state of the stack and to impose restrictions on its capacity. 

If we try to use stack.get() on an empty stack, the LifoQueue based implementation will keep waiting until an element is added, which can then be popped. This has been shown in the example below - 

from queue import LifoQueue


stack = LifoQueue(maxsize = 3) # initialising with capacity 3

stack.put(19)  # push

print('Elements pushed ⤵️ ')

print(stack.get(), 'popped ⤴️ ') # pop

print("Empty:", stack.empty()) # to check if the stack is empty

print(stack.get(), 'popped ⤴️ ') # will keep on waiting

Output:

Depending on your use-case, this can be avoided by replacing the get() function with get_nowait() -

print(stack.get_nowait(), 'popped ⤴️ ')

This will result in an error since our stack is already empty.

Output:

Conclusion: Which method to use?

We looked at three different ways to implement stacks in Python. If we were to summarize our findings, it would be this -

If you’re looking for a quick, easy-to-use solution, and do not need to care about scaling your application, you can go ahead and use Python lists to implement stacks.

If you’re in this for the long run and are working on an application that is expected to grow and scale, the collections.deque class would be a more reliable and consistent alternative. Besides, the deque class uses the same functions for insertion (append()) and deletion (pop()). As a result, switching from lists to deques is practically very easy, and therefore, should definitely be considered. 

On the other hand, if you wish to utilize multi-threaded programming and parallel processing in your project, you might want to use the queues.LifoQueue class instead. This is because lists and deques are not completely thread-safe for your stack implementation, as opposed to LifoQueue, which is more specialized for multiprocessing.

When is the Best Time to Use Stacks?

As we discussed above, stacks can be used for a variety of purposes. They are usually required when you need to access the data elements in the reverse order that you put them in. 

When you are less likely to access random elements from the list and only care about manipulating elements from one end of the data structure, it is much better to use stacks as they are relatively faster at insert and delete operations ( O(1) time ). Stacks also allow developers to enforce a certain usage pattern on their data structures. For example, when debugging your application’s state, you can be more sure of the behavior of your data elements and not have to worry about random elements inserted in the middle of your list.

Stacks can also be used for performing operations on more advanced data structures like trees. For example, tree traversal using a depth-first walk can be implemented using stacks - every time you go down a branch from the trunk, you push an element into the stack; every time you move back up, you pop the respective element out.

Start Stacking

In this post, we looked at the fundamentals of the stack data structure - about what they are and about their relevant data operations (push and pop). We also looked at how stacks are different from basic data containers like arrays, and advanced ones like queues. 

We learned about the three different ways of implementing stacks in Python - using lists, collections.deque, and using queues.LifoQueue. We also looked at the different conditions in which each of these approaches would be the most appropriate for your use-case.

In the end, we discussed where it was important to prefer stacks over more generic data structures. We talked about how advanced data structures like stacks allow you to exercise more control over the behavior of your data elements and optimize the more important data operations for your application.

Now that you know about how easy it is to implement stacks in Python, think about which approach suits you best and go ahead and make your own stacks.

Stay healthy, stay safe, and keep learning! Happy coding!