Understanding Queue and Stack in Data Structures

Data structures are fundamental concepts in computer science that help organize, manage, and store data efficiently. Two of the most basic and essential data structures are Queue and Stack. This article provides an in-depth explanation of their characteristics, Python implementation from scratch, and examples using Python's built-in libraries.

---

1. Stack (LIFO - Last In, First Out)

A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the last element added to the stack is the first one to be removed.

Characteristics of a Stack

• Insertion (push) and removal (pop) happen at the same end, called the top of the stack.
• Access to elements is restricted to the top of the stack only.
• Common operations:
  • push(item): Add an item to the top.
  • pop(): Remove the top item.
  • peek(): View the top item without removing it.
  • is_empty(): Check if the stack is empty.

Python Implementation (From Scratch)

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 an empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("Peek from an empty stack")

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Example Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek()) # Output: 2

Python Built-in Library Example (Using List)

# Using Python's list as a stack
stack = []
stack.append(1)
stack.append(2)
stack.append(3)

print(stack.pop())  # Output: 3
print(stack[-1])    # Peek at the top element, Output: 2

---

2. Queue (FIFO - First In, First Out)

A Queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means the first element added to the queue will be the first one to be removed.

Characteristics of a Queue

• Insertion (enqueue) happens at the rear end, and removal (dequeue) happens from the front end.
• Elements are processed in the order they were added.
• Common operations:
  • enqueue(item): Add an item to the rear.
  • dequeue(): Remove the item from the front.
  • peek(): View the front item without removing it.
  • is_empty(): Check if the queue is empty.

Python Implementation (From Scratch)

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 an empty queue")

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        raise IndexError("Peek from an empty queue")

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Example Usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.peek())     # Output: 2

Python Built-in Library Example (Using collections.deque)

from collections import deque

# Using deque as a queue
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)

print(queue.popleft())  # Output: 1
print(queue[0])         # Peek at the front element, Output: 2

---

3. Summary: Stack vs Queue

Feature	Stack	Queue
Principle	LIFO (Last In, First Out)	FIFO (First In, First Out)
Primary Operations	Push, Pop, Peek	Enqueue, Dequeue, Peek
Access Point	Top	Front and Rear
Common Python Tool	list	collections.deque

---

References

• Goodrich, Michael T., et al. "Data Structures and Algorithms in Python." Wiley, 2013.
• Python Software Foundation. collections.deque documentation.
• Wikipedia: Stack, Queue