In this session, I study stacks and queues. Like arrays and linked lists, these are fundamental concepts for understanding data structures. Let's take a closer look at each of them.
Stack
First, a stack operates on the principle of First In, Last Out (FILO). In other words, the first piece of data that goes in is the last one to come out.
For example, imagine putting tennis balls into a cylindrical container, one by one. Ball number 1 goes in first and sits at the bottom. Then ball number 2, ball number 3, and so on are stacked on top. If you continue this process up to ball number 5, the last one you put in ball number 5 will be on the top.
Now, how would you retrieve ball number 1? Naturally, you would have to remove balls 5, 4, 3, and 2 in that order before you can finally take out ball number 1. That’s why the data that goes in first comes out last.
This is essentially the core idea of a stack - First In, Last Out and understanding this concept means you've grasped most of what a stack is.
I’ve written a Python example based on the explanation above. Just take it as a reference.
# Create an empty stack
stack = []
# Push balls 1 to 5 onto the stack
for i in range(1, 6):
stack.append(f"Ball {i}")
print(f"Pushed : Ball {i}")
print("\nStack state after pushing : ", stack)
# Pop all balls from the stack one by one
while stack:
ball = stack.pop()
print(f"Popped : {ball}")
print("\nStack is now empty : ", stack)
Python
복사
In this example, we simulate placing Ball 1 to Ball 5 onto a stack using the append() method, which adds elements to the top of the stack. Each time a ball is pushed, a message is printed to confirm it.
After all five balls are on the stack, we print the current state. Then, we enter a loop where we remove (pop) each ball from the top of the stack using pop(). Because of the Last In, First Out (LIFO) behavior, the most recently added ball (Ball 5) is removed first.
Finally, we print the empty stack to show that all items have been removed.
The result will be like below
Pushed : Ball 1
Pushed : Ball 2
Pushed : Ball 3
Pushed : Ball 4
Pushed : Ball 5
Stack state after pushing : ['Ball 1', 'Ball 2', 'Ball 3', 'Ball 4', 'Ball 5']
Popped : Ball 5
Popped : Ball 4
Popped : Ball 3
Popped : Ball 2
Popped : Ball 1
Stack is now empty : []
Bash
복사
Queue
A queue follows the concept of First In, First Out (FIFO). This means that the data that comes in first is also the first to come out.
A common real-life example of a queue is standing in line. For instance, imagine waiting in line at a restaurant. Naturally, the person who arrives first is served first.
A queue works the same way, the data that enters first is the data that leaves first.
Like in the example illustration above, in a queue, the person who arrives first is the first to be served.
from collections import deque
# Create a queue
queue = deque()
# Enqueue data
queue.append("Alice")
queue.append("Bob")
queue.append("Charlie")
print("Queue state : ", list(queue)) # ['Alice', 'Bob', 'Charlie']
# Dequeue data
first = queue.popleft()
print("Served person : ", first) # 'Alice'
print("Current queue state : ", list(queue)) # ['Bob', 'Charlie']
Python
복사
This Python code demonstrates a simple implementation of a queue using the deque class from the collections module. A queue follows the First In, First Out (FIFO) principle, where the first element added is the first to be removed.
In the example, we start by creating an empty queue. We then enqueue three people—Alice, Bob, and Charlie—by adding them to the end of the queue using the append() method. The current state of the queue is displayed, showing the order in which people are waiting.
Next, we dequeue the first person in line using the popleft() method, which removes and returns the element from the front of the queue, in this case, Alice. Finally, we print the updated state of the queue to confirm that Alice has been served and removed, leaving Bob and Charlie waiting.
The result will be like below
Queue state : ['Alice', 'Bob', 'Charlie']
Served person : Alice
Current queue state : ['Bob', 'Charlie']
Bash
복사