Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Implementing a Stack Using Two Queues in Python

A stack stores items according to the last-in, first-out rule. The item added most recently is the first one removed, which makes stacks useful for undo operations, browser history, expression evaluation, depth-first search, and function-call management. Python developers normally reach for a list, but implementing a stack with two queues is a valuable exercise in data structures and interface design.

A queue has the opposite access pattern: first in, first out. Its front item leaves before newer items, so a queue does not directly provide the behaviour expected from a stack. The implementation must rearrange elements or delay that rearrangement until a removal is requested.

The phrase “implementing a stack using two queues in Python” describes a constraint rather than a practical replacement for list or collections.deque. The point is to preserve stack operations while restricting the internal representation to two queue-like objects. This reveals how abstract data types can be built from simpler primitives.

The examples below use collections.deque, whose append() and popleft() operations are efficient. This is suitable for Australian learners working on university assignments, coding interviews, or LeetCode-style problems, where the required interface matters as much as the final output.

Stack and queue behaviour

A stack exposes operations such as push, pop, top, and is_empty. A push places a value at the top, while a pop removes the top value. If values A, B, and C are pushed in that order, popping returns C, then B, then A.

A queue exposes enqueue and dequeue. Enqueuing A, B, and C produces removals in the same order: A, then B, then C. Since both structures can store a sequence of elements, the challenge is to transform queue order into stack order without accessing arbitrary positions.

There are two common designs. The first makes push expensive and keeps pop cheap. The second makes push cheap and moves elements during pop. Both are valid, and the best choice depends on the expected workload.

For a queue-based implementation, deque is preferable to repeatedly removing from the front of a Python list. Calling pop(0) on a list shifts the remaining elements and costs linear time, whereas popleft() is designed for efficient queue operations.

Choosing where the reordering happens

In the costly-push design, the newly added item is placed into an empty queue first. All existing items are then moved behind it. The queues are swapped, leaving the newest value at the front of the active queue. As a result, pop simply removes from the front.

Suppose the active queue contains [A, B]. To push C, place C in the other queue, then move A and B behind it. The new order is [C, A, B], which means the front behaves exactly like the top of a stack.

This approach gives constant-time pop and top, but push takes linear time because every existing item may be moved. It can be useful when a program performs many removals and relatively few insertions, such as a workload that consumes a prepared collection.

The costly-pop design leaves all newly inserted values in one queue. A pop operation moves every item except the final one into the second queue. The remaining item is the stack top, so it can be removed and returned. The queue roles are then exchanged.

A Python implementation

The following class uses the costly-push strategy. Only one queue holds values after each public operation, while the second queue temporarily stores elements during insertion. A private helper swaps the queue references rather than copying the containers.

from collections import deque


class StackWithTwoQueues:
    def __init__(self):
        self._active = deque()
        self._helper = deque()

    def push(self, value):
        self._helper.append(value)

        while self._active:
            self._helper.append(self._active.popleft())

        self._active, self._helper = self._helper, self._active

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from an empty stack")
        return self._active.popleft()

    def top(self):
        if self.is_empty():
            raise IndexError("top from an empty stack")
        return self._active[0]

    def is_empty(self):
        return not self._active

    def __len__(self):
        return len(self._active)

The push method first appends the new value to _helper. It then drains _active into _helper, so the latest value remains at the front. Swapping the references makes _helper the active queue and leaves the old queue empty and ready for the next operation.

top reads the first item without removing it. pop uses popleft() because the first queue element represents the stack top. Raising IndexError for an empty stack matches the behaviour of Python’s built-in list when pop() is called without an available item.

Testing the LIFO contract

A small test sequence checks the essential behaviour:

stack = StackWithTwoQueues()

stack.push("Sydney")
stack.push("Melbourne")
stack.push("Brisbane")

assert stack.top() == "Brisbane"
assert len(stack) == 3

assert stack.pop() == "Brisbane"
assert stack.pop() == "Melbourne"
assert stack.pop() == "Sydney"
assert stack.is_empty()

The values represent cities rather than abstract numbers, but the data type is irrelevant. A stack can contain strings, objects, lists, or custom records. In a practical Australian application, the same structure could track visited pages, undoable edits, or tasks entered during a morning commute.

Boundary cases deserve separate tests. Calling top or pop on a newly created stack should raise IndexError. Pushing duplicate values should preserve every occurrence, and pushing None should work because None is a valid Python value. Testing these cases prevents accidental reliance on truthiness or unique keys.

Property-based testing can compare the custom class with a normal Python list. For every randomly generated operation, perform append or pop on both structures and assert that the results agree. This is especially useful in coding interview preparation because it checks a long sequence of mixed operations rather than a single hand-picked example.

