墨滴
江

江小南

V1

2022/12/10阅读：33主题：萌绿

【408篇】C语言笔记-第十三章（栈与队列&考研真题实战）

第一节：栈的原理

1. 栈

stack:堆栈，又称栈或堆叠，先进后出-FILO(First In Last Out)。

栈：只允许在一端进行插入或删除操作的线性表，栈顶（Top）。

2. 栈的基本操作：

顺序存储实现栈：

typedef struct{
    Elemtype data[50];
    int top;
}SqStack;
SqStack S;

元素入栈：

S.data[++S.top]=4

# 相当于以下两行
S.top=S.top+1;
S.data[S.top]=4;

元素出栈：

x=S.data[S.top--];

# 相当于以下两行，x表示出栈的元素值
x=S.data[S.top];
S.top=S.top-1;

空栈：

# 表示栈为空，可以作为初始化栈
S.top=-1

栈满：

# 表示栈满
S.top=MaxSize-1;

链式存储实现栈：

初始化栈:

# 空栈，也可以初始化栈
LiStack Lhead=(LiStack)malloc(sizeof(struct Linknode));
Lhead->next=NULL;
LiStack top=NULL;

入栈：

top=(LiStack)malloc(sizeof(struct Linknode));
top->next=NULL;
top->data=1;
top->next=Lhead->next;
Lhead->next=top;

出栈：

# c为要出栈的元素。链表表示栈，相当于头插法，那么出栈就表示为
c=top->data;
Lhead->next=top->next;
free(top);
top=Lhead->next;

栈空栈满：

# 为真，则栈为空
Lhead->next==null

对于链表实现的栈，只要还有剩余内存，就可以继续添加元素。

第二节：初始化栈-入栈-出栈实战

#include <stdio.h>

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];  // 数组
    int top;
}SqStack;

// 初始化栈
void InitStack(SqStack &S){
    S.top=-1; // -1代表栈为空
}

// 判断栈是否为空
bool StackEmpty(SqStack S){
    if(S.top==-1){
        return true;
    } else{
        return false;
    }
}
// 入栈
bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1){  // 判断栈是否满了
        return false;
    }
    S.data[++S.top]=x;
    return true;
}
// 出栈
bool Pop(SqStack &S,ElemType x){
    if(-1==S.top){
        return false;
    }
    x=S.data[S.top--];
    return true;
}

// 获取栈顶元素
bool GetTop(SqStack S,ElemType &x){
    if(-1==S.top){
        return false;
    }
    x=S.data[S.top];
    return true;
}
int main() {
    SqStack S;
    InitStack(S); // 初始化栈
    bool flag;
    flag=StackEmpty(S);// 判断栈是否为空
    if(flag){
        printf("stack is empty\n");
    }
    Push(S,3);  // 入栈
    Push(S,4);
    Push(S,5);
    Push(S,6);
    Push(S,7);
    Push(S,8); // 只能放5个元素，8实际没有放入
    ElemType m;
    flag=GetTop(S,m);// 获取栈顶元素
    if(flag){
        printf("top is %d\n",m);
    }
    flag=Pop(S,m); // 出栈
    if(flag){
        printf("pop is %d\n",m);
    }
    flag=GetTop(S,m);// 获取栈顶元素
    if(flag){
        printf("top is %d\n",m);
    }
    return 0;
}
F:\Computer\Project\practice\13\13.2-stack\cmake-build-debug\13_2_stack.exe
stack is empty
top is 7
pop is 7
top is 6

进程已结束，退出代码为 0

第三节：队列-循环队列原理解析

1. 队列

队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队，删除元素称为出队或离队。先进先出-FIFO（First In First Out）。

队头（Front）。允许删除的一端，又称队首。

队尾（Rear）。允许插入的一端。

特性就是先进先出（First In First Out,FIFO）

2. 循环队列

#define MaxSize 5
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize]; // 数组，存储MaxSize-1个元素
    int front,rear; // 队列头，队列尾
}SqQueue;

SqQueue Q;

解读：循环队列依靠front和rear两个指针同时工作，当front和rear同时指向同一个位置时，说明是初实化状态，队列为空，但是对于d1图的情况，指向同一个位置，但是并不是为空。所以采用的方法就是d2的情况，牺牲一个存储单元。

循环队列元素入队：

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front){ // 判断队列是否已满
        return false;
    }
    Q.data[Q.rear]=x; // 放入元素
    Q.rear=(Q.rear+1)%MaxSize; // 改变队尾标记
    return true;
}

循环队列元素出队：

bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front){
        return false;
    }
    x=Q.data[Q.front];//先进先出
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

队列的链式存储：

队列的链式表示称为链队列。它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

模拟动画链接： https://www.cs.usfca.edu/~galles/visualization/QueueLL.html

存储结构：

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;  // 链表结点的结构体
typedef struct{
    LinkNode *front,*rear; // 链表头，链表尾
}LinkQueue; // 先进先出
LinkQuete Q;

第四节：循环队列实战-数组实现

#include <stdio.h>

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; // 数组，存储MaxSize-1个元素
    int front,rear; // 队列头，队列尾
}SqQueue;

// 队列初始化
void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;  // 初始化两个指针相等且为0
}

// 判空
bool isEmpty(SqQueue &Q){
    if(Q.rear==Q.front){  // 不需要为0
        return true;
    } else{
        return false;
    }
}

