What Is a Stack?

Astack is adata structure that stores items in an Last-In/First-Out manner. This is frequently referred to as LIFO. This is in contrast to aqueue, which stores items in a First-In/First-Out (FIFO) manner.

It’s probably easiest to understand a stack if you think of a use case you’re likely familiar with: theUndo feature in 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 anAdd Function operation on it. After adding the function, you delete a word from a comment. This also gets added to the undo stack:

Notice how theDelete Word item is placed on top of the stack. Finally you indent a comment so that it’s lined up properly:

You can see that each of these commands are stored in an undo stack, with each new command being put at the top. When you’re working with stacks, adding new items like this is calledpush.

Now you’ve decided to undo all three of those changes, so you hit the undo command. It takes the item at the top of the stack, which was indenting the comment, and removes that from the stack:

Your editor undoes the indent, and the undo stack now contains two items. This operation is the opposite ofpush and is commonly calledpop.

When you hit undo again, the next item is popped off the stack:

This removes theDelete Word item, leaving only one operation on the stack.

Finally, if you hitUndo a third time, then the last item will be popped off the stack:

The undo stack is now empty. HittingUndo again after this will have no effect because your undo stack is empty, at least in most editors. You’ll see what happens when you call.pop() on an empty stack in the implementation descriptions below.

Implementing a Python Stack

There are a couple of options when you’re implementing a Python stack. This article won’t cover all of them, just the basic ones that will meet almost all of your needs. You’ll focus on using data structures that are part of the Python library, rather than writing your own or using third-party packages.

You’ll look at the following Python stack implementations:

• list
• collections.deque
• queue.LifoQueue

>>>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>", line1, in<module>IndexError:pop from empty list

Usingcollections.deque to Create a Python Stack

Thecollections module containsdeque, which is useful for creating Python stacks.deque is pronounced “deck” and stands for “double-ended queue.”

You can use the same methods ondeque as you saw above forlist,.append(), and.pop():

Python

>>>fromcollectionsimportdeque>>>myStack=deque()>>>myStack.append('a')>>>myStack.append('b')>>>myStack.append('c')>>>myStackdeque(['a', 'b', 'c'])>>>myStack.pop()'c'>>>myStack.pop()'b'>>>myStack.pop()'a'>>>myStack.pop()Traceback (most recent call last):  File"<console>", line1, in<module>IndexError:pop from an empty deque

This looks almost identical to thelist example above. At this point, you might be wondering why the Python core developers would create two data structures that look the same.

Why Havedeque andlist?

As you saw in the discussion aboutlist above, it was built upon blocks of contiguous memory, meaning that the items in the list are stored right next to each other:

This works great for several operations, like indexing into thelist. GettingmyList[3] is fast, as Python knows exactly where to look in memory to find it. This memory layout also allows slices to work well on lists.

The contiguous memory layout is the reason thatlist might need to take more time to.append() some objects than others. If the block of contiguous memory is full, then it will need to get another block, which can take much longer than a normal.append():

deque, on the other hand, is built upon a doubly linked list. In alinked list structure, each entry is stored in its own memory block and has a reference to the next entry in the list.

A doubly linked list is just the same, except that each entry has references to both the previous and the next entry in the list. This allows you to easily add nodes to either end of the list.

Adding a new entry into a linked list structure only requires setting the new entry’s reference to point to the current top of the stack and then pointing the top of the stack to the new entry:

This constant-time addition and removal of entries onto a stack comes with a trade-off, however. GettingmyDeque[3] is slower than it was for a list, because Python needs to walk through each node of the list to get to the third element.

Fortunately, you rarely want to do random indexing or slicing on a stack. Most operations on a stack are eitherpush orpop.

The constant time.append() and.pop() operations makedeque an excellent choice for implementing a Python stack if your code doesn’t use threading.

Remove ads

Python Stacks and Threading

Python stacks can be useful in multi-threaded programs as well, but if you’re not interested in threading, then you can safely skip this section and jump to the summary.

The two options you’ve seen so far,list anddeque, behave differently if your program has threads.

To start with the simpler one, you should never uselist for any data structure that can be accessed by multiple threads.list is not thread-safe.

deque is a little more complex, however. If you read the documentation fordeque, it clearly states that both the.append() and.pop() operations are atomic, meaning that they won’t be interrupted by a different thread.

So if you restrict yourself to using only.append() and.pop(), then you will be thread safe.

The concern with usingdeque in a threaded environment is that there are other methods in that class, and those are not specifically designed to be atomic, nor are they thread safe.

So, while it’s possible to build a thread-safe Python stack using adeque, doing so exposes yourself to someone misusing it in the future and causing race conditions.

Okay, if you’re threading, you can’t uselist for a stack and you probably don’t want to usedeque for a stack, so howcan you build a Python stack for a threaded program?

The answer is in thequeue module,queue.LifoQueue. Remember how you learned that stacks operate on the Last-In/First-Out principle? Well, that’s what the “Lifo” portion ofLifoQueue stands for.

While the interface forlist anddeque were similar,LifoQueue uses.put() and.get() to add and remove data from the stack:

>>>fromqueueimportLifoQueue>>>myStack=LifoQueue()>>>myStack.put('a')>>>myStack.put('b')>>>myStack.put('c')>>>myStack<queue.LifoQueue object at 0x7f408885e2b0>>>>myStack.get()'c'>>>myStack.get()'b'>>>myStack.get()'a'>>># myStack.get() <--- waits forever>>>myStack.get_nowait()Traceback (most recent call last):  File"<console>", line1, in<module>  File"/usr/lib/python3.7/queue.py", line198, inget_nowaitreturnself.get(block=False)  File"/usr/lib/python3.7/queue.py", line167, ingetraiseEmpty_queue.Empty

Unlikedeque,LifoQueue is designed to be fully thread-safe. All of its methods are safe to use in a threaded environment. It also adds optional time-outs to its operations which can frequently be a must-have feature in threaded programs.

This full thread safety comes at a cost, however. To achieve this thread-safety,LifoQueue has to do a little extra work on each operation, meaning that it will take a little longer.

Frequently, this slight slow down will not matter to your overall program speed, but if you’ve measured your performance and discovered that your stack operations are the bottleneck, then carefully switching to adeque might be worth doing.

I’d like to stress again that switching fromLifoQueue todeque because it’s faster without having measurements showing that your stack operations are a bottleneck is an example ofpremature optimization. Don’t do that.

Python Stacks: Which Implementation Should You Use?

In general, you should use adeque if you’re not using threading. If you are using threading, then you should use aLifoQueue unless you’ve measured your performance and found that a small boost in speed for pushing and popping will make enough difference to warrant the maintenance risks.

list may be familiar, but it should be avoided because it can potentially have memory reallocation issues. The interfaces fordeque andlist are identical, anddeque doesn’t have these issues, which makesdeque the best choice for your non-threaded Python stack.

Conclusion

You now know what a stack is and have seen situations where they can be used in real-life programs. You’ve evaluated three different options for implementing stacks and seen thatdeque is a great choice for non-threaded programs. If you’re implementing a stack in a threading environment, then it’s likely a good idea to use aLifoQueue.

You are now able to:

• Recognize when a stack would be a good data structure
• Select which implementation is right for your problem

If you still have questions, feel free to reach out in the comments sections below. Now, go write some code since you gained another tool to help you solve your programming problems!