In Python, you can implement a queue or a stack using various data structures, such as lists or the collections.deque module. Below is how you can implement both:
1. Stack Implementation
A stack follows the “Last In, First Out” (LIFO) principle, meaning the last element added is the first one to be removed.
Using a List
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item) # Adds an item to the end of the list
def pop(self):
if not self.is_empty():
return self.stack.pop() # Removes and returns the last item
return None
def peek(self):
if not self.is_empty():
return self.stack[-1] # Returns the last item without removing it
return None
def is_empty(self):
return len(self.stack) == 0 # Checks if the stack is empty
def size(self):
return len(self.stack) # Returns the number of items in the stack
Example usage:
stack = Stack()
stack.push(10)
stack.push(20)
print(stack.pop()) # Output: 20
print(stack.peek()) # Output: 10
2. Queue Implementation
A queue follows the “First In, First Out” (FIFO) principle, meaning the first element added is the first one to be removed.
Using a List
You can use a list, but removing items from the front can be inefficient (O(n) time complexity). To implement an efficient queue, it’s better to use collections.deque.
Using collections.deque
from collections import deque
class Queue:
def __init__(self):
self.queue = deque()
def enqueue(self, item):
self.queue.append(item) # Adds an item to the end of the deque
def dequeue(self):
if not self.is_empty():
return self.queue.popleft() # Removes and returns the first item
return None
def peek(self):
if not self.is_empty():
return self.queue[0] # Returns the first item without removing it
return None
def is_empty(self):
return len(self.queue) == 0 # Checks if the queue is empty
def size(self):
return len(self.queue) # Returns the number of items in the queue
Example usage:
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue()) # Output: 10
print(queue.peek()) # Output: 20
Summary
- Stack: Can be implemented with a list where items are added with
append()and removed withpop(). - Queue: Can be implemented using
dequefor efficient appending and popping from both ends.
Both of these implementations support the basic operations like adding, removing, and checking the status of the queue or stack.