登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 科技 ›栈与队列

栈与队列

归筠溪 昨天 17:58
github仓库：https://github.com/EanoJiang/Data-structures-and-algorithms
栈与队列

栈（stack）

类比成一摞盘子，最上面的盘子就是栈顶，最下面的就是栈底。把元素添加到栈顶是入栈，删除栈顶就是出栈。
“先入后出"
1.png

顺序实现

栈的结构
  1. #define MAXSIZE 100
  2. typedef int ElemType;
  4. typedef struct {
  5.     ElemType data[MAXSIZE];
  6.     int top;
  7. } Stack;
复制代码
栈的初始化

2.png
  1. // 初始化栈
  2. void initStack(Stack *s) {
  3.     s->top = -1;
  4. }
复制代码
栈的常用操作

3.png

入栈
  1. //入栈
  2. int push(Stack *s, ElemType e){
  3.     if(s->top == MAXSIZE-1){
  4.         printf("栈满\n");
  5.         return 0;
  6.     }
  7.     s->top++;
  8.     //从栈顶入栈
  9.     s->data[s->top] = e;
  10.     return 1;
  11. }
复制代码
出栈
  1. //出栈
  2. ElemType pop(Stack *s,ElemType *e){
  3.     if(s->top == -1){
  4.         printf("栈空\n");
  5.         return 0;
  6.     }
  7.     *e = s->data[s->top];
  8.     s->top--;
  9.     return *e;
  10. }
复制代码
查看栈顶元素
  1. //查看栈顶元素
  2. ElemType getTop(Stack *s,ElemType *e){
  3.     if(s->top == -1){
  4.         printf("栈空\n");
  5.         return 0;
  6.     }
  7.     *e = s->data[s->top];
  8.     return *e;
  9. }
复制代码
  1. int main(){
  2.     Stack s;
  3.     initStack(&s);
  4.     push(&s,1);
  5.     push(&s,2);
  6.     push(&s,3);
  7.     ElemType elem;
  8.     getTop(&s,&elem);
  9.     printf("栈顶元素:%d\n",elem);
  10.     pop(&s,&elem);
  11.     printf("出栈元素:%d\n",elem);
  12.     printf("栈顶元素:%d\n",getTop(&s,&elem));
  13.     return 0;
  15. }
复制代码
顺序表_动态分配
  1. #include #include #define MAXSIZE 100typedef int ElemType;typedef struct {    ElemType *data;    int top;} Stack;// 初始化栈Stack* initStack() {    Stack *s = (Stack*)malloc(sizeof(Stack));    s->data = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));    s->top = -1;    return s;}//入栈
  2. int push(Stack *s, ElemType e){
  3.     if(s->top == MAXSIZE-1){
  4.         printf("栈满\n");
  5.         return 0;
  6.     }
  7.     s->top++;
  8.     //从栈顶入栈
  9.     s->data[s->top] = e;
  10.     return 1;
  11. }//出栈
  12. ElemType pop(Stack *s,ElemType *e){
  13.     if(s->top == -1){
  14.         printf("栈空\n");
  15.         return 0;
  16.     }
  17.     *e = s->data[s->top];
  18.     s->top--;
  19.     return *e;
  20. }//查看栈顶元素
  21. ElemType getTop(Stack *s,ElemType *e){
  22.     if(s->top == -1){
  23.         printf("栈空\n");
  24.         return 0;
  25.     }
  26.     *e = s->data[s->top];
  27.     return *e;
  28. }int main(){    Stack *s = initStack();    push(s,1);    push(s,2);    push(s,3);    ElemType elem;    getTop(s,&elem);    printf("栈顶元素:%d\n",elem);    pop(s,&elem);    printf("出栈元素:%d\n",elem);    printf("栈顶元素:%d\n",getTop(s,&elem));    free(s->data);    free(s);    return 0;}
复制代码
链式实现
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  5. typedef int ElemType;
  7. typedef struct Stack{
  8.     ElemType data;
  9.     struct Stack *next;
  10. }Stack;
  12. Stack* initStack(){
  13.     Stack *s = (Stack*)malloc(sizeof(Stack));
  14.     s->next = NULL;
  15.     return s;
  16. }
  18. //判断栈是否为空
  19. bool isEmpty(Stack *s){
  20.     return s->next == NULL;
  21. }
  22. //入栈
  23. //头插法
  24. int push(Stack *s, ElemType e){
  25.     Stack *p = (Stack*)malloc(sizeof(Stack));
  26.     p->data = e;
  27.     p->next = s->next;
  28.     s->next = p;
  29.     return 1;
  30. }
  32. //出栈
  33. //删去头结点的next
  34. ElemType pop(Stack *s, ElemType *e){
  35.     if(s->next == NULL){
  36.         printf("栈为空！\n");
  37.         return 0;
  38.     }
  39.     *e = s->next->data;
  41.     Stack *p = s->next;
  42.     s->next = p->next;
  43.     free(p);
  45.     return *e;
  46. }
  48. //获取栈顶元素
  49. ElemType getTop(Stack *s){
  50.     if(s->next == NULL){
  51.         printf("栈为空！\n");
  52.         return 0;
  53.     }
  54.   
  55.     return s->next->data;
  56. }
  58. int main(){
  59.     Stack *s = initStack();
  60.     push(s,1);
  61.     push(s,2);
  62.     push(s,3);
  63.     printf("栈顶元素:%d\n",getTop(s));
  64.     ElemType elem;
  65.     pop(s,&elem);
  66.     printf("出栈元素:%d\n",elem);
  67.     printf("栈顶元素:%d\n",getTop(s));
  68.     free(s);
  69.     return 0;
  70.   
  71. }
