Linked Lists
December 29, 2023
Trees
December 29, 2023
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. In a stack, elements are added and removed from the same end, often referred to as the “top” of the stack. The last element added is the first one to be removed.
Key Operations:
- Push: Adds an element to the top of the stack.
- Pop: Removes the element from the top of the stack.
- Peek or Top: Returns the value of the top element without removing it.
- isEmpty: Checks if the stack is empty.
- Size: Returns the number of elements in the stack.
Common Use Cases:
- Function Calls: Stacks are used to keep track of function calls and returns in many programming languages.
- Undo Mechanisms: Many applications use a stack to implement undo functionality.
- Expression Evaluation: Stacks are employed in parsing and evaluating expressions.
Implementation:
In many programming languages, you can implement a stack using arrays or linked lists.
# Stack implementation using Python list
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
Queues:
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. In a queue, elements are added at the rear (enqueue) and removed from the front (dequeue). The first element added is the first one to be removed.
Key Operations:
- Enqueue: Adds an element to the rear of the queue.
- Dequeue: Removes the element from the front of the queue.
- Front: Returns the value of the front element without removing it.
- isEmpty: Checks if the queue is empty.
- Size: Returns the number of elements in the queue.
Common Use Cases:
- Task Scheduling: Queues are used in task scheduling algorithms.
- Print Queue: Print jobs are typically processed in the order they are received, forming a queue.
- Breadth-First Search (BFS): Queues are used in graph algorithms like BFS.
Implementation:
Queues can be implemented using arrays or linked lists.
# Queue implementation using Python collections.deque
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.popleft()
def front(self):
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
In both stacks and queues, the choice of implementation (array or linked list) depends on the specific requirements of the application. Stacks and queues are fundamental data structures with various real-world applications.
