メインコンテンツにスキップ

Python Stack: Implementing LIFO Data Structures

Learn about LIFO principles, how to implement stacks in Python using lists, deque, and LifoDeque, and apply them for undo/redo systems or graph traversal.
· 15 分 読む

AIで探求

Every time you hit Ctrl+Z to undo a mistake, click the back button in your browser, or watch a recursive function unspool its results, you are relying on a stack. Because they are so deeply embedded in the software you use daily, you often interact with Stacks without even realizing it.

In this article, we’ll take a look at what a stack is, the core logic behind stacks, compare different implementation strategies using Python’s built-in libraries, and apply them to solve algorithmic problems.

I recommend taking our course on Writing Efficient Python Code to pair your data structure knowledge with performance best practices, and keeping the Python Basics Cheat Sheet handy as a quick reference. 

What Is a Stack in Python?

Before looking into code, it is important to understand the conceptual foundation that makes the Python stack such a powerful tool. Let’s take a look at the core principle behind stacks and see how they differ from other common data structures.

The LIFO data structure

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means the most recently added element is always the first one to be removed. Think of it like a stack of plates in a cafeteria. You place new plates on top and always pick up the topmost plate first. You never pull a plate from the middle or the bottom. Access is restricted entirely to the top.

python stack LIFO principle

This single constraint, top-only access, is what gives stacks their predictability and efficiency. Every element enters and exits through the same end, which keeps operations simple and fast.

One thing worth noting early on is that Python does not ship with a dedicated, primitive stack type the way some other languages do. There is no stack keyword or built-in class. Instead, Python offers robust built-in alternatives like lists, collections.deque, and queue.LifoQueue that can all behave as stacks. We will look at each of these implementations in detail later in the article.

Stack vs Other Data Structures

Understanding what a stack is becomes much clearer when you see what it is not. The two structures most commonly compared against stacks are queues and standard Python lists.

python stack vs list vs queue

Stack vs queue

A queue follows the First-In-First-Out (FIFO) principle, the opposite of a stack. In a queue, elements are added at the back and removed from the front, like a line of people waiting at a ticket counter. Stacks and queues are both linear and both restrict how you access elements, but they do so in opposite directions. 

Choosing the wrong one can silently break an algorithm's logic. For example, replacing a stack with a queue in a depth-first search would turn it into a breadth-first search, producing entirely different results.

Stack vs list

A standard Python list, on the other hand, provides random access. You can read, insert, or delete elements at any index using operations like my_list[3] or my_list.insert(2, value). This flexibility is useful in many contexts, but it also means there is nothing preventing you from accidentally accessing or modifying elements in the middle of the structure. 

When you are implementing an algorithm that depends on strict LIFO ordering, such as backtracking, syntax parsing, or undo functionality, the unrestricted nature of a list can introduce subtle bugs.

This is exactly why the restricted access pattern of a stack is a feature, not a limitation. By only allowing interaction with the top element, a Python stack enforces correctness by design. You cannot accidentally dequeue from the wrong end or overwrite an element buried deep in the structure. 

In algorithm design, constraints like these are what keep your logic clean and your code predictable.

Core Stack Operations and Time Complexity

Now that we understand what a Python stack is and how it differs from other structures, let's take a look at the fundamental operations that every stack supports and analyze how efficiently each one performs.

Standard stack operations

Every stack implementation is based on a small set of standard operations, regardless of the programming language. These are the building blocks you will use every time you work with a stack.

Push adds an element to the top of the stack. If the stack contains [A, B] and you push C, the stack becomes [A, B, C], with C now sitting on top.

Pop removes and returns the element currently at the top. Continuing the example above, popping from [A, B, C] returns C and leaves the stack as [A, B].

Peek (sometimes called top) lets you view the element at the top without removing it. This is useful when your logic needs to inspect the current top value before deciding whether to pop, a pattern that comes up frequently in expression parsing and balanced parentheses problems.

