数据结构之栈、队列——算法与数据结构入门笔记(四)

简介: 数据结构之栈、队列——算法与数据结构入门笔记(四)

本文是算法与数据结构的学习笔记第四篇,将持续更新,欢迎小伙伴们阅读学习 。有不懂的或错误的地方,欢迎交流



栈是一种线性数据结构,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶 (Top), 另一端称为栈底 (Bottom)。栈中的数据元素遵守后进先出 LIFO(Last In First Out)的原则,即最后进入的元素最先被访问。

压栈(push):栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈(pop):栈的删除操作叫做出栈,出数据也在栈顶。

下面的动图可以更直观的理解栈的出入栈

栈的特点

  1. 后进先出(LIFO):最后进入栈的元素最先被访问,而最先进入栈的元素最后被访问。
  2. 只允许在一端进行插入和删除操作:栈通常只允许在栈顶进行插入和删除操作,而不允许在其他位置进行操作。
  3. 栈顶指针:栈顶指针指向栈顶元素,它随着元素的插入和删除而改变。

栈的应用

  1. 函数调用:编程语言中的函数调用过程使用栈来保存函数的返回地址、参数和局部变量等信息。每当一个函数被调用,其相关信息被压入栈中;当函数执行完毕,这些信息被弹出栈,控制权回到调用函数。
  2. 表达式求值:栈在表达式求值中起到重要作用。通过将中缀表达式转换为后缀表达式,并使用栈来存储操作数和运算符,可以实现对表达式的求值。
  3. 括号匹配:栈常用于检查表达式中括号是否匹配的问题。遍历表达式时,遇到左括号就将其压入栈中,遇到右括号时与栈顶元素进行匹配,如果匹配则弹出栈顶元素,继续遍历;如果不匹配,则括号不匹配。
  4. 撤销操作:在文本编辑器或图形处理软件中,栈可用于实现撤销操作。每次执行操作时,相关信息被压入栈中,当用户需要撤销操作时,将栈顶元素弹出,回退到上一个状态。
  5. 中断处理和现场保护:中断是计算机系统中常见的事件,例如硬件故障、外部设备请求等。当系统发生中断时,当前正在执行的程序需要被暂停,转而处理中断事件。栈在中断处理中扮演着重要角色,用于保存和恢复程序的执行现场。当发生中断时,系统会自动将当前程序的执行现场(包括程序计数器、寄存器等状态信息)保存到栈中。然后,中断服务程序(Interrupt Service Routine,ISR)被执行,处理中断事件。处理完成后,系统从栈中恢复之前保存的执行现场,继续原来被中断的程序的执行。通过栈的保存和恢复操作,确保中断处理的流程正确且不会破坏原有的程序执行。

栈的基本操作

  1. 初始化栈。
  2. 压栈,往栈中添加一个元素。
  3. 出栈,从栈顶删除一个元素。
  4. 获取栈顶元素。
  5. 判断栈是否为空、是否满栈。
  6. 栈的销毁。

注意:在操作栈时,要避免“上溢”和“下溢”

上溢:指栈已满,若继续存数据,则会上溢,出现报错(栈满再存出现上溢)

下溢:指栈已空,若继续取数据,则会下溢,出现报错(栈空再取出现下溢)


C 语言

栈有两种实现方式,一种是使用数组来实现,另一种是使用链表来实现。下面是总结的用数组和链表实现的优缺点。

用数组实现的优点

1 . 数组在内存中是连续存储的,因此访问元素时速度较快。CPU高速缓存命中率会更高。

2. 下标的随机访问。尾插尾删效率不错.

3. 数组实现相对简单,不需要额外的指针来维护元素之间的关系。

数组实现的缺点

1 . 数组的大小是固定的,因此在栈空间不足时需要进行扩容操作,这可能会导致性能下降。

2 . 在删除元素时,需要移动数组中的其他元素,这也可能会导致性能下降。

用链表实现的优点

1 .链表的大小可以动态调整,因此可以更好地利用空间。

2 . 任意位置插入删除O(1) ,链表的性能较高,因为不需要移动其他元素。

链表实现的缺点

1 . CPU高速缓存命中率会更低,不是连续存储的,因此访问元素时速度较慢。

2. 不支持下标的随机访问.

用链表还是用数组结构实现,这个问题的答案取决于具体的应用场景和需求,下面我们给出了数组栈和链表栈的 C 语言实现。


数组栈


