LIFO Principle of Stack

In programming terms, putting an item on top of the stack is called push and removing an item is called pop.

In the above image, although item 3 was kept last, it was removed first. This is exactly how the LIFO (Last In First Out) Principle works.

Core Operations

Every stack needs to support two main actions, plus a couple of quick checks:

• Push: Add an element to the top of the stack.

• Pop: Remove and return the element at the top of the stack.

• Peek / Top: Look at the top element without removing it.

• IsEmpty: Check if the stack has any elements left.

Implementing a Stack in Python

While you can write a custom class, Python's built-in list type works perfectly as a stack out of the box because it has fast built-in methods for adding and removing items from the end.

• To push an item in the stack, use the list function append list.append(item)

• To pop an item in the stack, use the list function pop list.pop()

• To get the top most item in the stack, write list[-1]

# 1. Initialize an empty stack

stack = []

# 2. Push elements onto the stack (Using .append())

stack.append("Plate A")

stack.append("Plate B")

stack.append("Plate C")

print("Current Stack:", stack) 

# Output: ['Plate A', 'Plate B', 'Plate C']

# 3. Peek at the top element (Using negative indexing [-1])

top_element = stack[-1]

print("Top Element:", top_element) 

# Output: Plate C

# 4. Pop elements off the stack (Using .pop())

removed_item = stack.pop()

print("Popped:", removed_item) 

# Output: Plate C

print("Stack after pop:", stack) 

# Output: ['Plate A', 'Plate B']

Example:

Reverse a list using a stack

#Solution

list=[1,2,3,4,5]

list.append(6)

list.append(7)

print("List before reversal:",list)

for i in range(0,len(list)):

    list.insert(i,list.pop())

print("List after reversal:",list)

Stack Time Complexity

For the array-based implementation of a stack, the push and pop operations take constant time, i.e. O(1).

Real-World Use Cases

Stacks are used all over software engineering. You probably interact with them every day without realizing it:

1. The Undo/Redo Button: Every time you press Ctrl + Z in a text editor, your app pops your last action off a history stack to revert it.

2. The Browser History: When you click the "Back" button in Chrome or Safari, it pops the most recent URL you visited off the stack to take you to the previous page.

3. Function Calls (The Call Stack): When a programming language calls a function inside another function, it uses a stack to keep track of which function to return to when the current one finishes.

Performance Note: While a standard Python list is perfect for learning and small scripts, it can occasionally be slow if it grows very large. For heavy-duty production apps, Python engineers prefer using collections.deque, which is a double-ended queue specifically designed for lightning-fast pops and appends from either side.

Another fundamental data structure is the queue. It is a close “cousin” of the stack, but a queue is a collection of objects that are inserted and removed according to the first-in, first-out (FIFO) principle. That is, elements can be inserted at any time, but only the element that has been in the queue the longest can be next removed. 

We usually say that elements enter a queue at the back and are removed from the front. A metaphor for this terminology is a line of people waiting to get on an amusement park ride. People waiting for such a ride enter at the back of the line and get on the ride from the front of the line. There are many other applications of queues. 

Stores, theaters, reservation centers, and other similar services typically process customer requests according to the FIFO principle. A queue would therefore be a logical choice for a data structure to handle calls to a customer service center, or a wait-list at a restaurant. FIFO queues are also used by many computing devices, such as a networked printer, or a Web server responding to requests. 

There are four different types of queues:

• Simple Queue (A normal queue)

• Circular Queue

• Priority Queue

• Double Ended Queue

A queue(simple queue) is an object (an abstract data structure - ADT) that allows the following operations:

• Enqueue/put: Add an element to the end of the queue

• Dequeue/get: Remove an element from the front of the queue

• IsEmpty: Check if the queue is empty

• IsFull: Check if the queue is full

• Peek: Get the value of the front of the queue without removing it

FIFO Representation of a Queue

In the above image, since 1 was kept in the queue before 2, it is the first to be removed from the queue as well. It follows the FIFO rule.

In programming terms, putting items in the queue is called enqueue, and removing items from the queue is called dequeue.

The queue library handles all the heavy lifting behind the scenes, making it safe to use even if multiple parts of your program are running at the same time (thread safety). There are three main operations you need to know:

• put(item): Adds an item to the end of the queue.

• get(): Removes and returns the item at the front of the queue.