python stack
operations: Push, pop, peek

On top of those three core operations, two helper methods are important for writing safe, error-free stack code:

  • is_empty() checks whether the stack contains any elements. Calling pop or peek on an empty stack is a common source of runtime errors, so checking emptiness first is a defensive programming habit you should build early.

  • size() returns the current number of elements in the stack. This is helpful when you need to track how deep a recursion has gone or how many items still have to be processed.

Finally, it is worth defining a term you will encounter in textbooks and interviews: Stack Underflow. It is the error condition that occurs when you attempt to pop or peek from an empty stack. There is nothing to remove or view, so the operation is invalid. 

The exact exception or behavior this produces depends on the implementation. We will see how Python handles it concretely when we look at list, deque, and LifoQueue in the next section.

Analyzing complexity

One of the biggest reasons stacks are so widely used in algorithms is their efficiency. Let's break down the time and space complexity of each operation.

Push is O(1). In an efficient stack implementation, adding an element to the top is a constant-time operation. The stack does not need to shift or rearrange any existing elements. It simply places the new item at the end. This holds true for both collections.deque and, in the amortized case, Python's built-in list.

Pop is O(1). Removing the top element is equally fast. The stack accesses the last position directly, returns the value, and decrements its internal size tracker. Again, no shifting of other elements is required.

Peek is O(1). Viewing the top element without removal is a direct index lookup, making it constant-time as well.

Search is O(n). This is where stacks reveal their deliberate trade-off. If you need to find out whether a specific value exists somewhere in the stack, you have no choice but to scan through all n elements from top to bottom. 

Stacks are not designed for arbitrary lookups. They sacrifice search capability in exchange for fast, predictable push and pop. If your use case requires frequent searches, a different data structure, like a set or a dictionary, would be a better fit.

Space complexity is O(n). A stack holding n elements requires memory proportional to n. There is no hidden overhead beyond what is needed to store the elements themselves, plus a small constant for the structure's internal bookkeeping.

Here is a quick summary:

Operation

Time Complexity

Notes

Push

O(1)

Constant time. Amortized O(1) for Python lists

Pop

O(1)

Constant time

Peek

O(1)

Direct access to the top element

Search

O(n)

Must scan all elements

Space

O(n)

Linear in the number of stored elements

The key takeaway is that a Python stack is optimized for fast insertion and removal at one end. As long as you use it for what it is designed to do, like managing ordered, LIFO access, it delivers excellent performance. The moment you find yourself searching through a stack regularly, it is a signal to reconsider your choice of data structure.

Python Stack Implementations

With the theory and complexity analysis behind us, it is time to write actual code. Python offers three primary ways to implement a stack, each with its own strengths and trade-offs. Let’s walk through all three and see how to decide which one fits our use case.

Python stack using the built-in list

The most straightforward way to create a Python stack is with the built-in list. Since lists are dynamic arrays that support adding and removing elements from the end, they map naturally to stack behavior. 

The .append() method serves as a push, and .pop() without an argument removes and returns the last element. Let’s see this with a code example below:

# Creating a stack using a Python list
stack = []

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)

# Pop the top element
top = stack.pop()
print(top)
print(stack)

# Peek at the top element
print(stack[-1])
[10, 20, 30]
30
[10, 20]
20

This works well, but you need to handle the empty stack case carefully. In Python, both .pop() and stack[-1] raise an IndexError when the list is empty. This is how Python surfaces the Stack Underflow condition we defined earlier. 

The best practice is to wrap these calls in a try/except block or check emptiness before accessing the top, like in the following example:

# Handling Stack Underflow with try/except
stack = []

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty stack")

try:
    top = stack[-1]
except IndexError:
    print("Stack Underflow: cannot peek at an empty stack")

# Alternatively, check before accessing
if stack:
    top = stack.pop()
else:
    print("Stack is empty")
Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is empty

