手撕数据结构：栈和队列的概念以及实现

在计算机科学中，数据结构是组织和存储数据的方式。栈和队列是最基本的两种数据结构，了解它们的概念及其实现对学习算法和解决问题至关重要。

一、栈（Stack）

1. 概念

栈是一种后进先出（LIFO, Last In First Out）的数据结构。也就是说，最后入栈的元素最先出栈。我们可以将其比作书本的堆叠，最后放上去的书本是最先可以拿到的。

栈主要有两个基本操作： - 推入（Push）：将一个元素放入栈顶。 - 弹出（Pop）：移除并返回栈顶的元素。

2. 实现

栈可以使用数组或链表来实现。以下是用 Python 实现的栈的基本代码示例：

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

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

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

    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from an empty stack")
        return self.items.pop()

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

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

# 使用示例
if __name__ == "__main__":
    stack = Stack()
    stack.push(1)
    stack.push(2)
    print(stack.pop())  # 输出 2
    print(stack.peek())  # 输出 1

二、队列（Queue）

1. 概念

队列是一种先进先出（FIFO, First In First Out）的数据结构。即最早入队的元素最先出队。可以将队列比作排队买票，最先到达的顾客最先被服务。

队列也有两个基本操作： - 入队（Enqueue）：将一个元素添加到队列的末尾。 - 出队（Dequeue）：移除并返回队列的头部元素。

2. 实现

队列同样可以使用数组或链表来实现。以下是用 Python 实现的队列的基本代码示例：

class Queue:
    def __init__(self):
        self.items = []

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

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Dequeue from an empty queue")
        return self.items.pop(0)

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

# 使用示例
if __name__ == "__main__":
    queue = Queue()
    queue.enqueue(1)
    queue.enqueue(2)
    print(queue.dequeue())  # 输出 1
    print(queue.size())      # 输出 1

三、总结

栈和队列作为基础数据结构，具有广泛的应用场景。在算法和程序设计中，栈可以用于解决递归问题、表达式求值等，而队列常被用于广度优先搜索、任务调度等场景。通过对它们的理解和具体实现，我们能够更好地掌握数据结构的基本操作，从而为后续学习复杂数据结构和算法打下良好的基础。