Choosing a Stack

Christopher Trudeau
Stacks and Queues: Selecting the Ideal Data Structure Christopher Trudeau 01:41
Recommended Tutorial Course Slides (.pdf) Sample Code (.zip) Ask a Question

A stack is a collection that stores arbitrary items in an order specified by Last-In/First-Out (LIFO) semantics. This means that the last item put into the stack is the first item available for removal from the stack. This is similar to a pile of lunch room trays – you access the most recent tray put on top first.

There is no native stack implementation in Python. Your choices for a stack are: using the built-in list type, the deque object from the collections library, or queue.LifoQueue.

Here are resources and additional documentation about deque, LifoQueue, and linked lists:

00:00 In the previous lesson, I showed you the deque and LifoQueue objects and how to use them as stacks. In this lesson, I’ll talk about how to choose between the different ways of getting a stack in Python. If you aren’t doing anything particularly complicated, just stick with a list. If you’re worried about performance, then it might be time to move up from a list to the deque object.

00:23 deque objects are more performant because they don’t have to pay the dynamic resizing cost. And it is equally performant no matter which end of the queue you are dealing with.

00:33 This, of course, brings up an interesting point. Technically, Python just doesn’t have a stack. Whether you’re using a list, deque, or something else, it is only your discipline as a coder that will make the object stack-like.

00:45 At any time, you can always cheat and get at things outside of LIFO order. Finally, if you’re doing multithreaded things, LifoQueue is thread-safe and the way to go. Thread locking requires additional overhead, though, so only use this in the multithreaded case.

01:02 Otherwise, you will pay performance penalties.

01:06 For further reading, the Python documentation is a good place to start. Here are the docs for deque and for LifoQueue.

01:17 If you’d like to know more about linked lists, this article is a good starting point. Or, if you want to dive deeper into concurrency, this course may be of interest.

01:26 If I recall correctly, the guide for this one is particularly handsome, witty, engaging, and… humble!

01:35 That’s all for stacks. Next up, I’ll start the section on queues with the FifoQueue.

Become a Member to join the conversation.