数据结构_栈和队列学习

第一部分：栈的理解与C语言实现

栈的基本概念

• 定义：栈是一种线性数据结构，遵循“后进先出”（LIFO, Last In First Out）原则，类似于生活中的盘子堆叠。
• 操作特性：主要操作包括压栈（push）、弹栈（pop）和查看栈顶元素，不支持随机访问。

数组实现栈

        数组：简单易实现，空间固定，可能造成空间浪费或溢出。

函数设计

• 初始化栈：分配内存，设置栈顶指针。使用数组在实现栈
• 入栈操作(pushstack)：在栈顶添加元素，更新栈顶指针。
• 出栈操作(popstack)：移除栈顶元素，更新栈顶指针。
• 查看栈顶元素(peek)：返回栈顶元素，不改变栈状态。
• 判断栈是否为空(is_empty)：检查栈是否没有元素。

示例代码

1#include <stdio.h>
2#define MAX_SIZE 100
3
4typedef struct {
5    int data[MAX_SIZE];//静态数组
6    int top;
7} Stack;
8
9void initStack(Stack* s) {
10    s->top = -1; // 初始化栈顶指针为-1，表示空栈
11}
12
13void pushStack(Stack* s, int item) {
14    if (s->top == MAX_SIZE - 1) {
15        printf("Stack Overflow\n");
16        return;
17    }
18    s->data[++(s->top)] = item;
19}
20
21int popStack(Stack* s) {
22    if (s->top == -1) {
23        printf("Stack Underflow\n");
24        return -1;
25    }
26    return s->data[s->top--];
27}
28
29int peek(Stack* s) {
30    if (s->top != -1)
31        return s->data[s->top];
32    else
33        return -1; // 或其他错误码
34}
35
36int is_empty(Stack* s) {
37    return s->top == -1;
38}

链表实现栈

        

实现思路

• 节点定义：每个节点包含数据和指向下一个节点的指针。
• 栈结构：包含一个指向栈顶节点的指针。

函数设计

• 初始化栈：栈顶指针设为NULL。
• 入栈操作(push)：创建新节点，将其连接到当前栈顶节点。
• 出栈操作(pop)：保存栈顶节点信息，更新栈顶指针为栈顶节点的下一个节点，然后释放原栈顶节点。
• 查看栈顶(peek)：直接返回栈顶节点的数据。

• 判断空(is_empty)：检查栈顶指针是否为NULL。

示例代码

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node* next;
} Node;
 
typedef struct Stack {
    Node* top;
} Stack;
 
void initStack(Stack* s) {
    s->top = NULL;
}
 
void push(Stack* s, int item) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = item;
    newNode->next = s->top;
    s->top = newNode;
}
 
int pop(Stack* s) {
    if (s->top == NULL) {
        printf("Stack Underflow\n");
        return -1;
    }
    Node* temp = s->top;
    int data = temp->data;
    s->top = temp->next;
    free(temp);
    return data;
}
 
int peek(Stack* s) {
    if (s->top != NULL)
        return s->top->data;
    else
        return -1;
}
 
int isEmpty(Stack* s) {
    return s->top == NULL;
}
 
// 注意：记得在程序结束时释放栈中所有节点的内存

使用数组或链表实现优劣评价

• 优点：
  • 动态大小，理论上不受限于预先分配的内存大小。
  • 插入和删除操作时间复杂度为O(1)，高效。
• 缺点：
  • 需要额外的内存开销用于存储节点的指针。
  • 相比数组，链表的随机访问性能较差。

第二部分：队列的理解与C语言实践

队列的基础理论

• 定义：遵循“先进先出”（FIFO, First In First Out）原则，与栈相反。
• 常见类型：
  • 循环队列：解决传统队列头尾指针移动问题，空间利用更高效。
  • 链式队列：通过链表实现，动态调整大小，但访问速度相对慢。

应用领域

• 缓存系统、任务调度、广度优先搜索(BFS)等。

使用数组实现队列

• 数据结构选择与比较：与栈类似，数组实现简单但可能有假满/假空问题，链式队列解决了这一问题。

函数设计

• 初始化队列：清空队列，设置头尾指针。
• 入队操作(pushqueue)：在队尾添加元素，更新尾指针。
• 出队操作(popqueue)：从队首移除元素，更新头指针。
• 查看队首元素(front)：返回队首元素，不修改队列。
• 判断队列是否为空(is_empty)：检查队列是否为空。

循环队列的实现细节与优势

• 细节：当队列满时，可以通过将尾指针回绕到数组起始位置来重新开始填充。
• 优势：解决了普通队列的空间浪费问题，提高了空间利用率。

示例代码与分析

1#include <stdio.h>
2#define MAX_SIZE 100
3
4typedef struct {
5    int data[MAX_SIZE];
6    int front, rear;
7} Queue;
8
9void initQueue(Queue* q) {
10    q->front = q->rear = 0;
11}
12
13void enqueue(Queue* q, int item) {
14    if ((q->rear + 1) % MAX_SIZE == q->front) {
15        printf("Queue Overflow\n");
16        return;
17    }
18    q->data[q->rear] = item;
19    q->rear = (q->rear + 1) % MAX_SIZE;
20}
21
22int dequeue(Queue* q) {
23    if (q->front == q->rear) {
24        printf("Queue Underflow\n");
25        return -1;
26    }
27    int item = q->data[q->front];
28    q->front = (q->front + 1) % MAX_SIZE;
29    return item;
30}
31
32int front(Queue* q) {
33    if (!is_empty(q))
34        return q->data[q->front];
35    else
36        return -1; // 或其他错误码
37}
38
39int is_empty(Queue* q) {
40    return q->front == q->rear;
41}

使用链表实现队列

实现思路

• 链式队列有两种常见方式：
  • 单向队列：每个节点包含数据和指向下一个节点的指针。需要额外的队尾指针。
  • 双向队列：每个节点包含数据、前驱指针和后继指针。可以更高效地在两端进行插入和删除操作。

函数设计（以单向队列为示例）

• 初始化队列：前后指针均设为NULL。
• 入队操作(enqueue)：在队尾添加新节点，更新队尾指针。
• 出队操作(dequeue)：保存队首节点信息，更新队首指针为其后继，然后释放原队首节点。
• 查看队首(front)：直接返回队首节点的数据。
• 判断空(is_empty)：检查队首指针是否为NULL。

示例代码

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node* next;
} Node;
 
typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;
 
void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}
 
void enqueue(Queue* q, int item) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = item;
    newNode->next = NULL;
    if (q->rear == NULL)
        q->front = q->rear = newNode;
    else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}
 
int dequeue(Queue* q) {
    if (q->front == NULL) {
        printf("Queue Underflow\n");
        return -1;
    }
    Node* temp = q->front;
    int data = temp->data;
    q->front = temp->next;
    if (q->front == NULL)
        q->rear = NULL;
    free(temp);
    return data;
}
 
int front(Queue* q) {
    if (q->front != NULL)
        return q->front->data;
    else
        return -1;
}
 
int isEmpty(Queue* q) {
    return q->front == NULL;
}
 
// 同样，确保在程序结束时释放队列中所有节点的内存

优劣评价

• 优点：
  • 动态大小，灵活应对数据量变化。
  • 插入和删除操作同样保持O(1)的时间复杂度。
• 缺点：
  • 与链式栈相似，链式队列也有额外的内存开销。
  • 相对于循环数组实现的队列，链式队列的访问效率较低，特别是随机访问。