Stack and Queue
Stacks and Queues are fundamental data structures. They are used for managing collections of data with specific rules:
- Stack (LIFO): Last-In, First-Out order.
- Queue (FIFO): First-In, First-Out order.
1. Stack
- A stack is a linear data structure that follows the LIFO principle.
- Push: Add an element to the top of the stack.
- Pop: Remove the top element.
- Peek: View the top element without removing it.
a) Example Using Python Built-in List
x = []
x.append(2) # First In
x.append(5)
x.append(1)
x.append(3)
x.append(9)
print(x) # Output: [2, 5, 1, 3, 9]
x.pop() # Last Out
print(x) # Output: [2, 5, 1, 3]b) Implementing Stack Class
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
else:
raise IndexError("pop from empty stack")
def peek(self):
if not self.is_empty():
return self.items[-1]
else:
raise IndexError("peek from empty stack")
def size(self):
return len(self.items)
# Stack example
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) # Output: 3
print(f'Value of last element: {stack.peek()}') # Output: 2
print(f'Size of stack: {stack.size()}') # Output: 2
---------------------------------------
3
Value of last element: 2
Size of stack: 2
2. Queue
- A queue is a linear data structure that follows the FIFO principle.
- Enqueue: Add an element to the end of the queue.
- Dequeue: Remove the front element.
- Front: View the front element without removing it.
a) Example Using Python Built-in List
x = []
x.append(2) # First In
x.append(5)
x.append(1)
x.append(3)
x.append(9)
print(x) # Output: [2, 5, 1, 3, 9]
x.pop(0) # First Out
print(x) # Output: [5, 1, 3, 9]b) Implementing Queue Class
class Queue:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.pop(0)
else:
raise IndexError("dequeue from empty queue")
def front(self):
if not self.is_empty():
return self.items[0]
else:
raise IndexError("front from empty queue")
def size(self):
return len(self.items)
# Queue example
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
print(queue.dequeue()) # Output: 'a'
print(f'Value of first element: {queue.front()}') # Output: 'b'
print(f'Size of queue: {queue.size()}') # Output: 2
---------------------------------------
'a'
Value of first element: b
Size of queue: 2