Introduction to Stacks and Queues

Overview

Stacks and queues are fundamental data structures used in computer science and programming. These structures have specific properties and functionalities that make them useful in various applications. In this post, we will provide a comprehensive introduction to stacks and queues, explaining their basic concepts, functionalities, and differences, serving as a foundation for the subsequent posts.

Stack

A stack is a last-in, first-out (LIFO) data structure, meaning that the most recently added element is the first one to be removed. It operates like a collection of objects stacked on top of each other, resembling a physical stack of plates or books.

Operations

A stack typically supports the following operations:

1. Push: Add an element to the top of the stack.
2. Pop: Remove and return the topmost element from the stack.
3. Peek: Return the topmost element without removing it.
4. IsEmpty: Check if the stack is empty.
5. Size: Retrieve the number of elements in the stack.

Implementation

Stacks can be implemented using arrays or linked lists. Let's consider the array-based implementation:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]

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

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

Example

Let's see a simple example of how a stack works:

stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.peek())      # Output: 30
print(stack.pop())       # Output: 30
print(stack.is_empty())  # Output: False
print(stack.size())      # Output: 2

Queue

A queue is a first-in, first-out (FIFO) data structure, meaning that the element that has been in the queue the longest is the first one to be removed. It operates like a real-life queue, such as people waiting in line for a movie ticket or at a checkout counter.

Operations

A queue typically supports the following operations:

1. Enqueue: Add an element to the end of the queue.
2. Dequeue: Remove and return the element from the front of the queue.
3. Peek: Return the element at the front without removing it.
4. IsEmpty: Check if the queue is empty.
5. Size: Retrieve the number of elements in the queue.

Implementation

Queues can also be implemented using arrays or linked lists. Let's consider the linked list-based implementation:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, item):
        new_node = Node(item)
        if self.is_empty():
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def dequeue(self):
        if not self.is_empty():
            front = self.head
            self.head = self.head.next
            return front.data

    def peek(self):
        if not self.is_empty():
            return self.head.data

    def is_empty(self):
        return self.head is None

    def size(self):
        count = 0
        curr = self.head
        while curr:
            count += 1
            curr = curr.next
        return count

Example

Let's see a simple example of how a queue works:

queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.peek())      # Output: 10
print(queue.dequeue())   # Output: 10
print(queue.is_empty())  # Output: False
print(queue.size())      # Output: 2

Conclusion

In this introductory post, we explored the basic concepts, functionalities, and implementations of stacks and queues. Stacks follow the LIFO principle and are commonly used to handle function calls, undo/redo operations, and backtracking. Queues follow the FIFO principle and are often used in scheduling, buffering, and breadth-first search algorithms. Understanding these data structures will provide a solid foundation for the upcoming posts where we will dive deeper into their implementation details and practical applications.