Stack and Queue in Python
Subject: Data Structures and Algorithms · Language: Python · Level: intermediate · 8 min read
Learn stack and queue in Python with LIFO, FIFO, list, deque, operations, underflow, use cases, and DSA examples.
Stack and queue are linear data structures, but they follow different removal rules. A stack follows LIFO, which means Last In, First Out. A queue follows FIFO, which means First In, First Out.
A stack is useful when the most recent item should be processed first. Examples include undo operations, function calls, recursion behavior, expression evaluation, backtracking, and balanced parentheses checking.
A queue is useful when the earliest item should be processed first. Examples include scheduling, BFS, level order traversal, request handling, and task processing in arrival order.
In Python, a list can be used like a stack with `append()` and `pop()`. For queue operations, `deque` from the `collections` module is preferred because removing from the front with `popleft()` is efficient.
Students can remember the difference by inserting 10, 20, and 30. If 30 comes out first, it is stack behavior. If 10 comes out first, it is queue behavior. This small dry run makes the rule clear.
In interviews, stack and queue problems often depend on exact processing order. Before coding, write a small example and check which item should be removed next. This prevents many logic mistakes.
These rules decide which element can be removed first. In a normal Python list, we can access many positions using indexes, but in stack and queue problems we usually follow a strict removal rule.
Stack and queue are very important in DSA because many problems are not only about storing data, but also about processing data in the correct order.
What Is a Stack?
A stack works like a pile of plates. The plate placed last is removed first. This is why stack follows Last In, First Out.
In programming, the last inserted item is called the top of the stack. Insertion and deletion happen from the same end.
Stack Operations
The main stack operations are push, pop, peek, and is empty.
- Push means insert an item on top of the stack
- Pop means remove the top item
- Peek means read the top item without removing it
- is empty means check whether the stack has no elements
Stack Using Python List
Python does not require a separate stack class for beginner DSA. A list can be used as a stack.
```python
stack = []
stack.append(10)
stack.append(20)
stack.append(30)
```
Here, `append()` works like push. It inserts the value at the end of the list, which we treat as the top of the stack.
Removing from Stack
Use `pop()` to remove and return the top element.
```python
top = stack.pop()
```
If the stack contains `[10, 20, 30]`, then `pop()` removes `30` because it was inserted last.
Reading Top Element
To read the top element without removing it, use `stack[-1]`.
```python
top = stack[-1]
```
Before using `stack[-1]`, check that the stack is not empty. Otherwise, Python will raise an index error.
Stack Underflow
Underflow means trying to remove an element when the stack is already empty.
In Python, calling `pop()` on an empty list causes an error. So it is a good habit to check whether the stack has elements before popping.
```python
if stack:
value = stack.pop()
else:
print("Stack is empty")
```
Sample Output when `stack = []`
```text
Stack is empty
```
This makes the logic safer and clearer.
Where Stack Is Used
Stacks are useful when the most recent item should be handled first.
Common stack use cases include undo operations, recursion call stack, browser backtracking, expression evaluation, balanced parentheses, next greater element, and backtracking problems.
In interviews, balanced parentheses is one of the most common beginner stack problems.
What Is a Queue?
A queue works like a line of people waiting for service. The person who enters first is served first. This is why queue follows First In, First Out.
Insertion happens at the rear, and deletion happens from the front.
Queue Operations
The main queue operations are enqueue, dequeue, peek, and is empty.
- Enqueue means insert an item at the rear
- Dequeue means remove an item from the front
- Peek means read the front item without removing it
- is empty means check whether the queue has no elements
Why Not Use list.pop(0)?
A Python list can remove the first element using `pop(0)`, but this is inefficient for large input.
When the first element is removed from a list, all remaining elements shift left. This takes O(n) time.
For queue behavior, Python's `deque` is better because removing from the front using `popleft()` is efficient.
Queue Using deque
`deque` is available in the `collections` module.
```python
from collections import deque
queue = deque()
queue.append(10)
queue.append(20)
queue.append(30)
```
Here, `append()` adds values at the rear of the queue.
Removing from Queue
Use `popleft()` to remove and return the front element.
```python
front = queue.popleft()
```
If the queue contains `10, 20, 30`, then `popleft()` removes `10` because it was inserted first.
Reading Front Element
To read the front element without removing it, use `queue[0]`.
```python
front = queue[0]
```
Before reading or removing, check that the queue is not empty.
Queue Underflow
Queue underflow means trying to remove an element from an empty queue.
```python
if queue:
value = queue.popleft()
else:
print("Queue is empty")
```
Sample Output when `queue` is empty
```text
Queue is empty
```
This prevents runtime errors and makes the program stable.
Where Queue Is Used
Queues are useful when data must be processed in arrival order.
Common queue use cases include scheduling, request handling, BFS, level order traversal of trees, producer-consumer problems, and task processing systems.
In DSA, BFS is the most important queue-based technique for beginners.
Deque as Double-Ended Queue
A deque allows insertion and deletion from both ends.
```python
from collections import deque
dq = deque()
dq.append(10)
dq.appendleft(5)
dq.pop()
dq.popleft()
```
This makes deque useful for queues, sliding window problems, and some advanced DSA patterns.
Priority Queue Idea
A priority queue removes elements based on priority instead of normal arrival order.
In Python, priority queue logic is commonly implemented using `heapq`.
```python
import heapq
heap = []
heapq.heappush(heap, 30)
heapq.heappush(heap, 10)
print(heapq.heappop(heap))
```
Output
```text
10
```
Python's heap gives the smallest value first by default.
Stack vs Queue
A stack removes the newest element first. A queue removes the oldest element first.
If the insertion order is 10, 20, 30, then a stack removes 30 first, but a queue removes 10 first.
This difference is the heart of stack and queue problems.
Example Program
```python
from collections import deque
stack = []
stack.append(10)
stack.append(20)
stack.append(30)
queue = deque()
queue.append(10)
queue.append(20)
queue.append(30)
print("Stack top removed =", stack.pop())
print("Queue front removed =", queue.popleft())
```
Output
```text
Stack top removed = 30
Queue front removed = 10
```
This program shows the difference clearly. Stack removes `30` first because it was inserted last. Queue removes `10` first because it was inserted first.
Stack and Queue in DSA
Stacks and queues are used when the order of processing matters. If the latest item should be processed first, use a stack. If the earliest item should be processed first, use a queue.
Before solving a problem, ask: should I process the newest value or the oldest value? This question often tells you whether stack or queue is needed.
A stack and queue both store multiple values, but their removal rules are different. A stack removes the most recent value first. A queue removes the oldest value first. This one rule changes the type of problems each structure can solve.
Use a stack when the latest pending item should be handled first. This appears in undo operations, expression evaluation, recursion behavior, bracket matching, and backtracking.
Many students confuse stack and queue because both support insertion and deletion. The correct way to separate them is to ask: after inserting 10, 20, and 30, which value should come out first? If it is 30, it is stack behavior. If it is 10, it is queue behavior.
Practice Question
Use a stack to check whether parentheses in a string are balanced. Then create a queue, insert five numbers, and remove them one by one to observe FIFO order.