Stacks and Queues

You have probably stood in a line at a coffee shop, or hit “undo” a hundred times while writing an essay. Believe it or not, both of those everyday moments are basically data structures in disguise. In this guide, we will meet two of the most useful ones in programming: the Stack and the Queue. Then we will use what we learn to solve a classic problem: converting math expressions between infix, prefix, and postfix form.

What Is a Stack?

Imagine a stack of plates at a buffet. You can only do two things with that stack:

• Put a new plate on top
• Take a plate off from the top

You can never grab a plate from the middle or the bottom without removing everything above it first. That is exactly how a stack data structure works.

This behavior has a name: LIFO, which stands for Last In, First Out. The last plate you put down is the first one someone picks up.

Tip

Other places you have seen this pattern without realizing it:

• The “undo” button in a text editor (it undoes your most recent action first)
• Your browser’s back button (it takes you to the last page you visited)
• Function calls in your code (more on this later - it is called the “call stack”)

The Only Spot That Matters: The Top

In a stack, there is one special position called the top. Every single operation happens here.

Push sequence: 10, 20, 30

Top
 ↓
+----+
| 30 |
+----+
| 20 |
+----+
| 10 |
+----+

If you remove (pop) an item right now, 30 comes off first, since it was the last one added.

The Basic Things You Can Do With a Stack

Operation	What it does
push(x)	Adds x to the top
pop()	Removes and gives you the top item
peek() / top()	Shows you the top item, but does not remove it
isEmpty()	Tells you if the stack has nothing in it
isFull()	Tells you if the stack has run out of room (only matters for array-based stacks)

Building a Stack: A Few Different Ways

There is more than one way to build a stack. Let us walk through the common approaches, from the most basic to the most practical.

Using a Fixed-Size Array

This is the “from scratch” way of building a stack. You set up a list with a fixed size and keep track of where the top is using a number called top.

When the stack is empty, top starts at -1, because there is nothing there yet.

Initialize:
    top = -1
    size = N
    arr[size]

push(x):
    if top == size - 1:
        overflow (no more room!)
    top = top + 1
    arr[top] = x

pop():
    if top == -1:
        underflow (nothing to remove!)
    x = arr[top]
    top = top - 1
    return x

peek():
    if top == -1:
        error
    return arr[top]

Caution

Stack Overflow happens when you try to push onto a stack that is already full. There is simply no room left.

Stack Underflow happens when you try to pop from a stack that is already empty. There is nothing to remove.

These two words show up everywhere in interviews, so it is worth remembering: overflow = too full, underflow = too empty.

Here is what this looks like in actual Python code:

class Stack:
    def __init__(self, size):
        self.size = size
        self.arr = [None] * size
        self.top = -1

    def push(self, x):
        if self.top == self.size - 1:
            raise Exception("Stack Overflow")
        self.top += 1
        self.arr[self.top] = x

    def pop(self):
        if self.top == -1:
            raise Exception("Stack Underflow")
        x = self.arr[self.top]
        self.top -= 1
        return x

    def peek(self):
        if self.top == -1:
            raise Exception("Stack is Empty")
        return self.arr[self.top]

    def is_empty(self):
        return self.top == -1

Every operation here (push, pop, peek) takes the same amount of time no matter how big the stack is. In Big-O terms, that is O(1) for each one, and the whole stack takes up O(N) space in memory.

Using a Linked List

The problem with the array version above is that it has a fixed size. If you said the stack could hold 10 items and you try to push an 11th, you get an overflow error, even if your computer has plenty of free memory.

A linked list based stack fixes this. Instead of a fixed-size array, you build the stack out of nodes that point to each other, and you can keep adding nodes as long as your computer has memory available.

Top
 ↓
+------+    +------+    +------+
| 30   | -> | 20   | -> | 10   | -> None
+------+

• Pushing means adding a new node at the very front
• Popping means removing the front node

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.top = None

    def push(self, x):
        node = Node(x)
        node.next = self.top
        self.top = node

    def pop(self):
        if self.top is None:
            raise Exception("Stack Underflow")
        x = self.top.data
        self.top = self.top.next
        return x

    def peek(self):
        if self.top is None:
            raise Exception("Stack is Empty")
        return self.top.data