• empty(): Returns True if the queue has nothing left in it.

Step-by-Step Implementation

Because order matters when managing a queue, let's look at the correct sequence for creating, filling, and emptying one.

1.Import and Initialize: Setup.

First, import the library and create a new Queue instance.

from queue import Queue

# Create an empty FIFO queue

line = Queue(maxsize=8)

2.Add Items (Enqueuing): Using put().

Add elements to the back of the line using .put().

line.put("Alice")

line.put("Bob")

line.put("Charlie")

3.Process Items (Dequeuing): Using get().

Remove items from the front of the line using .get(). Because it's FIFO, Alice will come out first.

print(line.get())  # Outputs: Alice

print(line.get())  # Outputs: Bob

4.Check if Empty: Using empty().

Always check if the queue is empty before pulling data, especially inside loops, to avoid your program freezing.

while not line.empty():

    print(f"Serving: {line.get()}")  # Outputs: Serving: Charlie

Queue operations work as follows:

• Two pointers, FRONT and REAR, are used.

• FRONT tracks the first element in the queue.

• REAR tracks the last element in the queue.

• Initially, both FRONT and REAR are set to -1.

Enqueue Operation

1. Check if the queue is full.

2. If inserting the first element, set FRONT to 0.

3. Increase REAR by 1.

4. Insert the new element at the position pointed to by REAR.

Dequeue Operation

1. Check if the queue is empty.

2. Return (or remove) the element pointed to by FRONT.

3. Increase FRONT by 1.

4. If the queue becomes empty after deletion (i.e., FRONT > REAR), reset both FRONT and REAR to -1.

Limitations of Queue

As you can see in the image above, after a bit of enqueuing and dequeuing, the size of the queue has been reduced.

And we can only add indexes 0 and 1 only when the queue is reset (when all the elements have been dequeued).

After REAR reaches the last index, if we can store extra elements in the empty spaces (0 and 1), we can make use of the empty spaces. This is implemented by a modified queue called the circular queue.

Complexity Analysis

The complexity of enqueue and dequeue operations in a queue using an array is O(1). If you use pop(N) in python code, then the complexity might be O(n) depending on the position of the item to be popped.

Real-World Use Cases

While its limitations make it a bit rigid for complex memory management, a Simple Queue is perfect for situations where data must be processed in the exact order it arrives. Its strict First-In, First-Out (FIFO) nature ensures fairness, order, and synchronization.

Here are the primary real-world and computing applications of a simple queue:

1. Operating System & CPU Scheduling

When multiple processes want to use a single resource (like a CPU core), the Operating System uses queues to manage them fairly.

• FIFO/FCFS (First-Come, First-Served) Scheduling: The CPU executes processes in the exact order they enter the ready state.

• Semaphore & Lock Management: When multiple threads try to access a locked resource (like a database row), the threads that are blocked are placed into a simple queue, waiting their turn to get the lock.

2. Network Traffic Management (Buffers)

Data traveling across the internet doesn't arrive in a perfectly smooth stream; it arrives in bursts. Routers, switches, and network interface cards use simple queues to handle this traffic.

• Packet Buffering: When a router receives packets faster than it can transmit them, it stores them in a FIFO queue buffer.

• Data Flow Synchronization: It prevents a fast sender from overwhelming a slow receiver by letting the receiver process data at its own pace from the queue.

3. Shared Resource Peripherals

Whenever a single physical hardware device is shared among multiple users or applications, a queue coordinates the requests.

• Print Spooler: When five people in an office click "Print" at the same time, the printer doesn't mix their pages together. It uses a simple queue to print User 1's entire document, then User 2's, and so on.

• Disk Write Buffers: When an application writes data to a slow hard drive, the data is pushed to a memory queue so the application can keep running while the drive writes the data sequentially.

4. Messaging & Event Handling (Asynchronous Systems)

Modern software architectures rely heavily on queues to decouple systems so they don't have to wait for each other.

• IO Streams & Event Loops: Keyboard strokes, mouse clicks, and touch gestures are registered as "events." The OS places these in a simple event queue, and your application processes them one by one so clicks aren't missed or registered out of order.

• Message Brokers: Simple implementations of message queues (like basic setups in RabbitMQ or Celery) hold tasks or notifications (e.g., sending a welcome email after signup) until a background worker is free to process them.