Complexity and memory analysis

With the costly-push implementation, push has O(n) time complexity when the stack contains n elements. Every existing element is transferred once. pop, top, and is_empty take O(1) time, and the class uses O(n) additional storage for the two queues.

The costly-pop design reverses the trade-off. Its push operation is O(1), while pop and usually top are O(n). If top is implemented by moving elements and then restoring them, it still needs linear work. This version is preferable when insertions dominate removals.

Across a long sequence of operations, the total cost can be described using amortised analysis. Neither design makes every operation constant time, but the chosen arrangement may be efficient for a particular pattern. A normal deque used directly as a stack provides O(1) insertion and removal, so the two-queue version is mainly educational or required by an external constraint.

Complexity analysis is part of the same broader skill used in graph algorithms. For example, when studying the reverse-delete algorithm, it is important to distinguish the cost of sorting edges from the cost of connectivity checks. Data structure choices influence those costs in both cases.

Alternative design with a costly pop

The second implementation keeps pushes simple and performs the rearrangement only when the top is requested or removed. The final element in the active queue is the stack top, so all earlier elements must be moved to the helper queue.

from collections import deque


class LazyStackWithTwoQueues:
    def __init__(self):
        self._first = deque()
        self._second = deque()

    def push(self, value):
        self._first.append(value)

    def pop(self):
        if not self._first:
            raise IndexError("pop from an empty stack")

        while len(self._first) > 1:
            self._second.append(self._first.popleft())

        value = self._first.popleft()
        self._first, self._second = self._second, self._first
        return value

    def top(self):
        if not self._first:
            raise IndexError("top from an empty stack")

        while len(self._first) > 1:
            self._second.append(self._first.popleft())

        value = self._first[0]
        self._second.append(self._first.popleft())
        self._first, self._second = self._second, self._first
        return value

The top method must restore the removed final item after inspecting it. If it failed to do so, observing the top would change the stack, violating the expected interface. This is a common implementation error: a read-only operation must preserve all values and their order.

A variation can maintain a separate top variable, making top constant time after each push. However, that adds bookkeeping and requires careful updates after every pop. The simplest implementation is often easier to verify, particularly in an assessment where correctness and clear invariants matter.

Invariants and related algorithms

An invariant is a condition that remains true after each public operation. For the costly-push version, the key invariant is that _active is ordered from stack top to stack bottom, while _helper is empty. For the costly-pop version, all values are in _first before an operation begins, and the queue roles are restored afterwards.

Writing the invariant in plain English before coding can expose design mistakes. It also helps explain why moving elements is necessary rather than treating the two queues as interchangeable storage bins. Similar reasoning appears in Kosaraju’s algorithm, where traversal order and the state of visited vertices must be preserved across passes.

Stacks themselves appear in depth-first search, syntax parsing, backtracking, and graph traversal. A stack made from queues is slower than a native stack, but it demonstrates that an abstract interface can survive even when its natural primitive is unavailable. This is a useful lesson in modular design: callers depend on operations, not internal representation.

The same principle applies to Python modules used in Melbourne software teams or university projects. A class can hide its storage policy, allowing the implementation to change from two queues to a deque later without changing code that calls push and pop.

Practical use and Python trade-offs

For production Python, collections.deque is generally the direct solution when both ends need efficient operations. A list is also an excellent stack because append() and pop() at the end are amortised O(1). Choosing two queues solely for real software would add movement and complexity without improving performance.

The exercise becomes more relevant when an interview specifies queues, when a teaching task limits available operations, or when a codebase exposes a queue-only abstraction. It also provides practice with encapsulation, exception handling, complexity analysis, and testable invariants.

A data-processing example could involve a small Australian retailer examining purchase sequences. The Apriori algorithm is designed for frequent itemset mining, while a stack might support parsing transaction rules or backtracking through candidate combinations. The algorithms have different purposes, but both rely on choosing operations that fit the data’s structure.

Local context can matter when designing such systems. A Sydney delivery service may process bursts around evening commuting hours, while a Brisbane or Perth retailer may batch events according to local warehouse schedules. If customer records are involved, Australian organisations also need to consider obligations under the Privacy Act 1988 and the Australian Privacy Principles. A clear data structure does not replace compliance, but predictable behaviour makes systems easier to audit and maintain.

The two-queue stack therefore works best as a compact demonstration of abstraction and trade-offs. Its core rule is simple: arrange the newest value at the removable end, either during push or during pop. Once that invariant is maintained, the queue-backed structure reliably behaves like a LIFO stack.