How to Implement a Stack Using Deque in Python

A stack is a fundamental data structure that follows the Last-In, First-Out (LIFO) principle: the last element added is the first one removed. While you can implement a stack using a plain Python list, Python's collections.deque is specifically optimized for fast appends and removals from both ends, making it an excellent choice for stack implementations.

This guide covers both using the built-in collections.deque directly and building a custom stack class with a manually implemented deque.

Why Use deque Instead of a List?

Python lists support append() and pop() for stack operations, but they have a drawback: when the internal array needs to be resized, these operations can take O(n) time. A deque (double-ended queue) uses a doubly-linked list internally, guaranteeing O(1) time for both append and pop operations at either end.

Operation	List	Deque
append() (push)	O(1) amortized	O(1)
pop() (from end)	O(1) amortized	O(1)
pop(0) (from front)	O(n)	O(1)
Memory reallocation	Occasional	Never

Method 1: Using collections.deque Directly

The simplest approach is to use collections.deque as a stack with append() for push and pop() for pop:

from collections import deque

# Create a stack using deque
stack = deque()

# Push elements
stack.append(1)
stack.append(2)
stack.append(4)
print("Stack after pushes:", list(stack))

# Push another element
stack.append(5)
print("After push(5):", list(stack))

# Pop the top element
removed = stack.pop()
print(f"Popped: {removed}")
print("After pop:", list(stack))

# Peek at the top element (without removing)
top = stack[-1]
print(f"Top element: {top}")

# Check if stack is empty
print(f"Is empty: {len(stack) == 0}")
print(f"Size: {len(stack)}")

Output:

Stack after pushes: [1, 2, 4]
After push(5): [1, 2, 4, 5]
Popped: 5
After pop: [1, 2, 4]
Top element: 4
Is empty: False
Size: 3

Method 2: Stack Class Wrapping collections.deque

For a cleaner interface with proper stack terminology, wrap deque in a class:

from collections import deque


class Stack:
    """Stack implementation using collections.deque."""

    def __init__(self):
        self._container = deque()

    def push(self, item):
        """Add an item to the top of the stack."""
        self._container.append(item)

    def pop(self):
        """Remove and return the top item. Raises IndexError if empty."""
        if self.is_empty():
            raise IndexError("Pop from an empty stack")
        return self._container.pop()

    def top(self):
        """Return the top item without removing it."""
        if self.is_empty():
            raise IndexError("Top from an empty stack")
        return self._container[-1]

    def is_empty(self):
        """Return True if the stack is empty."""
        return len(self._container) == 0

    def size(self):
        """Return the number of items in the stack."""
        return len(self._container)

    def __repr__(self):
        return f"Stack({list(self._container)})"


# Usage
stack = Stack()

stack.push(1)
stack.push(2)
stack.push(4)
print(stack)

stack.push(5)
print(f"After push(5): {stack}")

removed = stack.pop()
print(f"Popped: {removed}")
print(f"After pop: {stack}")

print(f"Top: {stack.top()}")
print(f"Size: {stack.size()}")
print(f"Is empty: {stack.is_empty()}")

Output:

Stack([1, 2, 4])
After push(5): Stack([1, 2, 4, 5])
Popped: 5
After pop: Stack([1, 2, 4])
Top: 4
Size: 3
Is empty: False

Method 3: Custom Deque Implementation with a Doubly-Linked List

For educational purposes or environments where collections.deque is not available, here is a stack built on top of a custom doubly-linked list deque:

class Node:
    """A node in a doubly-linked list."""

    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None


class Deque:
    """Doubly-linked list implementation of a deque."""

    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    def is_empty(self):
        return self._size == 0

    def append(self, value):
        """Add to the end (tail)."""
        new_node = Node(value)
        if self.is_empty():
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self._size += 1

    def pop_last(self):
        """Remove and return the last element."""
        if self.is_empty():
            raise IndexError("Pop from empty deque")
        value = self.tail.value
        if self.head == self.tail:
            self.head = self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None
        self._size -= 1
        return value

    def peek_last(self):
        """Return the last element without removing."""
        if self.is_empty():
            raise IndexError("Peek from empty deque")
        return self.tail.value

    def size(self):
        return self._size

    def display(self):
        elements = []
        current = self.head
        while current is not None:
            elements.append(str(current.value))
            current = current.next
        return ' -> '.join(elements) if elements else '(empty)'


class Stack:
    """Stack implemented using a custom Deque."""

    def __init__(self):
        self._deque = Deque()

    def push(self, item):
        self._deque.append(item)

    def pop(self):
        return self._deque.pop_last()

    def top(self):
        return self._deque.peek_last()

    def is_empty(self):
        return self._deque.is_empty()

    def size(self):
        return self._deque.size()

    def display(self):
        print(f"Stack (bottom to top): {self._deque.display()}")


# Usage
stack = Stack()

stack.push(7)
stack.push(8)
stack.push(9)
stack.display()

popped = stack.pop()
print(f"Popped: {popped}")
stack.display()

print(f"Top: {stack.top()}")
print(f"Size: {stack.size()}")

Output:

Stack (bottom to top): 7 -> 8 -> 9
Popped: 9
Stack (bottom to top): 7 -> 8
Top: 8
Size: 2

Common Mistake: Popping from an Empty Stack

Calling pop() on an empty stack without checking first causes an error:

from collections import deque

stack = deque()

# WRONG: popping from an empty deque raises IndexError
try:
    stack.pop()
except IndexError as e:
    print(f"Error: {e}")

Output:

Error: pop from an empty deque

The correct approach: always check before popping, or use the wrapper class that provides a clear error message:

from collections import deque

stack = deque()

# CORRECT: check before popping
if stack:
    value = stack.pop()
else:
    print("Stack is empty, nothing to pop")

Output:

Stack is empty, nothing to pop

warning

Always check is_empty() or len(stack) > 0 before calling pop() or top(). Attempting these operations on an empty stack raises an IndexError.

Stack Operations Summary

Operation	Method (deque)	Method (class)	Time Complexity
Push	deque.append(item)	stack.push(item)	O(1)
Pop	deque.pop()	stack.pop()	O(1)
Peek/Top	deque[-1]	stack.top()	O(1)
Is Empty	len(deque) == 0	stack.is_empty()	O(1)
Size	len(deque)	stack.size()	O(1)

Which Approach to Use?

Approach	Best For
collections.deque directly	Quick scripts, simple use cases
Wrapper class around deque	Production code needing clear stack semantics and error handling
Custom linked-list deque	Learning data structures, interview practice, or restricted environments

For production Python code, wrapping collections.deque in a Stack class (Method 2) gives you the best combination of performance, clarity, and safety. The custom linked-list implementation (Method 3) is valuable for understanding how deques work internally but is not necessary for practical applications.