Summary Rule of Thumb: Use a simple queue whenever order preservation is critical and every item has equal priority.

A circular queue is a linear data structure that operates on the First In, First Out (FIFO) principle, but with a clever twist: the last position is connected straight back to the first position to form a circle.

It solves the biggest flaw of a standard linear queue: wasted space.

The Problem It Solves

In a regular linear queue, once you add items and remove them, the "front" of the queue moves forward. Even if those early slots become empty, a standard queue won't let you reuse them because new items can only be added at the very end (rear). Eventually, you run out of space at the back, even if the front of the queue is completely empty.

A circular queue fixes this by wrapping around to the beginning using modulo arithmetic.

How It Works (The Math)

Instead of just incrementing our pointers with + 1, we use the remainder operator (%) relative to the maximum size of the queue.

• To Enqueue (Insert): rear = (rear + 1) % size

• To Dequeue (Delete): front = (front + 1) % size

Imagine a queue of size 5 (indices 0 to 4). If rear is at index 4 and you add a new item, the math becomes:

(4 + 1) % 5 = 0

The rear pointer smoothly wraps right back around to index 0!

Python Implementation:

class CircularQueue:

   def __init__(self, capacity):

       self.capacity = capacity

       self.queue = [None] * capacity

       self.front = -1

       self.rear = -1

   def is_full(self):

       # The queue is full if the next spot after rear is front

       return (self.rear + 1) % self.capacity == self.front

   def is_empty(self):

       # The queue is empty if front hasn't been set yet

       return self.front == -1

   def enqueue(self, item):

       if self.is_full():

           print("Queue is full! Cannot add item.")

           return False

       # If inserting the first element

       if self.front == -1:

           self.front = 0

       # Move rear pointer circularly and insert

       self.rear = (self.rear + 1) % self.capacity

       self.queue[self.rear] = item

       return True

   def dequeue(self):

       if self.is_empty():

           print("Queue is empty! Nothing to remove.")

           return None

       data = self.queue[self.front]

       self.queue[self.front] = None  # Optional: clear the spot

       # If this was the last element, reset the queue pointers

       if self.front == self.rear:

           self.front = -1

           self.rear = -1

       else:

           # Move front pointer circularly

           self.front = (self.front + 1) % self.capacity

       return data

   def display(self):

       if self.is_empty():

           print("Queue is empty.")

           return

       print("Current Queue State:", self.queue)

# Create a queue with a fixed capacity of 3

cq = CircularQueue(3)

cq.enqueue("A")

cq.enqueue("B")

cq.enqueue("C")

cq.display()  # Output: Current Queue State: ['A', 'B', 'C']

# This will trigger the "Queue is full" check

cq.enqueue("D")

# Remove an item from the front ("A")

print("Dequeued:", cq.dequeue()) 

# Because it's circular, we can now add "D" into that freed-up first slot!

cq.enqueue("D")

cq.display()  # Output: Current Queue State: ['D', 'B', 'C']

Why Use It?

• Memory Efficient: It fully utilizes the allocated array size without needing to shift elements down when something is deleted.

• Fast: Both insertion and deletion happen in constant time, O(1).

• Real-world uses: Traffic light systems, CPU scheduling, and buffering systems (like an audio buffer playing music smoothly while downloading the next chunk).

Key Use Cases

1. Operating System Scheduling (Round Robin)

This is the classic example. An OS needs to give every process a "slice" of CPU time. It puts all active processes into a queue, lets one run for a fixed time quantum, and then moves it to the back. A circular queue is perfect here: the "head" of the queue keeps spinning around, ensuring that processes are scheduled fairly in a continuous loop.

2. Data Buffering (Audio, Video, & Networking)

When you're streaming audio or downloading a file, data arrives at unpredictable speeds (the "producer") but needs to be played or processed at a steady rate (the "consumer").

• The Problem: If the stream is continuous, a linear queue would eventually fill up and crash or require expensive data shifting.

• The Circular Solution: You use a circular buffer. The producer overwrites the oldest data if it's running too fast, or the consumer catches up as it processes the stream. It effectively creates an infinite "loop" of memory.

3. Embedded Systems & Communication (UART/SPI/I2C)

If you're working with something like an ESP32 or Arduino, you’ll see these everywhere. When an MCU (microcontroller unit) receives serial data (like from a GPS module or a sensor), it can't always process the byte the microsecond it arrives.