#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义栈结构
typedef struct {
    int data[MAX_SIZE]; // 用数组存储栈的元素
    int top; // 栈顶指针
} Stack;
// 初始化栈
void init(Stack *stack) {
    stack->top = -1; // 初始化栈顶指针为-1,表示栈为空
}
// 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}
// 判断栈是否已满
int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}
// 入栈操作
void push(Stack *stack, int item) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->top++; // 栈顶指针加1
    stack->data[stack->top] = item; // 将元素入栈
}
// 出栈操作
int pop(Stack *stack) {
    int item;
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    }
    item = stack->data[stack->top]; // 获取栈顶元素
    stack->top--; // 栈顶指针减1
    return item;
}
// 获取栈顶元素
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->data[stack->top];
}
// 销毁栈
void destroy(Stack *stack) {
    stack->top = -1; // 将栈顶指针重置为-1,表示栈为空
}
int main() {
    Stack stack;
    init(&stack);
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);
    printf("Top element: %d\n", peek(&stack));
    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));
    printf("Top element: %d\n", peek(&stack));
    destroy(&stack);
    return 0;
}


链表栈


#include <stdio.h>
#include <stdlib.h>
// 定义链表节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// 定义栈结构
typedef struct {
    Node* top; // 栈顶指针
} Stack;
// 初始化栈
void init(Stack* stack) {
    stack->top = NULL; // 初始化栈顶指针为空
}
// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == NULL;
}
/* 由于链表实现的栈理论上没有大小限制,因此不存在“栈满”的情况。在入栈操作时只需要创建新节点,并将其插入到链表头部即可。
如需限制栈的大小,可以通过设置一个变量来记录当前栈中存储的元素个数,然后在入栈时进行判断,若已满则不允许再次入栈。*/
// 入栈操作
void push(Stack* stack, int item) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = item; // 设置新节点的数据为要入栈的元素
    newNode->next = stack->top; // 将新节点插入到栈顶
    stack->top = newNode; // 更新栈顶指针
}
// 出栈操作
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    }
    Node* topNode = stack->top; // 获取栈顶节点
    int item = topNode->data; // 获取栈顶元素
    stack->top = topNode->next; // 更新栈顶指针
    free(topNode); // 释放栈顶节点的内存
    return item;
}
// 获取栈顶元素
int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->top->data;
}
// 销毁栈
void destroy(Stack* stack) {
    while (!isEmpty(stack)) {
        pop(stack);
    }
}
int main() {
    Stack stack;
    init(&stack);
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);
    printf("Top element: %d\n", peek(&stack));
    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));
    printf("Top element: %d\n", peek(&stack));
    destroy(&stack);
    return 0;
}


队列


队列是栈的兄弟结构,是只允许在一端进行插入元素操作,在另一端进行删除元素操作的线性数据结构。进行插入操作的一端称为队尾,进行删除操作的一端称为队头。队列中的数据元素遵守先进先出 FIFO(First In First Out)的原则,即最先进入的元素最先被访问。



队列的特点

  1. 先进先出(FIFO):第一个插入的元素是第一个被删除的元素,因此表现为先进先出的顺序。
  2. 元素只能从队尾插入(入队)和从队头删除(出队)。

队列的应用

  1. 消息传递:在消息传递模型中,消息被发送到队列中等待接收方进行处理。发送方可以通过入队操作向队列发送消息,而接收方则通过出队操作从队列中获取消息。
  2. 缓存区管理:在网络通信、磁盘I/O等场景中,队列被用于管理数据的缓冲区。接收到的数据被放入队列中,然后按照一定的规则从队列中取出,保证数据按照顺序传输。
  3. 任务调度:操作系统中的任务调度通常使用队列来管理待执行的任务,按照先来先服务(First-Come-First-Served,FCFS)的原则进行调度。
  4. 广度优先搜索:图的广度优先搜索算法(BFS)使用队列来保存待访问的节点。从起始节点开始,将其放入队列中,然后不断从队列中取出节点,并将其邻接节点放入队列,直到队列为空。

队列的基本操作

  1. 入队(enqueue):将元素插入到队列的末尾。
  2. 出队(dequeue):从队列的头部删除一个元素并返回。
  3. 获取队列头部元素的值。
  4. 获取队列中元素的个数。
  5. 判断队列是否为空、是否已满。
  6. 队列的销毁


C 语言

队列有两种实现方式,一种是使用数组来实现,另一种是使用链表来实现。下面是总结的用数组和链表实现的优缺点。

用数组实现的优点

1 . 数组在内存中是连续存储的,因此访问元素时速度较快。CPU高速缓存命中率会更高。

2 . 数组实现相对简单,不需要额外的指针来维护元素之间的关系。

数组实现的缺点

1 . 需要事先确定队列的最大长度,这可能会导致性能下降。

2 . 需要移动元素来保持队列的顺序。

用链表实现的优点

1 . 不需要事先确定队列的最大长度,可以动态扩展。

2 . 插入和删除操作只需要修改指针,不需要移动元素。

3 . 可以实现多个队列共享一个链表。

