Stacks and queues are fundamental data structures that are widely used in programming and computer science. They help manage data in an organized way, allowing for efficient access and modification.
▎Stacks
A stack is a collection of elements that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed.
▎Key Operations
1. Push: Add an element to the top of the stack.
2. Pop: Remove the element from the top of the stack.
3. Peek/Top: Retrieve the top element without removing it.
4. IsEmpty: Check if the stack is empty.
▎Example Implementation in Python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
raise IndexError("pop from empty stack")
def peek(self):
if not self.is_empty():
return self.items[-1]
raise IndexError("peek from empty stack")
def is_empty(self):
return len(self.items) == 0
# Example usage
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.peek()) # Output: 2
print(stack.pop()) # Output: 2
print(stack.is_empty()) # Output: False
▎Queues
A queue is a collection of elements that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed.
▎Key Operations
1. Enqueue: Add an element to the back of the queue.
2. Dequeue: Remove the element from the front of the queue.
3. Front/Peek: Retrieve the front element without removing it.
4. IsEmpty: Check if the queue is empty.
▎Example Implementation in Python
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.pop(0)
raise IndexError("dequeue from empty queue")
def front(self):
if not self.is_empty():
return self.items[0]
raise IndexError("front from empty queue")
def is_empty(self):
return len(self.items) == 0
# Example usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.front()) # Output: 1
print(queue.dequeue()) # Output: 1
print(queue.is_empty()) # Output: False
▎Use Cases
• Stacks are commonly used in:
– Function call management (call stack).
– Undo mechanisms in applications.
– Syntax parsing (e.g., in compilers).
• Queues are commonly used in:
– Task scheduling (e.g., print jobs).
– Breadth-first search algorithms in graphs.
– Managing requests in web servers.
▎Conclusion
Stacks and queues are essential data structures that provide efficient ways to manage data based on specific access patterns. Understanding how to implement and utilize these structures can significantly improve your programming skills and problem-solving abilities.