Test cases

In the previous article, we discussed the linked list—a fundamental data structure that provides flexible storage for elements. In this article, we will explore two critically important data structures: stacks and queues. Though simple in concept, both are widely applied across diverse problem domains.

I. Stack

1.1 Concept of a Stack

A stack is a Last-In-First-Out (LIFO) data structure. This means the element most recently added to the stack is the first one to be removed. You can visualize it as a stack of papers in a box: the last paper placed in sits on top, and you can only remove papers starting from the top.

1.2 Basic Stack Operations

A stack supports the following core operations:

• push(x): Adds element x onto the top of the stack
• pop(): Removes and returns the top element of the stack
• peek(): Returns the top element without removing it
• isEmpty(): Checks whether the stack is empty

1.3 Practical Application Example

A classic use case is parentheses matching in expressions. To verify whether parentheses in a string are properly balanced, we can leverage a stack:

def is_valid_parentheses(s: str) -> bool:
    stack = []
    parentheses_map = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in parentheses_map.values():
            stack.append(char)
        elif char in parentheses_map.keys():
            if stack == [] or parentheses_map[char] != stack.pop():
                return False
    return stack == []

# Test cases
print(is_valid_parentheses("()[]{}"))  # Output: True
print(is_valid_parentheses("(]"))      # Output: False

In this example, we traverse the input string, pushing opening brackets onto the stack. When encountering a closing bracket, we check whether the top of the stack contains its matching opening bracket. Finally, the string is valid only if the stack is empty after processing all characters.

II. Queue

2.1 Concept of a Queue

A queue is a First-In-First-Out (FIFO) data structure. Unlike a stack, the element that enters the queue first is the first one to be removed—akin to people lining up: the person who arrives earliest is served first.

2.2 Basic Queue Operations

A queue supports the following core operations:

• enqueue(x): Adds element x to the rear (tail) of the queue
• dequeue(): Removes and returns the element from the front (head) of the queue
• peek(): Returns the front element without removing it
• isEmpty(): Checks whether the queue is empty

2.3 Practical Application Example

A common application is task scheduling, where a queue manages pending tasks awaiting execution. Here’s a simple implementation:

from collections import deque

class TaskQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)

    def process_task(self):
        if not self.is_empty():
            return self.queue.popleft()
        return None

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

# Test
task_queue = TaskQueue()
task_queue.add_task("Task 1")
task_queue.add_task("Task 2")

while not task_queue.is_empty():
    print("Processing:", task_queue.process_task())

In this example, we use Python’s deque to implement a basic task queue supporting task insertion (add_task) and sequential processing (process_task).

III. Summary

Stacks and queues are foundational—yet remarkably powerful—data structures. They play pivotal roles in software design, enabling elegant solutions to many real-world problems through their intuitive operational semantics. In the next article, we’ll continue our overview of data structures by exploring more advanced ones: trees and graphs—stay tuned!