栈与循环队列

1.栈（Stack）是一种具有后进先出（LIFO）特性的线性数据结构。在栈中，元素的插入和删除操作只能在栈的一端进行，通常称为栈顶。栈不支持在任意位置的元素访问，只能访问栈顶的元素。栈的常见操作包括入栈（push）将元素放入栈顶、出栈（pop）将栈顶元素移除，以及获取栈顶元素（peek）等。

下面是一个使用Python列表实现栈的示例代码：

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

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

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

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

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

在上述代码中，我们定义了一个Stack类，使用Python列表作为内部存储结构。push方法将元素添加到栈顶，pop方法将栈顶元素移除并返回它，peek方法返回栈顶元素而不移除它，is_empty方法用于判断栈是否为空。 以下是对栈的一些操作示例：

stack = Stack()
stack.push(10)  # 入栈: 10
stack.push(20)  # 入栈: 20
print(stack.peek())  # 获取栈顶元素: 20
stack.pop()  # 出栈: 20
print(stack.peek())  # 获取栈顶元素: 10

2.循环队列（Circular Queue）是一种通过循环方式实现的队列。与普通队列不同的是，在循环队列中，当队列满时，新的元素可以覆盖队列的起始位置。这种设计在一定程度上提高了存储空间的利用率。循环队列有两个关键指针，一个指向队列的起始位置（front），一个指向队列的末尾位置的下一个位置（rear）。常见操作包括入队（enqueue）将元素添加到队列末尾，出队（dequeue）将队列起始位置的元素移除，并且可以判断队列是否为空或已满。

下面是一个使用Python列表实现循环队列的示例代码：

class CircularQueue:
    def __init__(self, k):
        self.queue = [None] * k
        self.front = 0
        self.rear = 0
        self.size = 0
        self.capacity = k

    def enqueue(self, item):
        if self.is_full():
            return False
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return None
        item = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacity

在上述代码中，我们定义了一个CircularQueue类，使用Python列表作为循环队列的内部存储结构。enqueue方法将元素添加到队列末尾，dequeue方法将队列起始位置的元素移除并返回它，is_empty方法用于判断队列是否为空，is_full方法判断队列是否已满。 以下是对循环队列的一些操作示例：

queue = CircularQueue(3)
queue.enqueue(10)  # 入队: 10
queue.enqueue(20)  # 入队: 20
queue.enqueue(30)  # 入队: 30
print(queue.dequeue())  # 出队: 10
print(queue.dequeue())  # 出队: 20
queue.enqueue(40)  # 入队: 40
print(queue.dequeue())  # 出队: 30
print(queue.is_empty())  # 判断队列是否为空: True

以上是栈和循环队列的简单介绍和示例代码。它们都是常见的数据结构，用于解决各种问题。