This still gives you O(1) push and pop, but now you never run out of room unless your computer’s memory itself runs out.

Just Use Python’s Built-In List

Here is the good news: in real projects, you almost never build a stack from scratch. Python’s regular list already behaves like a stack if you only use it from one end.

stack = []

stack.append(10)   # push
stack.append(20)
stack.append(30)

stack.pop()        # removes and returns 30
stack[-1]          # peek at the top, without removing it

Note

There is one rule to remember here: always add and remove from the end of the list using append() and pop(). Those are fast, O(1) operations.

But if you ever use insert(0, x) or pop(0) (adding or removing from the front), that becomes slow - O(N) - because Python has to shift every other item over by one spot. Avoid that for a stack.

Using deque

If you want to be extra safe and explicit, Python has a tool called deque (pronounced “deck”) that is built exactly for this kind of fast adding and removing.

from collections import deque

stack = deque()

stack.append(10)   # push
stack.append(20)

stack.pop()        # pop
stack[-1]          # peek

If someone in an interview asks you “list or deque for a stack?”, the honest answer is: a list works fine, but deque is considered cleaner and a bit safer, so many people reach for it by default.

The Hidden Stack Inside Your Code: The Call Stack

Here is something that might surprise you: every time you call a function, your program is secretly using a stack behind the scenes. It is called the call stack.

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

When you call fact(3), here is what happens to the call stack:

fact(3)
 -> fact(2)
   -> fact(1)
     -> fact(0)

Each call gets stacked on top of the previous one, and they only finish (and get removed) once the one above them is done. This is also why infinite recursion crashes your program:

def f():
    f()

f()  # RecursionError - this is a stack overflow!

The function keeps calling itself, adding more and more to the call stack, until there is no room left.

Real Problems People Solve With Stacks

Stacks are not just a theory exercise. They power some genuinely useful tools and show up constantly in coding interviews.

Checking Balanced Brackets

Ever wonder how your code editor knows you forgot to close a bracket? Stacks make that possible.

Input: "{[()]}"
Output: True (every bracket is properly closed)

The idea is simple:

• When you see an opening bracket, push it
• When you see a closing bracket, check if it matches the top of the stack, then pop

def is_valid(s):
    stack = []
    mp = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in mp.values():
            stack.append(ch)
        else:
            if not stack or stack.pop() != mp[ch]:
                return False

    return not stack

Finding the “Next Greater” Item (Monotonic Stack)

This pattern shows up a lot in interviews. The goal is to find, for each item in a list, the next item that is bigger than it - and to do it efficiently, without checking every pair.

It is used in problems like:

• Stock span (how many days in a row was the price lower than today?)
• Largest rectangle in a histogram
• Daily temperatures

Solving Postfix Math Expressions

Input: "23*54*+9-"

You scan left to right. Whenever you see a number, push it. Whenever you see an operator, pop the top two numbers, do the math, and push the result back. We will cover this expression stuff in detail later in this guide.

Min Stack (A Fun Twist)

This is a stack that can also tell you the smallest item in it, instantly, in O(1) time. The trick is to keep a second helper stack that tracks the minimum at each point.

Stack vs Queue: The Quick Comparison

Before we move to queues, here is a sneak peek at how they differ:

Stack	Queue
LIFO (Last In, First Out)	FIFO (First In, First Out)
Works from a single end	Works from two ends
Used in DFS (Depth First Search)	Used in BFS (Breadth First Search)

When a Stack Is NOT the Right Tool

• When you need to grab items in the middle of the data (stacks only let you touch the top)
• When you need “first come, first served” order (that is what a queue is for)

What Is a Queue?

Now picture a line of people waiting to buy movie tickets. The person who joined the line first gets served first. Nobody can cut in line and get served before the people ahead of them. That is a Queue.

This is called FIFO: First In, First Out.

Tip

Real-world queues you interact with constantly:

