What are Stacks and Queues?
Stacks and queues are linear data structures that only usually support push, pop, and peek operations, with no random access. Items must be traversed sequentially.
- Stack: An ordered collection of items where new items are added and existing items removed from the same end (top). (LIFO: Last in, first out)
- Queue: An ordered collection of items where new items are added to the rear, and existing items removed from the front. (FIFO: First-in first-out.)
This guide walks you through everything you need to know about the stack, queue, and deque data structures, with clear, commented code samples.
- Properties of a stack
- Properties of a queue
- Big O time complexity of operations
- Pros and cons of stacks
- Pros and cons of queues
- Create a stack in Python
- Create a queue in Python
- What is a deque?
- Create a deque in Python
- Stack and queue problems
Properties of a Stack
- Items that are closer to the base of the stack have been there the longest
- Think of as a stack of plates
- Can only add and remove to top of stack
- LIFO (Last in, first out)
- Can build with either arrays or linked lists
- Cache locality can make arrays faster for search
- If not dynamic array, could be more expensive to grow it
- e.g. Browser history back and forward buttons
Properties of a Queue
- Items that are closer to the front of the queue have been there the longest
- FIFO (First in, first out)
- Usually don’t lookup in a queue
- Best implemented with a linked list. Faster to remove items without shift
- e.g. Printer queue of documents to be printed, or a queue of people
Big O Time Complexity
Stacks
- lookup: O(n)
- pop: O(1)
- push: O(1)
- peek: O(1)
Queues
- lookup: O(n)
- enqueue: O(1)
- dequeue: O(1)
- peek: O(1)
Pros and Cons of Stacks
Pros:
- Fast Operations
- Fast Peek
- Ordered
Cons:
- Slow Lookup
Pros and Cons of Queues
Queues share the same pros and cons as stacks.
Create a Stack in Python
class Stack:
def __init__(self):
"""
Attributes:
items: A Python list to hold items in the stack.
"""
self.items = []
def push(self, item):
"""Adds a new item to the top of the stack.
Args:
item: The new item being added to the stack.
"""
self.items.append(item)
def pop(self):
"""Removes an item from the top of the stack.
Returns:
If items exist in stack, the item being removed from the stack.
If no items exist, IndexError.
"""
if self.is_empty():
raise IndexError("Stack is empty.")
return self.items.pop()
def peek(self):
"""Displays the item current at the top of the stack.
Returns:
If items exist in stack, the value at the top of the stack.
If no items exist, IndexError.
"""
if self.is_empty():
raise IndexError("Stack is empty.")
return self.items[-1]
def is_empty(self):
"""Checks if the stack is currently empty.
Returns:
True if stack is empty. False if stack contains items.
"""
return self.items == []
def size(self):
"""Display a count of how many items are in the stack.
Returns:
Integer value representing the count of items in the stack.
"""
return len(self.items)
Create a Queue in Python
class Queue:
def __init__(self):
"""
Attributes:
items: A Python list to hold items in the queue.
"""
self.items = []
def enqueue(self, item):
"""Adds a new item to the back of the queue.
Args:
item: The new item being added to the queue.
"""
self.items.insert(0, item)
def dequeue(self):
"""Removes an item from the front of the queue.
Returns:
If items exist in queue, the item being removed from the queue.
If no items exist, IndexError.
"""
if self.is_empty():
raise IndexError("Queue is empty.")
return self.items.pop()
def peek(self):
"""Displays the item current at the front of the queue.
Returns:
If items exist in queue, the value at the front of the queue.
If no items exist, IndexError.
"""
if self.is_empty():
raise IndexError("Queue is empty.")
return self.items[0]
def is_empty(self):
"""Checks if the queue is currently empty.
Returns:
True if queue is empty. False if queue contains items.
"""
return self.items == []
def size(self):
"""Display a count of how many items are in the queue.
Returns:
Integer value representing the count of items in the queue.
"""
return len(self.items)
What is a Deque?
A deque is a double-ended queue, where items can be added and removed from the left or right.
Python includes deques as part of its collections module:
from collections import deque
It’s also possible to create our own deque class using a list.
Create a Deque in Python
class Deque:
def __init__(self):
"""
Attributes:
items: A Python list to hold items in the deque.
"""
self.items = []
def add_right(self, item):
"""Adds a new item to the right of the queue.
Args:
item: The new item being added to the queue.
"""
self.items.append(item)
def add_left(self, item):
"""Adds a new item to the left of the deque.
Args:
item: The new item being added to the deque.
"""
self.items.insert(0, item)
def remove_right(self):
"""Removes an item from the right of the deque.
Returns:
If items exist in queue, the item being removed from the deque.
If no items exist, IndexError.
"""
if self.is_empty():
raise IndexError("Deque is empty.")
return self.items.pop()
def remove_left(self):
"""Removes an item from the left of the deque.
Returns:
If items exist in deque, the item being removed from the deque.
If no items exist, IndexError.
"""
if self.is_empty():
raise IndexError("Deque is empty.")
return self.items.pop(0)
def size(self):
"""Display a count of how many items are in the deque.
Returns:
Integer value representing the count of items in the deque.
"""
return len(self.items)
def is_empty(self):
"""Checks if the deque is currently empty.
Returns:
True if deque is empty. False if queue contains items.
"""
return self.items == []
Stack and Queue Problems
Problem 1:
Implement a queue using two stacks. (Leetcode: 232)
Solution 1:
class QueueWithStacks:
def __init__(self):
"""
Attributes:
in_stack: A Python list to hold new items.
out_stack: A Python list to hold items to be removed.
"""
self.in_stack = []
self.out_stack = []
def enqueue(self, item):
"""Adds a new item to the queue.
A new item is added to the top of the in_stack.
Args:
item: The new item being added to the queue.
"""
self.in_stack.append(item)
def dequeue(self):
"""Removes an item from the queue.
If items in out_stack, return the top item from out_stack.
If out_stack is empty, move all items from in_stack to out_stack.
If out_stack and in_stack both empty, raise error.
Returns:
Oldest item in the queue (top item in out_stack).
"""
if len(self.out_stack) == 0:
# Move items from in_stack to out_stack
while len(self.in_stack) > 0:
in_stack_item = self.in_stack.pop()
self.out_stack.append(in_stack_item)
# Raise error if out_stack empty
if len(self.out_stack) == 0:
raise IndexError("Queue is empty.")
return self.out_stack.pop()
