数据结构01-线性结构-链表栈队列-队列篇

**数据结构01 - 线性结构 - 链表、栈、队列**

在计算机科学中，数据结构是指组织和存储数据的方式。线性结构是一种最基本的数据结构，它将元素按顺序排列起来。在本文中，我们将讨论链表、栈和队列这三个重要的线性结构。

### 链表链表是一种特殊的线性结构，每个元素都有一个指向下一个元素的引用（或称为“后继者”）。这种结构允许我们快速插入或删除元素，而不需要移动其他元素。

#### 链表的定义

ctypedef struct Node {
 int data;
 struct Node* next; // 指向下一个元素的指针} Node;

typedef struct LinkedList {
 Node* head; // 头结点 Node* tail; // 尾结点} LinkedList;

#### 链表的操作- **插入**:在链表中插入新元素时，我们需要找到正确的位置并更新指针。

cvoid insert(LinkedList* list, int data) {
 Node* newNode = malloc(sizeof(Node));
 newNode->data = data;
 newNode->next = NULL;

 if (list->head == NULL) { // 链表为空，直接设置新元素为头结点 list->head = newNode;
 list->tail = newNode;
 } else {
 Node* current = list->head;
 while (current->next != NULL) { // 找到链表的尾结点 current = current->next;
 }
 current->next = newNode; // 将新元素设置为尾结点 list->tail = newNode;
 }
}

- **删除**:从链表中删除一个元素时，我们需要找到该元素并更新指针。

cvoid delete(LinkedList* list, int data) {
 if (list->head == NULL) return; // 链表为空，直接返回 if (list->head->data == data) { // 删除头结点 Node* temp = list->head;
 list->head = list->head->next;
 free(temp);
 return;
 }

 Node* current = list->head;
 while (current->next != NULL) {
 if (current->next->data == data) { // 找到要删除的元素 Node* temp = current->next;
 current->next = current->next->next;
 free(temp);
 return;
 }
 current = current->next;
 }

 // 如果链表中没有找到该元素，则直接返回}

### 栈栈是一种特殊的线性结构，它遵循后进先出的原则（LIFO）。这意味着最后添加的元素将首先被移除。

#### 栈的定义

ctypedef struct Stack {
 int* data; // 存储数据的数组 int top; // 栈顶指针 int capacity; // 栈容量} Stack;

#### 栈的操作- **push**:将元素添加到栈中时，我们需要更新栈顶指针。

cvoid push(Stack* stack, int data) {
 if (stack->top == stack->capacity -1) { // 栈已满，直接返回 return;
 }
 stack->data[++stack->top] = data; // 将新元素添加到栈顶}

- **pop**:从栈中移除一个元素时，我们需要更新栈顶指针。

cint pop(Stack* stack) {
 if (stack->top == -1) { // 栈为空，直接返回 return -1;
 }
 int data = stack->data[stack->top--]; // 将栈顶元素弹出 return data;
}

### 队列队列是一种特殊的线性结构，它遵循先进先出的原则（FIFO）。这意味着最先添加的元素将首先被移除。

#### 队列的定义

ctypedef struct Queue {
 int* data; // 存储数据的数组 int front; // 队头指针 int rear; // 队尾指针 int capacity; // 队列容量} Queue;

#### 队列的操作- **enqueue**:将元素添加到队列中时，我们需要更新队尾指针。

cvoid enqueue(Queue* queue, int data) {
 if (queue->rear == queue->capacity -1) { // 队列已满，直接返回 return;
 }
 queue->data[++queue->rear] = data; // 将新元素添加到队尾}

- **dequeue**:从队列中移除一个元素时，我们需要更新队头指针。

cint dequeue(Queue* queue) {
 if (queue->front == queue->rear) { // 队列为空，直接返回 return -1;
 }
 int data = queue->data[queue->front++]; // 将队头元素弹出 return data;
}

在本文中，我们讨论了链表、栈和队列这三个重要的线性结构。这些数据结构在计算机科学中有着广泛的应用，例如缓存管理、浏览器历史记录等。在实际编程中，选择合适的数据结构可以显著提高程序的性能和效率。