• A checkout line at a store
• Documents waiting to print
• Your computer’s CPU deciding which task to run next
• Messages waiting to be delivered over a network

Two Important Spots: Front and Rear

A queue has two ends that matter:

Front -> where elements leave the queue
Rear  -> where elements join the queue

Operation	Meaning
enqueue	Add an element at the rear
dequeue	Remove the element at the front
peek / front	Look at the front element
isEmpty	Check if the queue has nothing in it
isFull	Check if the queue has run out of room (array-based only)

One important rule: a queue never lets you insert or delete from the middle. Only the front and the rear matter.

Building a Queue: A Few Different Ways

A Basic Array

The simplest version keeps track of two index numbers: front and rear.

Initially:
front = -1
rear  = -1

Adding an item (enqueue):

if rear == capacity - 1:
    overflow
else:
    if front == -1:
        front = 0
    rear += 1
    arr[rear] = value

Removing an item (dequeue):

if front == -1 or front > rear:
    underflow
else:
    value = arr[front]
    front += 1

Caution

There is an annoying problem with this basic version: once you dequeue a few items, the spots at the beginning of the array become empty, but the queue never reuses them. Eventually you “run out of space” even though there is technically free room sitting unused at the front. The fix for this is the circular queue, coming up next.

The Circular Queue

A circular queue solves the wasted-space problem by treating the array like a loop. Once you reach the last slot, you wrap back around to the first one.

next_index = (index + 1) % capacity

Here is what it looks like visually. Notice the two empty slots at the front are still usable - they have not been wasted:

[ _ | _ | 30 | 40 | 50 ]
        ^            ^
      front         rear

Checking if it’s full:

front == (rear + 1) % capacity

Checking if it’s empty:

front == -1

Enqueue logic:

if (front == (rear + 1) % capacity):
    overflow
else:
    if front == -1:
        front = rear = 0
    else:
        rear = (rear + 1) % capacity
    arr[rear] = value

Dequeue logic:

if front == -1:
    underflow
else:
    value = arr[front]
    if front == rear:
        front = rear = -1
    else:
        front = (front + 1) % capacity

Using a Linked List

Just like with stacks, a linked-list based queue grows and shrinks freely, without ever needing to “wrap around” or worry about a fixed size.

Node:
    data
    next

Queue:
    front pointer
    rear pointer

Enqueue:

create new node
if rear is NULL:
    front = rear = new node
else:
    rear.next = new node
    rear = new node

Dequeue:

if front is NULL:
    underflow
else:
    temp = front
    front = front.next
    if front is NULL:
        rear = NULL

Both enqueue and dequeue here take O(1) time.

Python List

queue = []

queue.append(10)   # enqueue
queue.append(20)

queue.pop(0)       # dequeue, but this is slow!

The problem is pop(0). Removing the very first item of a Python list forces every other item to shift over by one position, which takes O(n) time. For small queues this barely matters, but it adds up fast in real applications.

Python’s deque

The name deque literally stands for Double-Ended Queue, and it is built exactly for this job.

from collections import deque

q = deque()

q.append(10)     # enqueue
q.append(20)

q.popleft()      # dequeue

Tip

Rule of thumb: Always reach for deque over a plain list when you need a queue in Python. It gives you O(1) speed on both ends, every time.

Different Flavors of Queues

Not every queue is the plain “first come, first served” kind. Here are the variations you will run into:

Simple Queue

The basic kind we just covered. Strict FIFO, one end for adding, one end for removing.

Circular Queue

Reuses freed-up space by wrapping around to the beginning of the array, instead of wasting it.

Priority Queue

Instead of “first in, first out,” items leave based on priority rather than the order they arrived in. The most important (or least important) item goes first, no matter when it was added.

Python gives you this through the heapq module:

import heapq

pq = []

heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 10)

heapq.heappop(pq)   # always returns the smallest value

This shows up in things like:

• Dijkstra’s shortest path algorithm
• Task scheduling
• “Top K” style problems (e.g., “find the 3 cheapest items”)

Deque (Double-Ended Queue)

A deque lets you add or remove from both ends, not just one.