• The Solution: The hardware interrupt pushes incoming bytes into a circular queue. Your main program periodically checks that queue and "pops" the data to process it. This prevents data loss during high-speed serial communication.

4. Traffic Light Systems

Traffic controllers use a repeating cycle (Green -> Yellow -> Red). This is a simple, fixed-size state machine where the "tasks" (the light colors) are stored in a circular queue. The system just cycles through the queue indices indefinitely.

Deque or Double Ended Queue is a type of queue in which insertion and removal of elements can either be performed from the front or the rear. Thus, it does not follow FIFO rule (First In First Out).

Insertion

append(item): Add an item to the right end.

appendleft(item): Add an item to the left end.

insert(index, value): Add an element with the specified value at the given index.

extend(list): This function is used to insert multiple values at the right end. It takes a list of values as an argument.

extendleft(list): This function is similar to extend(), but it reverses the list of values passed as the argument and then appends that list to the left end of the deque.

Deletion

pop(): Remove an element from the right end.

popleft(): Remove an element from the left end.

remove(value): Remove the first occurrence of the mentioned value.

Miscellaneous

count(value): Return the total number of occurrences of the given value.

index(e, start, end): Search the given element from start to finish and return the index of the first occurrence.

rotate(n): Rotate the deque n number of times. A positive value rotates it to the right, while a negative value rotates it to the left.

reverse(): Reverse the order of the deque.

Code:

# Import collections module:

import collections

# Initialize deque:

dq = collections.deque([4, 5, 6])

# Append to the right:

dq.append(7)

print("Append 7 to the right: ", list(dq))

# Append to the left:

dq.appendleft(3)

print("Append 3 to the left: ", list(dq))

# Append multiple values to right:

dq.extend([8, 9, 10])

print("Append 8, 9 and 10 to the right: ", list(dq))

# Append multiple values to left:

dq.extendleft([1, 2])

print("Append 2 and 1 to the left: ", list(dq))

# Insert -1 at index 5

dq.insert(5, -1)

print("Insert -1 at index 5: ", list(dq))

# Pop element from the right end:

dq.pop()

print("Remove element from the right: ", list(dq))

# Pop element from the left end:

dq.popleft()

print("Remove element from the left: ", list(dq))

# Remove -1:

dq.remove(-1)

print("Remove -1: ", list(dq))

# Count the number of times 5 occurs:

i = dq.count(5)

print("Count the number of times 5 occurs: ", i)

# Return index of '7' if found between index 4 and 6:

i = dq.index(7, 4, 6)

print("Search index of number 7 between index 4 and 6: ", i)

# Rotate the deque three times to the right:

dq.rotate(3)

print("Rotate the deque 3 times to the right: ", list(dq))

# Reverse the whole deque:

dq.reverse()

print("Reverse the deque: ", list(dq))

The time complexity of all the above operations is constant i.e. O(1).

Applications of Deque Data Structure

A deque (double-ended queue) is a linear data structure that allows insertion and deletion of elements from both the front and the rear. Due to this flexibility, it is used in a wide range of applications.

• Undo and Redo Operations: Deques are used in text editors, image editing software, and IDEs to maintain a history of user actions. This allows users to undo or redo previous operations efficiently.

• Browser History: Web browsers use a deque-like structure to manage the Back and Forward history. Users can move backward to previously visited pages and forward again without losing the browsing sequence.

• Implementing Both Stacks and Queues: Since elements can be inserted and removed from either end, a deque can efficiently function as both a stack (LIFO) and a queue (FIFO).

• Task Scheduling: Operating systems and applications can use deques to manage tasks with different priorities. Urgent tasks may be inserted at the front, while regular tasks are added at the rear.

• Palindrome Checking: A deque is useful for checking whether a string is a palindrome by repeatedly comparing and removing characters from both ends.

• Sliding Window Problems: Deques are widely used in algorithms that process data within a fixed-size window, such as finding the maximum or minimum element in every subarray of size k.

• Job and Process Scheduling: In CPU scheduling and simulation systems, deques help manage processes that need to be added or removed from either end based on priority or execution requirements.

• Caching Mechanisms: Some cache replacement algorithms maintain recently used and least recently used items using deque operations to improve data access efficiency.