There is one performance nuance worth understanding. Python lists are backed by dynamic arrays. When you call .append(), the operation is usually instant O(1). However, when the internal array runs out of pre-allocated space, Python must allocate a new, larger block of memory and copy all existing elements over to it. 

This occasional reallocation makes .append() an amortized O(1) operation rather than a strict O(1). In practice, the delay is rare and brief, but in latency-sensitive or real-time applications, this unpredictability can matter.

Despite this caveat, .append() and .pop() on a list are the preferred approach for most simple stack tasks. The zero-import requirement, familiar syntax, and broad developer familiarity make it a good default choice, especially for scripting, prototyping, and interview problems where simplicity counts.

Python stack using collections.deque

If you need consistent O(1) performance without the occasional reallocation lag, collections.deque is the recommended upgrade. The name stands for "double-ended queue," but it works perfectly as a high-performance Python stack. Our earlier example looks like this with the deque syntax:

from collections import deque

# Creating a stack using deque
stack = deque()

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) 

# Pop the top element
top = stack.pop()
print(top)
print(stack)
 
# Peek at the top element
print(stack[-1])
deque([10, 20, 30])
30
deque([10, 20])
20

Notice that the interface is identical to the list-based approach. .append(), .pop(), and [-1] all work the same way. The IndexError behavior on empty access is also unchanged, so your error-handling code does not need any modification:

from collections import deque

stack = deque()

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty deque stack")
Stack Underflow: cannot pop from an empty deque stack

The critical difference is under the hood. A deque is implemented as a doubly-linked list of fixed-size blocks rather than a single array. This means it never needs to reallocate and copy the entire structure when it grows. 

Every .append() and .pop() is a true, guaranteed O(1) operation, not amortized, but consistent. For algorithm-heavy work where you are pushing and popping thousands or millions of times, this consistency adds up.

Python stack using queue.LifoQueue

Python's standard library also includes the queue.LifoQueue, a stack implementation designed specifically for multi-threaded programs. The "LIFO" in the name confirms it follows Last-In-First-Out ordering, but the interface and behavior are quite different from the previous two approaches. Let’s see this with a code example:

from queue import LifoQueue

# Creating a thread-safe stack
stack = LifoQueue()

# Push elements using .put()
stack.put(10)
stack.put(20)
stack.put(30)
print(stack.qsize())

# Pop the top element using .get()
top = stack.get()
print(top)
print(stack.qsize())
3
30
2

The first thing to notice is the syntax change. Push becomes .put(), and pop becomes .get(). This naming comes from the queue module's producer-consumer design pattern, where one thread "puts" items and another "gets" them.

There are two important behavioral differences to be aware of. 

First, LifoQueue has no safe peek method. There is no built-in way to view the top element without removing it. You could access internal attributes, but doing so in a multi-threaded context defeats the purpose of using a thread-safe class and risks race conditions.

Second, LifoQueue does not raise IndexError when you attempt to get from an empty stack. By default, .get() blocks. It pauses the calling thread and waits indefinitely until another thread puts an item onto the stack. If you want non-blocking behavior, you can pass block=False, which raises a queue.Empty exception instead. Let’s see this with an example:

from queue import LifoQueue, Empty

stack = LifoQueue()

# Non-blocking get raises Empty, not IndexError
try:
    stack.get(block=False)
except Empty:
    print("Stack is empty — no items to get")
Stack is empty — no items to get

Because of the internal locking mechanism that makes LifoQueue thread-safe, its operations carry more overhead than list or deque. This makes it a poor choice for single-threaded code. Use LifoQueue strictly when you have multiple threads producing and consuming data concurrently, and reach for deque or list in every other situation.

Selecting the right stack implementation in Python

With three options available, here is a side-by-side comparison to guide your decision:

Feature

list

collections.deque

queue.LifoQueue

Import required

No

Yes (collections)

Yes (queue)

Push method

.append()

.append()