dq.append(10)        # add to the right
dq.appendleft(20)    # add to the left
dq.pop()             # remove from the right
dq.popleft()         # remove from the left

This flexibility makes it perfect for things like sliding window problems, where you need to add and remove items from either side as a “window” moves across some data.

Monotonic Queue

A more advanced trick where you keep the queue’s elements always increasing or always decreasing. It looks intimidating but the core idea is simple: as new elements come in, you remove smaller (or larger) elements from the back that can no longer matter.

This is the secret behind problems like “Sliding Window Maximum.”

Where Queues Show Up in Real Code

Queues are everywhere once you start noticing them:

• Breadth First Search (BFS) - exploring a graph level by level
• CPU scheduling - deciding which task runs next
• Rate limiting - controlling how many requests get processed per second
• Producer-consumer systems - one part of a program creates work, another part processes it
• Level order traversal of trees
• Print spoolers - print jobs waiting their turn
• Network buffering - data packets waiting to be sent or received

Here is what a queue-powered BFS actually looks like in code:

from collections import deque

def bfs(graph, start):
    visited = set()
    q = deque([start])

    while q:
        node = q.popleft()
        if node not in visited:
            visited.add(node)
            for nei in graph[node]:
                q.append(nei)

Speed Cheat Sheet: Stack and Queue Implementations

Implementation	Enqueue / Push	Dequeue / Pop
Array	O(1)	O(1)
Circular Array	O(1)	O(1)
Linked List	O(1)	O(1)
Python list (as queue)	O(1)	O(n)
Python deque	O(1)	O(1)

The takeaway: deque is almost always your safest, fastest choice in Python, whether you are building a stack or a queue.

Now Let’s Put Stacks to Work: Expression Conversion

Here is something cool: stacks are the secret tool behind how calculators and compilers understand math expressions. Let us use everything we just learned about stacks to solve a classic problem - converting between infix, prefix, and postfix expressions.

First, Let’s Get the Basics Straight

Before converting anything, you need two pieces of math knowledge locked in.

Operator precedence (which operation happens first):

^        highest priority
*  /     medium priority
+  -     lowest priority

Associativity (which direction ties get resolved):

^         -> right associative (resolves right to left)
+ - * /   -> left associative (resolves left to right)

The Three Forms of an Expression

You have been using infix your whole life. It just means the operator sits between the two values, like in normal math class.

A + B
(A + B) * C

Prefix puts the operator before the values:

+ A B
* + A B C

Postfix puts the operator after the values:

A B +
A B C * +

Note

These might look like a strange way to write math, but they have a big advantage: computers can evaluate prefix and postfix expressions without ever needing to worry about brackets or precedence rules. That is exactly why calculators and compilers convert to one of these forms internally.

Converting Infix to Postfix

This is the most common conversion you will be asked to do, and it leans directly on a stack.

The general rule:

