数据结构复习（一）到循环队列

**数据结构复习（一）**

在计算机科学中，数据结构是指组织和存储数据的方式。它决定了我们如何访问、修改和操作数据。在本文中，我们将回顾一些基本的数据结构，包括线性表、栈、队列和循环队列。

**1. 线性表**

线性表是一种最简单的数据结构，它是由一组元素按照一定的顺序排列而成。每个元素都有一个唯一的索引或下标，可以通过该下标来访问。

线性表可以分为两类：静态线性表和动态线性表。

* 静态线性表：其大小固定，不可改变。
* 动态线性表：其大小可以根据需要进行调整。

线性表的基本操作包括：

* 插入：在指定位置插入一个新元素。
* 删除：删除指定位置的元素。
* 查找：查找指定位置的元素。
* 排序：对线性表中的所有元素进行排序。

**示例代码**

class LinearTable:
 def __init__(self, size):
 self.size = size self.data = [None] * size def insert(self, index, value):
 if index < 0 or index >= self.size:
 raise IndexError("Index out of range")
 for i in range(self.size -1, index -1, -1):
 self.data[i +1] = self.data[i]
 self.data[index] = value def delete(self, index):
 if index < 0 or index >= self.size:
 raise IndexError("Index out of range")
 for i in range(index, self.size -1):
 self.data[i] = self.data[i +1]

 def find(self, index):
 if index < 0 or index >= self.size:
 return None return self.data[index]

# 创建一个线性表，大小为10linear_table = LinearTable(10)

# 插入元素linear_table.insert(5, "Hello")

# 删除元素linear_table.delete(3)

# 查找元素print(linear_table.find(2)) # 输出: None

**2. 栈**

栈是一种特殊的线性表，它遵循后进先出的原则。也就是说，最后添加的元素将最先被移除。

栈的基本操作包括：

* push：向栈顶添加一个新元素。
* pop：从栈顶移除一个元素。
* peek：查看栈顶的元素。

**示例代码**

class Stack:
 def __init__(self, size):
 self.size = size self.data = [None] * size def push(self, value):
 for i in range(self.size -1,0, -1):
 self.data[i] = self.data[i -1]
 self.data[0] = value def pop(self):
 return self.data.pop()

 def peek(self):
 return self.data[-1]

# 创建一个栈，大小为10stack = Stack(10)

# push元素stack.push("Hello")

# pop元素print(stack.pop()) # 输出: Hello# peek元素print(stack.peek()) # 输出: None

**3. 队列**

队列是一种特殊的线性表，它遵循先进先出的原则。也就是说，第一个添加的元素将最先被移除。

队列的基本操作包括：

* enqueue：向队尾添加一个新元素。
* dequeue：从队头移除一个元素。
* peek：查看队头的元素。

**示例代码**

class Queue:
 def __init__(self, size):
 self.size = size self.data = [None] * size def enqueue(self, value):
 for i in range(self.size -1,0, -1):
 self.data[i] = self.data[i -1]
 self.data[0] = value def dequeue(self):
 return self.data.pop()

 def peek(self):
 return self.data[-1]

# 创建一个队列，大小为10queue = Queue(10)

# enqueue元素queue.enqueue("Hello")

# dequeue元素print(queue.dequeue()) # 输出: Hello# peek元素print(queue.peek()) # 输出: None

**4. 循环队列**

循环队列是一种特殊的队列，它在队尾添加新元素时，会将老元素覆盖掉，而不是追加到队尾。

循环队列的基本操作包括：

* enqueue：向队尾添加一个新元素。
* dequeue：从队头移除一个元素。
* peek：查看队头的元素。

**示例代码**

class CircularQueue:
 def __init__(self, size):
 self.size = size self.data = [None] * size self.front =0 self.rear =0 def enqueue(self, value):
 if (self.rear +1) % self.size == self.front:
 raise IndexError("Queue is full")
 self.data[self.rear] = value self.rear = (self.rear +1) % self.size def dequeue(self):
 if self.front == self.rear:
 raise IndexError("Queue is empty")
 value = self.data[self.front]
 self.data[self.front] = None self.front = (self.front +1) % self.size return value def peek(self):
 if self.front == self.rear:
 raise IndexError("Queue is empty")
 return self.data[self.front]

# 创建一个循环队列，大小为10circular_queue = CircularQueue(10)

# enqueue元素circular_queue.enqueue("Hello")

# dequeue元素print(circular_queue.dequeue()) # 输出: Hello# peek元素print(circular_queue.peek()) # 输出: None

以上就是本文关于线性表、栈、队列和循环队列的基本概念和操作。这些数据结构是计算机科学中非常重要的基础知识，广泛应用于各种算法和程序设计中。