链表实现的缺点

1 . CPU高速缓存命中率会更低,不是连续存储的,因此访问元素时速度较慢。

2 .实现相对复杂。

用链表还是用数组结构实现,这个问题的答案取决于具体的应用场景和需求,下面我们给出了数组队列和链表队列的 C 语言实现。


数组队列


#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 队列的最大大小
// 定义队列结构体
struct queue {
    int* arr; // 数组指针
    int front; // 队首位置
    int rear; // 队尾位置
    int size; // 当前队列中存储的元素个数
};
// 初始化队列
struct queue* init() {
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    q->arr = (int*)malloc(MAX_SIZE * sizeof(int));
    q->front = 0;
    q->rear = -1;
    q->size = 0;
    return q;
}
// 判断队列是否为空
int is_empty(struct queue* q) {
    return q->size == 0;
}
// 判断队列是否已满
int is_full(struct queue* q) {
    return q->size == MAX_SIZE;
}
// 入队
void enqueue(struct queue* q, int value) {
    if (is_full(q)) {
        printf("Queue Overflow\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->arr[q->rear] = value;
    q->size++;
}
// 出队
int dequeue(struct queue* q) {
    if (is_empty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }
    int value = q->arr[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return value;
}
// 获取队首元素
int front(struct queue* q) {
    if (is_empty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }
    return q->arr[q->front];
}
// 获取队列长度
int size(struct queue* q) {
    return q->size;
}
// 销毁队列
void destroy(struct queue* q) {
    free(q->arr);
    free(q);
}
int main() {
    struct queue* q = init();
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    printf("%d\n", dequeue(q)); // 输出10
    printf("%d\n", front(q)); // 输出20
    enqueue(q, 40);
    printf("%d\n", dequeue(q)); // 输出20
    printf("%d\n", dequeue(q)); // 输出30
    printf("%d\n", dequeue(q)); // 输出40
    printf("%d\n", dequeue(q)); // 输出Queue Underflow
    destroy(q); // 销毁队列
    return 0;
}


链表队列

#include <stdio.h>
#include <stdlib.h>
// 定义队列节点结构体
struct queue_node {
    int data;
    struct queue_node* next;
};
// 定义队列结构体
struct queue {
    struct queue_node* front; // 队首指针
    struct queue_node* rear; // 队尾指针
    int size; // 当前队列中存储的元素个数
};
// 初始化队列
struct queue* init() {
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
    return q;
}
// 判断队列是否为空
int is_empty(struct queue* q) {
    return q->size == 0;
}
// 同链表栈,链表队列没有固定的大小限制,因此不需要判断队列是否已满
// 入队
void enqueue(struct queue* q, int value) {
    // 创建新节点
    struct queue_node* new_node = (struct queue_node*)malloc(sizeof(struct queue_node));
    new_node->data = value;
    new_node->next = NULL;
    if (is_empty(q)) {
        q->front = new_node;
        q->rear = new_node;
    } else {
        q->rear->next = new_node;
        q->rear = new_node;
    }
    q->size++;
}
// 出队
int dequeue(struct queue* q) {
    if (is_empty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }
    struct queue_node* temp = q->front;
    int value = temp->data;
    if (q->front == q->rear) {
        q->front = NULL;
        q->rear = NULL;
    } else {
        q->front = q->front->next;
    }
    free(temp);
    q->size--;
    return value;
}
// 获取队首元素
int front(struct queue* q) {
    if (is_empty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }
    return q->front->data;
}
// 获取队列长度
int size(struct queue* q) {
    return q->size;
}
// 销毁队列
void destroy(struct queue* q) {
    while (!is_empty(q)) {
        dequeue(q);
    }
    free(q);
}
int main() {
    struct queue* q = init();
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    printf("%d\n", dequeue(q)); // 输出10
    printf("%d\n", front(q)); // 输出20
    enqueue(q, 40);
    printf("%d\n", dequeue(q)); // 输出20
    printf("%d\n", dequeue(q)); // 输出30
    printf("%d\n", dequeue(q)); // 输出40
    printf("%d\n", dequeue(q)); // 输出Queue Underflow
    destroy(q); // 销毁队列
    return 0;
}


结论


栈和队列作为常见的数据结构,在算法和程序设计中扮演着重要的角色。本文总结了栈和队列的特点、应用场景以及C语言实现。通过深入理解它们的原理和应用,可以更好地解决问题和优化算法。希望本文能够对读者对栈和队列的学习和应用提供帮助。

相关文章
|
17天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
91 9
|
8天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
17 1
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
69 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
11天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
14天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
16天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
43 4
|
20天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
32 4
|
1月前
数据结构(栈与列队)
数据结构(栈与列队)
18 1
|
1月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
17 0