Stack and Queue Implementation Guide

1. Introduction

Stacks and queues are two of the most fundamental data structures in computer science. They appear simple at first glance, but they power many critical systems—from function call management in programming languages to large-scale messaging systems.

If you’ve ever used the undo button in a text editor, navigated browser history, or seen how tasks are processed in a server queue, you’ve already encountered stacks and queues in action.

Understanding these structures is essential for:

• mastering Data Structures and Algorithms (DSA)

• solving coding interview problems

• writing efficient real-world software systems

A stack follows the Last In, First Out (LIFO) principle. The last element added is the first one removed.

A queue follows the First In, First Out (FIFO) principle. The first element added is the first one removed.

Although Python provides built-in tools for stacks and queues, interviews and advanced engineering roles often expect you to understand how these structures work internally.

In this guide, you will learn:

1. Step 1: how stacks and queues work conceptually
2. Step 2: how to implement them from scratch
3. Step 3: how to optimize them using arrays and linked lists
4. Step 4: how Python’s built-in tools improve performance
5. Step 5: how these structures appear in real coding interview problems

By the end of this article, you will not only know how to use stacks and queues, but also how to build them yourself and analyze their performance.

2. Why Stacks and Queues Matter

Many beginners treat stacks and queues as simple textbook topics. In reality, they appear everywhere in modern computing systems.

Understanding them deeply helps you recognize patterns in algorithm problems and design efficient systems.

2.1 Core Building Blocks of Algorithms

Many algorithm techniques depend directly on stacks and queues.

Examples include:

• Depth-First Search (DFS) → uses a stack

• Breadth-First Search (BFS) → uses a queue

• Backtracking algorithms → rely on stacks

• Monotonic stack problems → common in interviews

• Sliding window techniques → often use deque structures

Without understanding stacks and queues, these patterns become difficult to implement.

2.2 Essential for Coding Interviews

Stacks and queues appear frequently in coding interview platforms like LeetCode, HackerRank, and CodeSignal.

Common interview problems include:

• Valid Parentheses

• Next Greater Element

• Min Stack

• Daily Temperatures

• Binary Tree Level Order Traversal

Interviewers often test whether you understand:

• LIFO vs FIFO behavior

• how to implement these structures efficiently

• time and space complexity of operations

2.3 Real Systems Depend on Them

Stacks and queues are not just academic concepts—they power real software systems.

Stacks power:

• function call management in programming languages

• recursion

• undo/redo systems

• expression evaluation in compilers

Queues power:

• task scheduling

• printer job management

• messaging systems

• event processing pipelines

• asynchronous job workers

For example, large-scale systems like message brokers process tasks using queue-based architectures.

2.4 Understanding Performance Trade-offs

When implementing stacks and queues, engineers must choose between different underlying data structures:

• Arrays

• Linked lists

• Circular buffers

• Double-ended queues

Each approach has different trade-offs in:

• memory usage

• cache efficiency

• resizing overhead

• pointer management

A strong engineer understands when to use each approach.

class ArrayStack:
  def __init__(self):
  self._data = []  # Internal list to store elements
  def push(self, item):
  """Add item to the top."""
  self._data.append(item)
  def pop(self):
  """Remove and return the top item."""
  if self.is_empty():
  raise IndexError("Pop from empty stack")
  return self._data.pop()
  def peek(self):
  """Return top item without removing."""
  if self.is_empty():
  raise IndexError("Peek from empty stack")
  return self._data[-1]
  def is_empty(self):
  """Check if stack is empty."""
  return len(self._data) == 0
  def size(self):
  return len(self._data)

💡 Pro Tip: Always handle empty cases. Raising IndexError is standard, but in real apps, you might return None or a default value.

 

3.2 Stack Using Linked List  

Why learn linked list implementation? Interviews love it, and it shows you understand memory allocation without resizing overhead.

Each node holds data and a pointer to the next node.

class Node:
  def __init__(self, value):
  self.value = value
  self.next = None
  class LinkedListStack:
  def __init__(self):
  self.head = None
  self._size = 0
  def push(self, item):
  """Add item to top (head)."""
  new_node = Node(item)
  new_node.next = self.head
  self.head = new_node
  self._size += 1
  def pop(self):
  """Remove and return top item."""
  if self.is_empty():
  raise IndexError("Pop from empty stack")
  value = self.head.value
  self.head = self.head.next
  self._size -= 1
  return value
  def peek(self):
  if self.is_empty():
  raise IndexError("Peek from empty stack")
  return self.head.value
  def is_empty(self):
  return self.head is None
  def size(self):
  return self._size

Time Complexity: All operations are O(1)—constant time. No loops needed.

3.3 Queue Using Array (with Wrap-Around)  

Queues are First In, First Out (FIFO) . Like a line at the DMV—the first person in line gets served first.