operand (a letter or number)    -> send straight to the output
operator                        -> push to the stack (after checking precedence)
(                               -> push to the stack
)                               -> pop everything until you hit a matching (

Let’s convert A + B * C step by step, very slowly so nothing is skipped:

Read	Stack	Output so far
A	empty	A
+	+	A
B	+	AB
*	+ *	AB
C	+ *	ABC
END	empty	ABC*+

Final postfix result:

ABC*+

Why does this make sense? Because * has higher precedence than +, the multiplication needs to happen first. Postfix naturally captures that: B C * means “multiply B and C first,” and then A gets added to that result.

B * C happens first
then A + (that result)

Converting Infix to Prefix

Caution

Do not try to convert infix straight to prefix in your head using some quick trick - it is very easy to mess up. Instead, always use the reverse method below. It feels indirect, but it is reliable.

The four-step recipe:

1. Reverse the infix expression
2. Swap every ( with ) and every ) with (
3. Convert that to postfix (using the method above)
4. Reverse the postfix result - that gives you prefix

Let’s convert (A + B) * C.

Step 1: Reverse the expression

C * ) B + A (

Step 2: Swap the brackets

C * ( B + A )

Step 3: Convert this to postfix

Converting C * (B + A) to postfix gives:

CBA+*

Step 4: Reverse that result

*+ABC

Final prefix result:

*+ABC

Quick sanity check: Reading * + A B C as “do the + on A and B first, then * that result with C” gives you back (A + B) * C. That matches what we started with, so we know the conversion worked.

Converting Prefix to Postfix

For this one, you read the expression from right to left, and use a stack to combine pieces as you go.

The pattern:

Prefix:  operator A B
Postfix: A B operator

Let’s convert *+ABC.

Read (right to left)	Stack
C	C
B	C, B
A	C, B, A
+	(A+B)
*	(A+B)*C

Final postfix result:

AB+C*

Converting Prefix to Infix

This works almost the same way as prefix to postfix, just scanning right to left and combining pieces with brackets instead.

The pattern:

Prefix: operator A B
Infix:  (A operator B)

Using the same expression, *+ABC:

Read (right to left)	Stack
C	C
B	C, B
A	C, B, A
+	(A+B)
*	(A+B)*C

Final infix result:

(A+B)*C

Converting Postfix to Infix

Now we flip directions: postfix gets read left to right.

The pattern:

Postfix: A B operator
Infix:   (A operator B)

Let’s convert AB+C*.

Read (left to right)	Stack
A	A
B	A, B
+	(A+B)
C	(A+B), C
*	(A+B)*C

Final infix result:

(A+B)*C

Converting Postfix to Prefix

Same left-to-right scan as above, but you build the prefix form instead of the infix form.

The pattern:

Postfix: A B operator
Prefix:  operator A B

Let’s convert AB+C*.

Read (left to right)	Stack
A	A
B	A, B
+	+AB
C	+AB, C
*	*+ABC

Final prefix result:

*+ABC

The Master Table (Worth Remembering)

From	To	How to do it
Infix	Postfix	Use a stack and check precedence
Infix	Prefix	Reverse, convert to postfix, reverse again
Prefix	Postfix	Scan right to left
Prefix	Infix	Scan right to left
Postfix	Infix	Scan left to right
Postfix	Prefix	Scan left to right

Quick Reference

Stack (LIFO)

Last In, First Out. You can only add or remove from the top. Think of a stack of plates.

Queue (FIFO)

First In, First Out. You add at the rear and remove from the front. Think of a line at a store.

Overflow / Underflow

Overflow = trying to add to something that is already full. Underflow = trying to remove from something that is already empty.

deque is your friend

For both stacks and queues in Python, collections.deque gives you fast, reliable O(1) operations on both ends.

Circular Queue

Solves the wasted-space problem of a basic array queue by wrapping back around to the start once the end is reached.

Expression Conversion

Infix is what you write by hand. Prefix and postfix are what computers prefer, since they skip the need for brackets and precedence rules.

Summary

The Core Idea

• A stack follows LIFO - last in, first out - and only touches one end (the top)
• A queue follows FIFO - first in, first out - and uses two ends (front and rear)
• Both can be built with arrays, linked lists, or Python’s built-in tools
• In Python, prefer deque over a plain list for both stacks and queues
• Infix, prefix, and postfix are three different ways to write the same math expression

Stack Highlights

• push, pop, peek, isEmpty are the core operations
• The call stack is a hidden stack that tracks your function calls
• Used for: balanced brackets, undo features, monotonic stack problems, evaluating postfix expressions
• Stack overflow = stack is full and you tried to push; underflow = stack is empty and you tried to pop

Queue Highlights

• enqueue, dequeue, front/peek, isEmpty are the core operations
• Circular queues fix the wasted-space problem of basic array queues
• Priority queues (via heapq) dequeue by importance, not arrival order
• Deques allow adding/removing from both ends - useful for sliding window problems
• BFS always uses a queue; DFS always uses a stack

Expression Conversion

• Infix to postfix: use a stack, respect precedence
• Infix to prefix: reverse, swap brackets, convert to postfix, reverse again
• Prefix conversions: always scan right to left
• Postfix conversions: always scan left to right
• Memorize the master table - it covers every direction you will ever be asked about