复制代码
队列(queue)

先入先出
入队：队尾入队
出队：队首出队
4.png

5.png

顺序实现

队列结构
  1. #define MAXSIZE 100
  3. typedef int ElemType;
  5. typedef struct{
  6.     ElemType data[MAXSIZE];
  7.     int front, rear;
  8. }Queue;
复制代码
初始化
  1. int initQueue(){
  2.     Queue *q = (Queue*)malloc(sizeof(Queue));
  3.     if(q == NULL){
  4.         return -1;
  5.     }
  6.     q->front = 0;
  7.     q->rear = 0;
  8.     return q;
  9. }
复制代码
判断是否为空

6.png

7.png
  1. bool isEmpty(Queue *q){
  2.     return q->front == q->rear;
  3. }
复制代码
出队

8.png
  1. //出队
  2. //从队首出队
  3. ElemType pop(Queue *q,ElemType *e){
  4.     if(isEmpty(q)){
  5.         printf("队列为空！\n");
  6.         return -1;
  7.     }
  8.     *e = q->data[q->front];
  9.     q->front++;
  10.     return *e;
  11. }
复制代码
入队

9.png

10.png
  1. //队首是空
  2. bool frontIsEmpty(Queue *q){
  3.     if(q->front == 0){
  4.         printf("队首不空\n");
  5.         return 0;
  6.     }
  7.     //队首索引不为0,说明前面有空的位置，需要挪过去
  8.     else{
  9.         int step = q->front;
  10.         for(int i = q->front;i <= q->rear;i++){
  11.             q->data[i-step] = q->data[i];
  12.         }
  13.         q->front = 0;
  14.         q->rear = q->rear - step;
  15.         return 1;
  16.     }
  17.   
  18. }
  20. //入队
  21. //从队尾入队
  22. int push(Queue *q, ElemType e){
  23.     //队尾到头的情况下，队首不空，说明队列已满
  24.     if(q->rear == MAXSIZE-1 && !frontIsEmpty(q)){
  25.         printf("队列已满！\n");
  26.         return 0;
  27.     }
  28.     q->data[q->rear] = e;
  29.     q->rear++;
  30.     return 1;
  32. }
复制代码
获取队首元素
  1. //获取队首元素
  2. ElemType getFront(Queue *q){
  3.     if(isEmpty(q)){
  4.         printf("队列为空！\n");
  5.         return -1;
  6.     }
  7.     return q->data[q->front];
  8. }
复制代码
  1. int main(){
  2.     Queue* q = initQueue();
  3.     push(q,1);
  4.     push(q,2);
  5.     push(q,3);
  6.     push(q,4);
  8.     printf("队首元素为：%d\n",getFront(q));
  10.     ElemType e;
  11.     pop(q,&e);
  12.     printf("出队元素为：%d\n",e);
  13.     pop(q,&e);
  14.     printf("出队元素为：%d\n",e);
  15.     return 0;
  16. }
复制代码
顺序实现_动态内存分配

只有结构体和初始化的区别，其他都一样
  1. typedef struct
  2. {
  3.     ElemType *data;
  4.     ElemType front, rear;
  5. } Queue;
  7. Queue *initQueue()
  8. {
  9.     Queue *q = (Queue *)malloc(sizeof(Queue));
  10.     q->data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
  11.     q->front = 0;
  12.     q->rear = 0;
  13.     return q;
  14. }
复制代码
循环队列

11.png
  1. #include #include #include // 最大容量#define MAXSIZE 4typedef int ElemType;typedef struct
  2. {
  3.     ElemType *data;
  4.     ElemType front, rear;
  5. } Queue;
  7. Queue *initQueue()
  8. {
  9.     Queue *q = (Queue *)malloc(sizeof(Queue));
  10.     q->data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
  11.     q->front = 0;
  12.     q->rear = 0;
  13.     return q;
  14. }int count = 0;bool isEmpty(Queue *q){    return count == 0 && q->rear == q->front;}// 入队// 从队尾入队int push(Queue *q, ElemType e){    // 队列满的时候，rear+1 == MAXSIZE，因为rear和front都是从0开始计数的    if (count == MAXSIZE && (q->rear + 1) % MAXSIZE == q->front)    {        printf("队列已满！\n");        return -1;    }    q->data[q->rear] = e;    //更新rear索引    q->rear = (q->rear + 1) % MAXSIZE;    count++;    printf("当前的元素个数为:%d\n",count);    return 1;}// 出队// 从队首出队ElemType pop(Queue *q, ElemType *e){    if (isEmpty(q))    {        printf("队列为空！\n");        return -1;    }    *e = q->data[q->front];    //更新front索引    q->front = (q->front + 1) % MAXSIZE;    count--;    printf("当前的元素个数为:%d\n",count);    return *e;}// 获取队首元素ElemType getFront(Queue *q){    if (isEmpty(q))    {        printf("队列为空！\n");        return -1;    }    return q->data[q->front];}int main()
  15. {
  16.     Queue *q = initQueue();
  17.     push(q, 1);
  18.     push(q, 2);
  19.     push(q, 3);
  20.     push(q, 4);
  22.     printf("队首元素为：%d\n", getFront(q));
  24.     ElemType e;
  25.     pop(q, &e);
  26.     printf("出队元素为：%d\n", e);
  27.     pop(q, &e);
  28.     printf("出队元素为：%d\n", e);
  29.     return 0;
  30. }