// 入队
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front){ // 判断是否队满
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

// 出队
bool DeQueue(SqQueue &Q,ElemType &x){
    bool ret;
    ret=isEmpty(Q);
    if(ret){
        return false;
    }
    x=Q.data[Q.front]; // 先进先出
    Q.front=(Q.front+1)%MaxSize;
    return true;
}
int main() {
    SqQueue Q;
    bool ret; // 存储返回值
    InitQueue(Q);  // 队列初始化
    ret=isEmpty(Q); // 判空
    if(ret){
        printf("queue is empty\n");
    } else{
        printf("queue is not empty\n");
    }
    ret=EnQueue(Q,3);
    ret=EnQueue(Q,4);
    ret=EnQueue(Q,5);
    ret=EnQueue(Q,6); // 最大入队MaxSize-1个元素
    if(ret){
        printf("enqueue success\n");
    } else{
        printf("enqueue failed\n");
    }
    ret=EnQueue(Q,7); // 超过最大MaxSize-1，无法入队
    if(ret){
        printf("enqueue success\n");
    } else{
        printf("enqueue failed\n");
    }
    ElemType e; // 保存出队元素
    ret=DeQueue(Q,e);
    if(ret){
        printf("deque success %d\n",e);
    } else{
        printf("deque failed\n");
    }
    ret=DeQueue(Q,e);
    if(ret){
        printf("deque success %d\n",e);
    } else{
        printf("deque failed\n");
    }
    return 0;
}
F:\Computer\Project\practice\13\13.3-cycle-queue\cmake-build-debug\13_3_cycle_queue.exe
queue is empty
enqueue success
enqueue failed
deque success 3
deque success 4

进程已结束，退出代码为 0

第五节：循环队列实战-链表实现

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear; // 链表头，链表尾
}LinkQueue; // 先进先出

// 初始化队列
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*) malloc(sizeof(LinkNode)); // 头和尾指向同一个结点
    Q.front->next=NULL; // 头结点的next指针为NULL
}

// 入队 尾部插入法
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode*) malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s; // rear始终指向尾部
    Q.rear=s;
}

// 出队 头部删除法
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear){
        return false; // 队列尾空
    }
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;  // 断链
    if(Q.rear==p){
        Q.rear=Q.front; // 队列置为空
    }
    free(p);
    return true;
}
int main() {
    LinkQueue Q;
    InitQueue(Q);  // 初始化队列
    EnQueue(Q,3);  // 入队
    EnQueue(Q,4);
    EnQueue(Q,5);
    EnQueue(Q,6);
    EnQueue(Q,7);
    bool ret;
    ElemType e; // 存储出队元素
    ret=DeQueue(Q,e);
    if(ret){
        printf("dequeue success %d\n",e);
    } else{
        printf("dequeue failed\n");
    }
    return 0;
}
F:\Computer\Project\practice\13\13.5-queue-cycle\cmake-build-debug\13_5_queue_cycle.exe
dequeue success 3

进程已结束，退出代码为 0

第六节：考研真题

解答：

（1）采用链式存储结构（两段式单向循环链表），队头指针为front，队尾指针为rear。因为第二个要求入队时，允许增加队列占用空间，所以必须采用链式存储。

（2）初始时，创建一个只有一个空闲结点的两段式单向循环链表，头指针front和尾指针rear均指向空闲结点。

队空的判定条件：front=rear。

队满的判定条件：front==rear->next。

（3）

（4）入队操作和出队操作的基本过程

入队：

若(front==rear->next) // 队满

则在rear后面插入一个新的空闲结点。入队元素保存到rear所值节点中，rear=rear->next;返回。

出队：

若(front==rear) // 队空

则出队失败，返回；

取front所指结点中的元素e，front=front->next;返回e。

不要求代码实现，但为了理解原理，源码如下：

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next; // 指向下一个结点
}LNode,*LinkList;

// 入队
void EnQueue(LinkList front,LinkList &rear,ElemType val){
    LinkList pnew;
    if(rear->next==front){
        // 队列满，申请一个结点的空间，放入队列
        pnew=(LinkList) malloc(sizeof(LNode));
        rear->data=val; // 把入队元素放入rear指向的节点
        rear->next=pnew; // 放了一个结点，相当于做了分割
        pnew->next=front;
        rear=pnew;
    } else{ // 队列不满时，直接放入，让rear后移一个结点
        rear->data=val;
        rear=rear->next;
    }
}

// 出队
void DeQueue(LinkList &front,LinkList rear){
    if(front==rear){
        printf("queue is empty\n");
    } else{
        printf("the data is %d\n",front->data);
        front=front->next;
    }
}

void CircleQueue(LinkList &front,LinkList &rear){
    // 队列头和队列尾都指向同一个结点，这是队列既是空的，也是满的
    front=(LinkList) malloc(sizeof(LNode));
    rear=front;
    rear->next=front;
    // 入队
    EnQueue(front,rear,3);
    EnQueue(front,rear,4);
    EnQueue(front,rear,5);
    // 出队
    DeQueue(front,rear);
    DeQueue(front,rear);
    DeQueue(front,rear);
}
int main() {
    LinkList front,rear;
    CircleQueue(front,rear);
    return 0;
}
F:\Computer\Project\practice\13\13.6-2019-42\cmake-build-debug\13_6_2019_42.exe
the data is 3
the data is 4
the data is 5

进程已结束，退出代码为 0

分类：

后端

标签：

C++

作者介绍

江
江小南
V1