Simple list implementation fails because pop(0) is O(n)—shifting all elements left. We need a circular queue .

class ArrayQueue:
  """Circular queue using fixed-size list."""
  def __init__(self, capacity=10):
  self._data = [None] * capacity
  self._front = 0
  self._size = 0
  self._capacity = capacity
  def enqueue(self, item):
  """Add item to the back."""
  if self._size == self._capacity:
  self._resize(2 * self._capacity)
  back = (self._front + self._size) % self._capacity
  self._data[back] = item
  self._size += 1
  def dequeue(self):
  """Remove and return front item."""
  if self.is_empty():
  raise IndexError("Dequeue from empty queue")
  value = self._data[self._front]
  self._data[self._front] = None  # Help garbage collection
  self._front = (self._front + 1) % self._capacity
  self._size -= 1
  return value
  def first(self):
  if self.is_empty():
  raise IndexError("Empty queue")
  return self._data[self._front]
  def is_empty(self):
  return self._size == 0
  def _resize(self, new_capacity):
  """Resize when full."""
  old_data = self._data
  self._data = [None] * new_capacity
  for i in range(self._size):
  self._data[i] = old_data[(self._front + i) % self._capacity]
  self._front = 0
  self._capacity = new_capacity

The modulo operator % creates the wrap-around effect. When back exceeds capacity, it cycles to index 0 if empty.

3.4 Queue Using Linked List  

Linked lists shine here—no wrap-around needed, just head and tail pointers.

class LinkedListQueue:
  def __init__(self):
  self.head = None
  self.tail = None
  self._size = 0
  def enqueue(self, item):
  """Add to back (tail)."""
  new_node = Node(item)
  if self.is_empty():
  self.head = new_node
  self.tail = new_node
  else:
  self.tail.next = new_node
  self.tail = new_node
  self._size += 1
  def dequeue(self):
  """Remove from front (head)."""
  if self.is_empty():
  raise IndexError("Dequeue from empty queue")
  value = self.head.value
  self.head = self.head.next
  if self.head is None:  # Queue becomes empty
  self.tail = None
  self._size -= 1
  return value
  def first(self):
  if self.is_empty():
  raise IndexError("Empty queue")
  return self.head.value
  def is_empty(self):
  return self.head is None
  def size(self):
  return self._size

All operations O(1). No resizing overhead.

 

Ready to go deeper? Join our expert sessions to practice implementing these with real-time feedback.

 

3.5 Python Built-in Optimizations  

Don’t reinvent the wheel in production. Python gives you powerful tools.

Stack with List (Simple)  

stack = []
  stack.append(1)   # push
  stack.append(2)
  top = stack.pop()  # 2

Queue with collections.deque  

deque (double-ended queue) is optimized for fast appends and pops from both ends.

from collections import deque
  queue = deque()
  queue.append(1)          # enqueue to right
  queue.append(2)
  front = queue.popleft()  # 1 (dequeue from left)
  stack = deque()
  stack.append(1)          # push to right
  top = stack.pop()        # pop from right (LIFO)

 

💡 Pro Tip: Use deque over list for queues. list.pop(0) is O(n); deque.popleft() is O(1).

 

queue Module (Thread-Safe)  

For multithreading, use queue.Queue.

from queue import Queue
  q = Queue()
  q.put(1)
  item = q.get()

3.6 Time & Space Complexity Cheat Sheet  

The following table summarizes the Average Time Complexity for standard operations and the Worst Case Space Complexity for common linear data structures.

Amortized Analysis  

Amortized—resizing occasionally costs O(n) but averages to O(1).

For array-based structures (Stacks, Queues, and Deques), the O(1) time complexity is amortized . While most operations are instant, resizing the underlying array occasionally requires a "copy" operation that costs O(n) . However, because this happens infrequently, the average cost remains O(1) .

Quick Comparison  

Array-Based: Best for memory locality and cache performance, but carries the overhead of occasional resizing.

Linked-Based: Provides consistent O(1) performance without spikes, but uses more memory per element due to storing pointers (nodes).

4. Common Mistakes  

Here’s where most students lose points. Avoid these traps.

Mistake 1: Forgetting Empty Checks  

What it looks like: Popping from an empty stack causes IndexError or AttributeError (if head is None).

Why students do it: Rush to implement functionality, skip edge cases.

How to avoid: Always check is_empty() before pop/dequeue/peek. Raise custom exceptions or return sentinel values.

Mistake 2: Using List for Queue (pop(0))  

What it looks like: queue = []; queue.pop(0)

Why it’s bad: O(n) time—every pop shifts all elements left. Slow for large data.

How to avoid: Use collections.deque or implement circular queue.

Mistake 3: Losing Reference in Linked List  

