数据结构4：栈和队列

栈

栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（bottom）。不含元素的空表称为空栈。
假设 S=(a1, a2, …, an)，则称 a1 为栈底元素，an 为栈顶元素。栈中元素按 a1, a2, …,an 的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按照后进先出的原则进行的。因此，栈又称为后进先出（Last In First Out, LIFO）的线性表。

类似于手枪的弹匣，最先压进去的子弹是最后打出去的一发。

所以，栈是限制插入和删除操作只能在一个位置进行的表，该位置是表的末端，叫作
栈顶（top）。对栈的基本操作有进栈（push）和出栈（Pop），前者相当于插入，
后者则是删除最后插入的元素。

栈的设置和初始化

一个栈一般需要一个数据域和一个栈指针（用于调用栈里面的元素）。

代码实现：

typedef struct stack {
    int top;
    int data[10000];
    } stack;

void initstack(stack *s) {
    s->top = -1;  //设置栈为空
}

压栈

往栈内增加元素类似于把子弹压入弹匣，故名。

代码实现:

void push(stack *s, int x) {
    if (s->top == 9999) {
        printf("栈满\n");
        return;
    }
    s->top++;
    s->data[s->top] = x;
}

出栈

删除栈内的元素类似于把子弹从弹匣内弹出，故名。

代码实现：

void pop(stack *s, int *x) {
    if (s->top == -1) {
        printf("栈空\n");
        return;
    }
    *x = s->data[s->top];
    s->top--;
}

这会把删除的元素赋予传入参数的指针x中

栈的链式结构

我们往往和链表一样，需要动态的内存分配的链式结构。

一般地，如果你详细阅读我之前的链表笔记，你就能理解链式结构的实现。

类似地：一个数据域，一个栈指针，一个指针域。

S是头节点，我们称它为栈顶指针，下一个节点就是栈顶。

typedef struct {
    int *data;
    int top;
    struct stack *next;
} stack;

stack* init_stack() {
    stack *s = (stack*)malloc(sizeof(stack));
    s->data = (int*)malloc(100 * sizeof(int));
    s->top = -1;
    s->next = NULL; //初始栈的指针为空
    return s;
}

链式结构的压栈

这里使用了头插法，即新节点插入到链表的头部，也就是栈顶。

所以，头插法符合栈的结构特点。

int push(stack *s, int x) {
    stack *new_s = (stack*)malloc(sizeof(stack));
    new_s->data = x;
    new_s->next = s -> next;  //如果s是栈顶指针的话，新节点的指针就是指向null
    s -> next = new_s;
    return 1;
}

链式结构的出栈

出栈操作类似于链表的从头删除节点，我们通过改变栈顶的元素的指针，使得头节点和新的栈顶连接起来。

int pop(stack *s, int *x) {
    if (s->next == NULL) {
        printf("这个栈为空！\n");
        return 0;
    }
    *x = s->next->data; //一样地，会把删除的元素放进传入指针里
    stack *temp = s->next;    //临时指针
    s->next = s->next->next;   //使得下一个节点成为新的栈顶
    free(temp);   //释放出栈节点
    return 1;
}

获取栈顶元素

没什么好说的，头节点的后继节点的数据域就是栈顶元素。

int get_top(stack *s, int *x) {
    if (s->next == NULL) {
        printf("这个栈为空！\n");
        return 0;
    }
    *x = s->next->data;
    return 1;
}

栈和单链表的关系

单链表的头插法和头删法可以用来实现栈的行为。栈是一种后进先出（LIFO，Last In First Out）的数据结构，而单链表的头插法和头删法正好符合栈的操作特性。

栈的特性：
- 后进先出（LIFO）：最后插入的元素最先被移除。
- 主要操作：
  - push：将元素插入栈顶。
  - pop：从栈顶移除元素。
  - peek：查看栈顶元素。
  - isEmpty：检查栈是否为空。
单链表的头插法和头删法：
- 头插法：将新节点插入到链表的头部。
- 头删法：从链表的头部删除节点。
栈和单链表的映射：
- 栈的 push 操作对应单链表的头插法。
- 栈的 pop 操作对应单链表的头删法。
- 栈顶对应单链表的头部。

从这方面来看，栈其实是单链表的一个衍生。

队列

队列（queue）是一种先进先出（First In First Out, FIFO）的线性表。它只
允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入的一端称为
队尾（rear）,允许删除的一端则称为队头（front）。假设队列为 q = (a1, a2, …,
an)，那么，a1 就是队头元素，an 就是队尾元素。队列中的元素是按照 a1, a2, …,
an 的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在 a1,
a2, …, an-1 都离开队列之后，an 才能退出队列。

我会展示队列的动画，可能有点长。

QQ录屏20250406134123

生成队列和初始化

typedef struct node{
    int data;
    int front;
    int rear;
}queue;

void initqueue(queue *q){
    q->front= 0;
    q->rear= 0;
}

判断队列是否为空

只要队列的队头和队尾相等，就代表队列为空，至于为什么请看上面的动画。

void is_queue_empty(queue *q){
    if(q->front == q->rear){
        printf("Queue is empty\n");
    }
    else{
        printf("Queue is not empty\n");
    }
}

出队

void dequeue(queue *q){
    if(q->front == q->rear){
        printf("Queue is empty\n");
    }
    else{
        q->front++;
    }
}

队列调整

rear==Max_value的时候不代表队列就是满的，如下面这种情况。

所以，我们需要调整队列，我们需要把这一连串的数据往队头移动。

不可避免地，这会造成一个比较高的时间复杂度。

代码实现：

int queue_full(queue *q){
    if (q->frint > 0 ){
        int step = q->rear;
        for (int i = q->front; i <= q->rear; i++){
            {
                q -> data[i-step] = q -> data[i];    //移动数据
            }
            q->front = 0;
            q->rear = q->rear - step;
        }
        return 1;
    }
    else{
        printf("Queue is  full\n");
        return 0;
    }
}

入队

int  enqueue(queue *q, int data){
    if(q->rear == 100){
        if(!queue_full(q)){
            return 0;
        }
    }
    q->rear++;
    q->data[q->rear] = data;
    return 1;
}

网络工程算法

#网络工程 #算法

数据结构4：双向链表下一篇

数据结构5：栈和队列

数据结构4：栈和队列

栈

栈的设置和初始化

压栈

出栈

栈的链式结构

链式结构的压栈

链式结构的出栈

获取栈顶元素

栈和单链表的关系

队列

生成队列和初始化

判断队列是否为空

出队

队列调整

入队