• Breadth-First Search (BFS): Deques can be used in graph traversal algorithms. They are especially useful in 0–1 BFS, where edges with different weights are processed from opposite ends of the deque.

• Music and Media Playlists: Media players can use a deque to efficiently add or remove songs from the beginning or end of a playlist and to manage the "Up Next" queue.

The priority queue is an advanced type of the queue data structure. Instead of dequeuing the oldest element, a priority queue sorts and dequeues elements based on their priorities.

Priority queues are used to handle scheduling problems where some tasks are prioritized over others.

However, if elements with the same priority occur, they are served according to their order in the queue.

Assigning Priority Value

Generally, the value of the element itself is considered for assigning the priority. For example, The element with the highest value is considered the highest priority element. However, in other cases, we can assume the element with the lowest value as the highest priority element. We can also set priorities according to our needs.

Difference between Priority Queue and Normal Queue

In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the values are removed on the basis of priority. The element with the highest priority is removed first.

The queue.PriorityQueue Class

Python provides a built-in implementation of the priority queue data structure.

Since the queue.PriorityQueue class needs to maintain the order of its elements, a sorting mechanism is required every time a new element is enqueued.

Python solves this by using a binary heap to implement the priority queue.

The Python priority queue is built on the heapq module, which is basically a binary heap.

For insertion, the priority queue uses the put function in the following way:

pQueue.put(value)

The get command dequeues the highest priority elements from the queue.

from queue import PriorityQueue

q = PriorityQueue()

q.put(4)

q.put(2)

q.put(5)

q.put(1)

q.put(3)

while not q.empty():

    next_item = q.get()

    print(next_item)

To attach custom data to a priority level, the standard practice is to insert them as tuples: (priority_number, data).

from queue import PriorityQueue

# 1. Initialize the Priority Queue

pq = PriorityQueue()

# 2. Insert items using .put()

# Format: pq.put((priority, data))

pq.put((3, "Low priority task"))

pq.put((1, "Critical emergency task"))

pq.put((2, "Medium priority task"))

# Check the current size

print(f"Queue size: {pq.qsize()}")  # Output: 3

# 3. Retrieve items using .get()

# It will always pop the lowest priority number first

while not pq.empty():

   priority, task = pq.get()

   print(f"Processing: {task} (Priority: {priority})")

To make the largest number have the highest priority (a Max-Heap behavior) using the queue.PriorityQueue class, you use the exact same trick as heapq: multiply your priority numbers by -1 when putting them into the queue.

Because PriorityQueue always serves the smallest number first, transforming 10 into -10 and 5 into -5 tricks the queue into prioritizing the 10 (since -10 is smaller than -5).

When two tasks share the exact same priority number in a queue.PriorityQueue, Python's behavior depends entirely on what comes after the priority number in your data structure.

By default, if the priority numbers are identical, Python will automatically move to the next item in your tuple (the data itself) and try to compare them to break the tie.

Scenario A: The Data is a String (Alphabetical Tie-Breaking)

If your task data is a string, Python will fall back to alphabetical order. The string starting with the letter closest to 'A' will be treated as the "smaller" item and come out first.

Scenario B: The Data Cannot Be Compared (Causes a Crash)

If your task data is a custom object or a dictionary, Python doesn't know how to compare them (e.g., it can't evaluate if ObjectA < ObjectB). When a tie occurs, your code will crash with a TypeError.

The Clean Fix: Insert an Auto-Incrementing Counter

To prevent crashes and strictly control tie-breaking (usually giving priority to whichever task was submitted first—FIFO), you should insert an auto-incrementing counter as a middleman in your tuple: (priority, tie_breaker, data).

A priority queue processes elements based on urgency, not the order they arrived.

The Top 5 Real-World Uses

• OS Scheduling: The CPU handles urgent tasks (like mouse clicks or audio streams) before background tasks (like system updates).

• GPS & Map Routing: Algorithms (like Dijkstra's) constantly pull the next closest intersection from a priority queue to calculate the fastest route.

• Network Streaming (QoS): Routers prioritize live video and voice packets over large file downloads to prevent calls from dropping.

• Data Compression: Formats like ZIP, JPEG, and MP3 use them to build efficient binary trees (Huffman Coding), processing the least frequent data chunks first.

• Event Simulators: Video games and engines process events sorted by their exact chronological timestamp.