What it looks like: In pop, you forget to update tail when removing last node.

Why it happens: You only update head, but tail still points to deleted node.

How to avoid: After head = head.next, if head is None, set tail = None.

Mistake 4: Modulo Off-by-One Errors  

What it looks like: In circular queue, back index calculated wrong, overwriting front.

Why it happens: Confusion between size and capacity.

How to avoid: Always test with wrap-around: enqueue full capacity, then dequeue, then enqueue again.

Mistake 5: Not Resizing Arrays  

What it looks like: Queue reaches capacity and throws error instead of growing.

Why it happens: Static array mentality.

How to avoid: Implement dynamic resizing (like Python list) or use linked list.

Mistake 6: Confusing LIFO and FIFO in Code  

What it looks like: Using a queue but popping from the wrong end.

Why it happens: Mental slip.

How to avoid: Comment your code: # push (add to top) and # pop (remove from top). Be explicit.

5. Real Interview Applications  

Now let’s see stacks and queues in action on actual coding challenges.

Valid Parentheses (Stack)  

def is_valid(s: str) -> bool:
  stack = []
  mapping = {')': '(', '}': '{', ']': '['}
  for char in s:
  if char in mapping:
  if not stack or stack[-1] != mapping[char]:
  return False
  stack.pop()
  else:
  stack.append(char)
  return not stack
  # Test
  print(is_valid("()[]{}"))  # True
  print(is_valid("([)]"))    # False

Monotonic Stack (Next Greater Element)  

def next_greater_element(nums):
  """Find next greater element for each array position."""
  result = [-1] * len(nums)
  stack = []  # stores indices
  for i in range(len(nums)):
  while stack and nums[i] > nums[stack[-1]]:
  idx = stack.pop()
  result[idx] = nums[i]
  stack.append(i)
  return result
  print(next_greater_element([2, 1, 2, 4, 3]))  # [4, 2, 4, -1, -1]

BFS with Queue (Binary Tree Level Order)  

from collections import deque
  def level_order(root):
  if not root:
  return []
  result = []
  queue = deque([root])
  while queue:
  level_size = len(queue)
  current_level = []
  for _ in range(level_size):
  node = queue.popleft()
  current_level.append(node.value)
  if node.left:
  queue.append(node.left)
  if node.right:
  queue.append(node.right)
  result.append(current_level)
  return result

6. FAQ  

Q1: What’s the difference between stack and queue?  

Stack is LIFO (Last In First Out)—like a stack of plates. Queue is FIFO (First In First Out)—like a line of people.

Q2: Can I use Python list as a queue?  

Technically yes, but performance suffers. list.pop(0) is O(n). Use collections.deque for O(1) operations.

Q3: What’s a deque, and when should I use it?  

deque (double-ended queue) supports fast appends/pops from both ends. Use it for queues, stacks, or sliding window problems.

Q4: How do I implement a stack with a queue?  

Use two queues. Push: enqueue to q1. Pop: move all but last from q1 to q2, dequeue last, swap queues. O(n) pop.

Q5: What are real-world examples of stacks and queues?  

Stacks: undo in editors, browser back button, function call stack. Queues: printer spooler, CPU scheduling, messaging systems.

Q6: What is stack overflow?  

When stack exceeds its memory limit—often from infinite recursion. In array-based stacks, it’s when you exceed capacity without resizing.

Q7: Which is better—array or linked list implementation?  

Arrays: better cache locality, less memory overhead per element. Linked lists: no resizing, constant time inserts/deletes at both ends (if you have tail pointer). Choose based on your constraints.

Q8: How do I handle multiple data types in one stack?  

Python allows mixed types in lists/deques. For strict typing, use from typing import Union or generic classes.

Q9: What’s a priority queue?  

Elements have priorities; higher priority dequeued first. Usually implemented with heaps, not FIFO.

Q10: Do I need to implement these from scratch in interviews?  

Sometimes. Be ready to implement basic stack/queue manually, but also know Python’s built-ins for solving higher-level problems.

7. Conclusion  

You’ve just built stacks and queues from scratch using arrays and linked lists. You’ve seen how Python’s built-in list and collections.deque optimize these structures, and you’ve applied them to real interview questions like valid parentheses and BFS.

Remember: understanding the internals—how pointers move in a linked stack or how modulo creates a circular queue—separates good students from great developers. Practice implementing these without looking at notes until the code flows naturally.

Your next steps:  

• Implement a MinStack that returns the smallest element in O(1)
• Build a task scheduler using a queue
• Solve 5 stack/queue problems on LeetCode  
  Need help with your assignment or stuck on a tricky implementation? Submit your assignment for code review, or book a tutoring session for one-on-one guidance. We’re here to help you not just pass, but truly understand.

Read more articles on our blog to master data structures, algorithms, and ace your CS degree.