复制代码
定义一个count变量用来记录当前元素的总个数，防止循环队列总是存不满的情况
也就是下面的情况：
12.png

rear总是指向队尾的下一个索引，那么满队列判断的时候1==1，满了，但实际没满，所以再加一个变量count的判断
链式实现

队列结构
  1. // 最大容量
  2. typedef int ElemType;
  4. // 队列节点
  5. typedef struct QueueNode
  6. {
  7.     ElemType data;
  8.     struct QueueNode *next;
  9. } QueueNode;
  11. // 队列
  12. typedef struct{
  13.     QueueNode *front;
  14.     QueueNode *rear;
  15. }Queue;
复制代码
初始化
  1. Queue* initQueue()
  2. {
  3.     QueueNode *qNode = (QueueNode *)malloc(sizeof(QueueNode));
  4.     qNode->data = 0;
  5.     qNode->next = NULL;
  6.     Queue *q = (Queue *)malloc(sizeof(Queue));
  7.     q->front = qNode;
  8.     q->rear = qNode;
  10.     return q;
  11. }
复制代码
队列是否空
  1. // 队列是否为空
  2. bool isEmpty(Queue *q)
  3. {
  4.     return q->rear == q->front;
  5. }
复制代码
入队

尾插法
13.png

14.png

15.png
  1. // 入队
  2. // 从队尾入队
  3. // 尾插法
  4. int push(Queue *q, ElemType e)
  5. {
  6.     QueueNode *qNode = (QueueNode *)malloc(sizeof(QueueNode));
  7.     qNode->data = e;
  8.     qNode->next = NULL;
  9.     //插在尾节点的next
  10.     q->rear->next = qNode;
  11.     q->rear = qNode;
  12.     return 1;
  13. }
复制代码
出队
  1. // 出队
  2. // 从队首出队
  3. ElemType pop(Queue *q, ElemType *e)
  4. {
  5.     QueueNode *qnode = q->front->next;
  6.     *e = qnode->data;
  7.     q->front->next = qnode->next;
  8.     if(q->rear == qnode){
  9.         q->rear = q->front;
  10.     }
  11.     free(qnode);
  12.     return *e;
  13. }
复制代码
队首元素
  1. // 获取队首元素
  2. ElemType getFront(Queue *q)
  3. {
  4.     if (isEmpty(q))
  5.     {
  6.         printf("队列为空！\n");
  7.         return -1;
  8.     }
  9.     return q->front->next->data;
  10. }
复制代码
  1. int main()
  2. {
  3.     Queue *q = initQueue();
  4.     push(q, 1);
  5.     push(q, 2);
  6.     push(q, 3);
  7.     push(q, 4);
  9.     printf("队首元素为：%d\n", getFront(q));
  11.     ElemType e;
  12.     pop(q, &e);
  13.     printf("出队元素为：%d\n", e);
  14.     pop(q, &e);
  15.     printf("出队元素为：%d\n", e);
  16.     return 0;
  17. }
复制代码
双端队列

16.png

习题1
17.png

选c
习题2
18.png

选d
习题3
19.png

选c
习题4
20.png

4个
dcbae
dcbea
dceba
decba
习题5
21.png

入队更新：
front指向队头
rear = (rear+1)%MAXSIZE
下面对每个选项进行验证，注意初始为空队列，front==rear：
a. rear递增后为1，错误
d.rear递增后为0，正确
选d
习题6
22.png

只有3不可能，n-1
习题7
23.png

选a
循环队列，队空条件: front == rear,   队满条件: front == (rear+1)%MAXSIZE
习题8
24.png

队列
98
7654
32
1
选c
习题9
25.png

入栈次序不能决定出栈顺序，栈不能两端操作，选c
习题10
26.png

注意栈顶位置
5 8 3 2(top)        2+3
8 3 2 5(top)        5-2
3 2 5 3(top)        3*5
2 5 3 15(top)
习题11
27.png

28.jpeg

选c
习题12
29.png

选d
总结

30.png


来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
相关推荐
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
归筠溪
昨天 17:58

0

粉丝关注

11

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