文章目录

• • 文档配套视频讲解链接地址
  • 第02 章 栈与队列
  • • 2.1 栈与队列的框图
    • 2.2 栈
    • • 1. 栈的概念
      • 2. 顺序栈
      • 3. 实例11 顺序栈
      • 4. 实例12 链式栈
    • 2.3 队列
    • • 1. 队列的概念
      • 2. 顺序队列
      • 3. 实例13 顺序队列
      • 4. 链式队列
      • 5. 实例14 链式队列
    • 2.4 实例15 球钟问题
    • 2.5 队列与栈的转换
    • • 1. 实例16 顺序的双栈实现一个队列
      • 2. 实例17 链式的双栈实现一个队列
      • 3. 实例18 顺序的双队列实现一个栈
      • 4. 实例19 链式的双队列实现一个栈

文档配套视频讲解链接地址

1. 腾讯课堂视频链接地址 : 14_栈与队列_顺序栈
2. 腾讯课堂视频链接地址 : 15_栈与队列_链式栈
3. 腾讯课堂视频链接地址 : 16_栈与队列_循环队列
4. 腾讯课堂视频链接地址 : 17_栈与队列_链式队列
5. 腾讯课堂视频链接地址 : 18_栈与队列_顺序双栈一队列
6. 腾讯课堂视频链接地址 : 19_栈与队列_顺序双队列一栈
7. 腾讯课堂视频链接地址 : 20_栈与队列_链式双栈一队列
8. 腾讯课堂视频链接地址 : 21_栈与队列_链式双栈一队列

第02 章 栈与队列

2.1 栈与队列的框图

2.2 栈

1. 栈的概念

栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈），允许进行操作的一端称为“栈顶”，另一固定端称为“栈底”，当栈中没有元素时称为“空栈”。

• 特点 ：后进先出（LIFO）Last In First Out
• 类比事物 , 弹夹

2. 顺序栈

• 它是顺序表的一种，具有顺序表同样的存储结构，由数组定义，配合用数组下标表示的栈顶指针top（相对指针）完成各种操作。

3. 实例11 顺序栈

• 源文件

04-ds/11-seqstack.c

• 源代码

#include  
#include 
#include 
#include // sequeue stack #define  N   32 
typedef struct 
{int data[N]; // 数组的空间int index ; // 是数组下标的索引 }seqstack_t; seqstack_t * create_empty_seqstack()
{seqstack_t * s = (seqstack_t *)malloc(sizeof(seqstack_t));memset(s->data,0,sizeof(s->data)) ; // 把数组中的内容清为0 s->index = -1 ; // 表示栈为空 return s ; 
}int seqstack_is_empty(seqstack_t * s)
{return (s->index == -1 ); 
}int seqstack_is_full(seqstack_t *s)
{return (s->index == N-1) ; 
}// 入栈 , 压栈 
int seqstack_push(seqstack_t *s, int value)
{if(seqstack_is_full(s)){printf("栈已满"); return -1 ;}s->index ++  ; s->data[s->index] = value ; return  0 ; 
}
int seqstack_pop(seqstack_t * s, int *pvalue)
{if(seqstack_is_empty(s)){printf("栈已空"); return -1 ; }*pvalue = s->data[s->index] ; s->index -- ; return 0 ; 
}int main(int argc, char const *argv[])
{seqstack_t * S = create_empty_seqstack(); printf("入栈顺序:");for(int i=0;i<33;i++){printf("%d ",i+1); seqstack_push(S,i+1); }printf("\n"); printf("出栈顺序:");for(int i=0,value;i<33;i++){seqstack_pop(S,&value); printf("%d ",value); }printf("\n"); return 0;
}

• 运行结果

入栈顺序:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 栈已满
出栈顺序:32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 栈已空1

4. 实例12 链式栈

• 源文件

04-ds/12-linkstack.c

• 源代码

#include 
#include 
#include 
#include // link stacktypedef struct node
{int data;struct node *next;
} linklist_t;linklist_t *create_empty_linkstack()
{linklist_t *s = (linklist_t *)malloc(sizeof(linklist_t));s->data = 0;s->next = NULL;return s;
}// 链表没有满  , 有空的概念
int linkstack_is_empty(linklist_t *s)
{return (s->next == NULL);
}// 头部插入法
int linkstack_push(linklist_t *s, int value)
{linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t));p->data = value;p->next = s->next;s->next = p;return 0;
}// 头部删除法
int linkstack_pop(linklist_t *s, int *pvalue)
{linklist_t *p = s->next; // p 指向s的下一个节点if(linkstack_is_empty(s)){printf("栈已空"); return -1 ; }// s->next 不为空 s->next = p->next; // 接链表 *pvalue = p->data ; // 读取数据free(p); return 0;
}int main(int argc, char const *argv[])
{linklist_t *S = create_empty_linkstack();printf("入栈顺序:");for(int i=0;i<33;i++){if( linkstack_push(S,i+1) ==  0 )  // 表示成功{printf("%d ",i+1);}}printf("\n");printf("出栈顺序:");for(int i=0,value;i<34;i++){if(linkstack_pop(S,&value) == 0 ){printf("%d ",value);}}printf("\n");return 0;
}

• 运行结果

入栈顺序:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 
出栈顺序:33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 栈已空

2.3 队列

1. 队列的概念

• 队列是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为“队尾”，允许进行删除操作的一端称为“队头”。当线性表中没有元素时，称为“空队”。
• 特点 ：先进先出（FIFO） First In First Out 。

2. 顺序队列

• 它是顺序表的一种，具有顺序表同样的储存结构，由数组定义，配合用数组下标表示的队头指针和队尾指针完成各种操作。

3. 实例13 顺序队列

• 源文件

04-ds/13-sequeue.c

• 源代码

#include 
#include 
#include 
// sequence queue#define N 32
typedef struct
{int data[N];int front; // 队列的头  , 数组的下标int rear;  // 队列的尾  , 数组的下标
} sequeue_t;// 空队列的概念是 : 队头等于队尾
// 为了区分空队 和满队 , 队列元素个数要比数组元素少一个
// 满队+1 等于空队
// 1 2 3 4 5
// f       f
// rsequeue_t *create_empty_sequeue()
{sequeue_t *q = (sequeue_t *)malloc(sizeof(sequeue_t));memset(q->data, 0, sizeof(q->data));q->front = q->rear = N - 1; //指向数组最后一个元素return q;
}int sequeue_is_empty(sequeue_t *q)
{return (q->front == q->rear);
}int sequeue_is_full(sequeue_t *q)
{// 队尾 +1 == 队头 , 就是满队// 任何一个一个数对N求余 , 这个数的范围是  0 - N-1return ((q->rear + 1) % N == q->front);
}int sequeue_enqueue(sequeue_t *q, int value)
{if (sequeue_is_full(q)){printf("队列已满");return -1;}q->rear = (q->rear + 1) % N; // 防止数组越界q->data[q->rear] = value;return 0;
}
int sequeue_dequeue(sequeue_t *q, int *pvalue)
{if (sequeue_is_empty(q)){printf("队列已空");return -1;}q->front = (q->front + 1) % N; // 防止数组越界*pvalue = q->data[q->front];return 0;
}int main(int argc, char const *argv[])
{sequeue_t *Q = create_empty_sequeue();//  这个队列, 最多可以存放 31 个元素printf("入队顺序为:");for (int i = 0; i < 32; i++){if (sequeue_enqueue(Q, i + 1) == 0){printf("%d ", i + 1);}}printf("\n");printf("出队顺序为:");for (int i = 0,value; i < 32; i++){if (sequeue_dequeue(Q, &value) == 0){printf("%d ", value);}}printf("\n");return 0;
}

• 运行结果

入队顺序为:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 队列已满
出队顺序为:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 队列已空

4. 链式队列

链式队列的尾部插入

5. 实例14 链式队列

• 源文件

04-ds/14-linkqueue.c

• 源代码

#include 
#include 
#include 
// sequence queuetypedef struct node
{int data;struct node *next;
} linklist_t;typedef struct
{linklist_t *front; // 队头linklist_t *rear;  // 队尾
} linkqueue_t;// 空队列的概念是 : 队头等于队尾
// 为了区分空队 和满队 , 队列元素个数要比数组元素少一个
// 满队+1 等于空队
// 1 2 3 4 5
// f       f
// rlinkqueue_t *create_empty_linkqueue()
{linklist_t *h = (linklist_t *)malloc(sizeof(linklist_t));linkqueue_t *q = (linkqueue_t *)malloc(sizeof(linkqueue_t));q->front = q->rear = h;q->front->data = 0;return q;
}int linkqueue_is_empty(linkqueue_t *q)
{return (q->front == q->rear);
}// 链式队列没有满的概念
// int linkqueue_is_full(linkqueue_t *q)
// {// }// 入队 队尾加
int linkqueue_enqueue(linkqueue_t *q, int value)
{linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t));p->data = value;p->next = q->rear->next; // 尾部插入第1步q->rear->next = p;       // 尾部插入第2步q->rear = p;             // 尾部插入第3步return 0;
}// 头部出队列 , 头部删除法
int linkqueue_dequeue(linkqueue_t *q, int *pvalue)
{linklist_t *p;if (linkqueue_is_empty(q)){printf("队列为空");return -1;}p = q->front->next;           // 头节点的下一个节点  , p是要删除的节点q->front->next = p->next;     // 接上链表if (q->front->next == NULL) // 此时队列为空q->rear = q->front; // *pvalue = p->data;free(p);return 0;
}int main(int argc, char const *argv[])
{linkqueue_t *Q = create_empty_linkqueue();//  这个队列, 最多可以存放 31 个元素printf("入队顺序为:");for (int i = 0; i < 32; i++){if (linkqueue_enqueue(Q, i + 1) == 0){printf("%d ", i + 1);}}printf("\n");printf("出队顺序为:");for (int i = 0, value; i < 33; i++){if (linkqueue_dequeue(Q, &value) == 0){printf("%d ", value);}}printf("\n");return 0;
}

• 运行结果

入队顺序为:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 
出队顺序为:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 队列为空

2.4 实例15 球钟问题

• 队列与栈应用

• 问题描述：球钟是一个利用球的移动来记录时间的简单装置。它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器。若分钟指示器中有2个球，五分钟指示器中有6个球，小时指示器中有5个球，则时间为5:32

• 工作原理：每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可容纳4个球。当放入第五个球时，在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾。而第五个球就会进入五分钟指示器。按此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球。

• 当小时指示器放入第12个球时，原来的11个球按照他们被放入时的相反顺序加入球队列的队尾，然后第12个球也回到队尾。这时，三个指示器均为空，回到初始状态，从而形成一个循环。因此，该球钟表示时间的范围是从0：00到11：59。

  现设初始时球队列的球数为27，球钟的三个指示器初态均为空。问，要经过多久，球队列才能回复到原来的顺序?

  Q : 是队列, 队列可以存放27个球

  S1: 是栈, 1分钟指示器, 里面可以存放5个球

  S5 : 是栈, 表示的5分钟的指示器, 里面可以存放12个球

  S60: 是栈, 表示小时指示器, 里面可以存放12个球

• 源文件

04-ds/15-ballclock.c

• 源代码

#include 
#include 
#include 
// sequence queue#define N 128
typedef struct
{int data[N];int front; // 队列的头  , 数组的下标int rear;  // 队列的尾  , 数组的下标
} sequeue_t;// 空队列的概念是 : 队头等于队尾
// 为了区分空队 和满队 , 队列元素个数要比数组元素少一个
// 满队+1 等于空队
// 1 2 3 4 5
// f       f
// rsequeue_t *create_empty_sequeue()
{sequeue_t *q = (sequeue_t *)malloc(sizeof(sequeue_t));memset(q->data, 0, sizeof(q->data));q->front = q->rear = N - 1; //指向数组最后一个元素return q;
}int sequeue_is_empty(sequeue_t *q)
{return (q->front == q->rear);
}int sequeue_is_full(sequeue_t *q)
{// 队尾 +1 == 队头 , 就是满队// 任何一个一个数对N求余 , 这个数的范围是  0 - N-1return ((q->rear + 1) % N == q->front);
}int sequeue_is_size(sequeue_t *q)
{// 队尾减去队头就是元素的个数if (q->rear >= q->front) //return (q->rear - q->front);elsereturn (N - q->front + q->rear);
}int sequeue_enqueue(sequeue_t *q, int value)
{if (sequeue_is_full(q)){printf("队列已满");return -1;}q->rear = (q->rear + 1) % N; // 防止数组越界q->data[q->rear] = value;return 0;
}
int sequeue_dequeue(sequeue_t *q, int *pvalue)
{if (sequeue_is_empty(q)){printf("队列已空");return -1;}q->front = (q->front + 1) % N; // 防止数组越界*pvalue = q->data[q->front];return 0;
}// sequeue stack
typedef struct
{int data[N]; // 数组的空间int index;   // 是数组下标的索引} seqstack_t;seqstack_t *create_empty_seqstack()
{seqstack_t *s = (seqstack_t *)malloc(sizeof(seqstack_t));memset(s->data, 0, sizeof(s->data)); // 把数组中的内容清为0s->index = -1;                       // 表示栈为空return s;
}int seqstack_is_empty(seqstack_t *s)
{return (s->index == -1);
}int seqstack_is_full(seqstack_t *s)
{return (s->index == N - 1);
}int seqstack_is_size(seqstack_t *s)
{return (s->index+1);
}// 入栈 , 压栈
int seqstack_push(seqstack_t *s, int value)
{if (seqstack_is_full(s)){printf("栈已满");return -1;}s->index++;s->data[s->index] = value;return 0;
}
int seqstack_pop(seqstack_t *s, int *pvalue)
{if (seqstack_is_empty(s)){printf("栈已空");return -1;}*pvalue = s->data[s->index];s->index--;return 0;
}// 检查队列是否是 是否是1,2,3...27 这个顺序
// 是这个顺序 返回真 
// 不是这个顺序 返回假
int check_sequeue(sequeue_t * q)
{for(int i=1;i<27;i++){// 正常顺序 1,2,3,4,...27 if(q->data[(q->front+i)%N] > q->data[(q->front+i+1)%N] ){return 0; // 这个顺序不对 }}return 1; // 所有顺序都对 , 返回真 }int main(int argc, char const *argv[])
{sequeue_t *Q = create_empty_sequeue(); // 创建一个空队列// 往队列中装入27个元素for (int i = 0; i < 27; i++){sequeue_enqueue(Q, i + 1);}seqstack_t *S1 = create_empty_seqstack();  // S1 分钟指示器 seqstack_t *S5 = create_empty_seqstack();  // S5 5分钟指示器 seqstack_t *S60 = create_empty_seqstack(); // S60 5小时指示器 int count =0 ; //  用来记录工作的分钟数 int value = 0 ,t12;while(1){count ++ ; // 计算累计时间的 sequeue_dequeue(Q,&value) ; // 从球队列中取出一个球seqstack_push(S1,value);    // 放入分钟指示器中/*************************************************************/// 分钟指示器的工作原理 if(seqstack_is_size(S1) < 5)  continue;seqstack_pop(S1,&value);  // 第五个球就会进入五分钟指示器seqstack_push(S5,value);  //在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾for(int i=0;i<4;i++) {seqstack_pop(S1,&value);  sequeue_enqueue(Q,value); }/*************************************************************/// 5分钟指示器的工作原理 if(seqstack_is_size(S5) < 12)  continue;seqstack_pop(S5,&value);  // 第12个球就会进入小时指示器seqstack_push(S60,value);  //在5分钟指示器的11个球就会按照他们被放入时的相反顺序加入球队列的队尾for(int i=0;i<11;i++) {seqstack_pop(S5,&value);  sequeue_enqueue(Q,value); }/*************************************************************/// 小时指示器的工作原理 if(seqstack_is_size(S60) < 12)  continue;seqstack_pop(S60,&t12);  // 第12个球拿出来 //小时指示器的11个球就会按照他们被放入时的相反顺序加入球队列的队尾for(int i=0;i<11;i++) {seqstack_pop(S60,&value);  sequeue_enqueue(Q,value); }sequeue_enqueue(Q,t12);  // 然后第12个球也回到队尾/*************************************************************/// 结束条件 if(check_sequeue(Q)) // 为真, 返回 , 为假继续循环{break; }else{continue;}}// 33120 是标准答案 printf("count = %d\n",count); return 0;
}

• 运行结果

count = 33120

2.5 队列与栈的转换

1. 实例16 顺序的双栈实现一个队列

• 使用双栈实现一个队列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QpQ8IKRT-1668935067808)(https://gitee.com/embmaker/cloudimage/raw/master/img/%E5%8F%8C%E6%A0%88%E5%AE%9E%E7%8E%B0%E4%B8%80%E9%98%9F%E5%88%97.jpg)]

• 使用顺序的栈实现一个顺序的队列

  • 第1步:入栈s1中, 入栈1,2,3,4
  • 第2步:把s1中的元素全部出栈到s2中 ,s2中的值:4,3,2,1
  • 第3步:从s2中出栈一个元素,这个元素就是1 , 把1出栈
  • 第4步:把s2所有的元素再次出栈到s1当中
  • 最终s1 内为: 2,3,4

• 源文件

04-ds/16-double_seqstack_one_sequeue.c

• 源代码

#include  
#include 
#include 
#include // sequeue stack #define  N   32 
typedef struct 
{int data[N]; // 数组的空间int index ; // 是数组下标的索引 }seqstack_t; seqstack_t * create_empty_seqstack()
{seqstack_t * s = (seqstack_t *)malloc(sizeof(seqstack_t));memset(s->data,0,sizeof(s->data)) ; // 把数组中的内容清为0 s->index = -1 ; // 表示栈为空 return s ; 
}int seqstack_is_empty(seqstack_t * s)
{return (s->index == -1 ); 
}int seqstack_is_full(seqstack_t *s)
{return (s->index == N-1) ; 
}// 入栈 , 压栈 
int seqstack_push(seqstack_t *s, int value)
{if(seqstack_is_full(s)){printf("栈已满"); return -1 ;}s->index ++  ; s->data[s->index] = value ; return  0 ; 
}
int seqstack_pop(seqstack_t * s, int *pvalue)
{if(seqstack_is_empty(s)){printf("栈已空"); return -1 ; }*pvalue = s->data[s->index] ; s->index -- ; return 0 ; 
}int sequeue_enqueue(seqstack_t *s1,seqstack_t *s2,int value)
{seqstack_push(s1,value); return 0; 
}
int sequeue_dequeue(seqstack_t *s1,seqstack_t *s2,int *pvalue)
{int value ; // 1. 把s1中的所有元素倒入到s2中while(!seqstack_is_empty(s1)){seqstack_pop(s1,&value); seqstack_push(s2,value); }// 2. 出一个元素  seqstack_pop(s2,pvalue);// 3. 把s2中的所有元素倒入到s1中while(!seqstack_is_empty(s2)){seqstack_pop(s2,&value); seqstack_push(s1,value); }return 0 ; 
}int main(int argc, char const *argv[])
{seqstack_t *S1 = create_empty_seqstack();seqstack_t *S2 = create_empty_seqstack();//  这个队列, 最多可以存放 31 个元素printf("入队顺序为:");for (int i = 0; i < 32; i++){if (sequeue_enqueue(S1,S2, i + 1) == 0){printf("%d ", i + 1);}}printf("\n");printf("出队顺序为:");for (int i = 0,value; i < 32; i++){if (sequeue_dequeue(S1,S2, &value) == 0){printf("%d ", value);}}printf("\n");return 0;
}

• 运行结果

入队顺序为:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 
出队顺序为:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

2. 实例17 链式的双栈实现一个队列

• 流程如实例16
• 源文件

04-ds/17-double_linkstack_one_linkqueue.c

• 源代码

#include  
#include 
#include 
#include // link stacktypedef struct node
{int data;struct node *next;
} linklist_t;linklist_t *create_empty_linkstack()
{linklist_t *s = (linklist_t *)malloc(sizeof(linklist_t));s->data = 0;s->next = NULL;return s;
}// 链表没有满  , 有空的概念
int linkstack_is_empty(linklist_t *s)
{return (s->next == NULL);
}// 头部插入法
int linkstack_push(linklist_t *s, int value)
{linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t));p->data = value;p->next = s->next;s->next = p;return 0;
}// 头部删除法
int linkstack_pop(linklist_t *s, int *pvalue)
{linklist_t *p = s->next; // p 指向s的下一个节点if(linkstack_is_empty(s)){printf("栈已空"); return -1 ; }// s->next 不为空 s->next = p->next; // 接链表 *pvalue = p->data ; // 读取数据free(p); return 0;
}int linkqueue_enqueue(linklist_t *s1,linklist_t *s2,int value)
{linkstack_push(s1,value); return 0; 
}
int linkqueue_dequeue(linklist_t *s1,linklist_t *s2,int *pvalue)
{int value ; // 1. 把s1中的所有元素倒入到s2中while(!linkstack_is_empty(s1)){linkstack_pop(s1,&value); linkstack_push(s2,value); }// 2. 出一个元素  linkstack_pop(s2,pvalue);// 3. 把s2中的所有元素倒入到s1中while(!linkstack_is_empty(s2)){linkstack_pop(s2,&value); linkstack_push(s1,value); }return 0 ; 
}int main(int argc, char const *argv[])
{linklist_t *S1 = create_empty_linkstack();linklist_t *S2 = create_empty_linkstack();//  这个队列, 最多可以存放 31 个元素printf("入队顺序为:");for (int i = 0; i < 32; i++){if (linkqueue_enqueue(S1,S2, i + 1) == 0){printf("%d ", i + 1);}}printf("\n");printf("出队顺序为:");for (int i = 0,value; i < 32; i++){if (linkqueue_dequeue(S1,S2, &value) == 0){printf("%d ", value);}}printf("\n");return 0;
}

• 运行结果

入队顺序为:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 
出队顺序为:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 

3. 实例18 顺序的双队列实现一个栈

• 初始状态 QueueA 和QueueB都为空

• 第1步: 把QueueA 入队1,2,3,4

• 第2补: 把QueueA 出队1,2,3 到QueueB, 此时QueueA中还剩下一个4

• 第3步: 从QueueA中出队最后一个元素4 , 4就是出栈的元素

• 第4步: 把QueueB中的所有元素再入队到QueueA中, 此时一次出栈完成

• 最后的效果是: QueueA中是 1,2,3 QueueB中空

• 计算队列元素个数

• 源文件

04-ds/18-double_sequeue_one_seqstack.c

• 源代码

#include 
#include 
#include 
// sequence queue#define N 32
typedef struct
{int data[N];int front; // 队列的头  , 数组的下标int rear;  // 队列的尾  , 数组的下标
} sequeue_t;// 空队列的概念是 : 队头等于队尾
// 为了区分空队 和满队 , 队列元素个数要比数组元素少一个
// 满队+1 等于空队
// 1 2 3 4 5
// f       f
// rsequeue_t *create_empty_sequeue()
{sequeue_t *q = (sequeue_t *)malloc(sizeof(sequeue_t));memset(q->data, 0, sizeof(q->data));q->front = q->rear = N - 1; //指向数组最后一个元素return q;
}int sequeue_is_empty(sequeue_t *q)
{return (q->front == q->rear);
}int sequeue_is_full(sequeue_t *q)
{// 队尾 +1 == 队头 , 就是满队// 任何一个一个数对N求余 , 这个数的范围是  0 - N-1return ((q->rear + 1) % N == q->front);
}int sequeue_is_size(sequeue_t *q)
{// 队尾减去队头就是元素的个数if (q->rear >= q->front) //return (q->rear - q->front);elsereturn (N - q->front + q->rear);
}int sequeue_enqueue(sequeue_t *q, int value)
{if (sequeue_is_full(q)){printf("队列已满");return -1;}q->rear = (q->rear + 1) % N; // 防止数组越界q->data[q->rear] = value;return 0;
}
int sequeue_dequeue(sequeue_t *q, int *pvalue)
{if (sequeue_is_empty(q)){printf("队列已空");return -1;}q->front = (q->front + 1) % N; // 防止数组越界*pvalue = q->data[q->front];return 0;
}int seqstack_push(sequeue_t *q1, sequeue_t *q2, int value)
{sequeue_enqueue(q1, value); // 队列不满return 0;
}
int seqstack_pop(sequeue_t *q1, sequeue_t *q2, int *pvalue)
{int value;// q1 出队列只剩下一个元素// printf("sequeue_is_size(q1)=%d\n",sequeue_is_size(q1));while (sequeue_is_size(q1) > 1){sequeue_dequeue(q1, &value) ; sequeue_enqueue(q2, value);}// 把q1中的元素出队sequeue_dequeue(q1, pvalue);// 把q2中的所有元素出队到q1while (sequeue_is_size(q2) > 0){sequeue_dequeue(q2, &value);sequeue_enqueue(q1, value);}return 0;
}int main(int argc, char const *argv[])
{sequeue_t *Q1 = create_empty_sequeue();sequeue_t *Q2 = create_empty_sequeue();printf("入栈顺序:");for (int i = 0; i < 32; i++){if (seqstack_push(Q1, Q2, i + 1) == 0) // 表示成功{printf("%d ", i + 1);}}printf("\n");printf("出栈顺序:");for (int i = 0, value; i < 32; i++){if (seqstack_pop(Q1, Q2, &value) == 0){printf("%d ", value);}}printf("\n");return 0;
}

• 运行结果

入栈顺序:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 队列已满32 
出栈顺序:31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 队列已空1 

4. 实例19 链式的双队列实现一个栈

• 源文件

04-ds/19-double_linkqueue_one_linkstack.c

• 源代码

#include 
#include 
#include 
// link queuetypedef struct node
{int data;struct node *next;
} linklist_t;typedef struct
{linklist_t *front; // 队头linklist_t *rear;  // 队尾
} linkqueue_t;// 空队列的概念是 : 队头等于队尾
// 为了区分空队 和满队 , 队列元素个数要比数组元素少一个
// 满队+1 等于空队
// 1 2 3 4 5
// f       f
// rlinkqueue_t *create_empty_linkqueue()
{linklist_t *h = (linklist_t *)malloc(sizeof(linklist_t));linkqueue_t *q = (linkqueue_t *)malloc(sizeof(linkqueue_t));q->front = q->rear = h;q->front->data = 0;return q;
}int linkqueue_is_empty(linkqueue_t *q)
{return (q->front == q->rear);
}// 链式队列没有满的概念
// int linkqueue_is_full(linkqueue_t *q)
// {// }int linkqueue_is_size(linkqueue_t *q)
{int size = 0 ; linklist_t *p = q->front->next;  // 指向队列的第1个元素while(p != NULL){size ++; p = p->next ; }return size  ; 
}// 入队 队尾加
int linkqueue_enqueue(linkqueue_t *q, int value)
{linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t));p->data = value;p->next = q->rear->next; // 尾部插入第1步q->rear->next = p;       // 尾部插入第2步q->rear = p;             // 尾部插入第3步return 0;
}// 头部出队列 , 头部删除法
int linkqueue_dequeue(linkqueue_t *q, int *pvalue)
{linklist_t *p;if (linkqueue_is_empty(q)){printf("队列为空");return -1;}p = q->front->next;           // 头节点的下一个节点  , p是要删除的节点q->front->next = p->next;     // 接上链表if (q->front->next == NULL) // 此时队列为空q->rear = q->front; // *pvalue = p->data;free(p);return 0;
}int linkstack_push(linkqueue_t *q1, linkqueue_t *q2, int value)
{linkqueue_enqueue(q1, value); // 队列不满return 0;
}
int linkstack_pop(linkqueue_t *q1, linkqueue_t *q2, int *pvalue)
{int value;// q1 出队列只剩下一个元素// printf("linkqueue_is_size(q1)=%d\n",linkqueue_is_size(q1));while (linkqueue_is_size(q1) > 1){linkqueue_dequeue(q1, &value) ; linkqueue_enqueue(q2, value);}// 把q1中的元素出队linkqueue_dequeue(q1, pvalue);// 把q2中的所有元素出队到q1while (linkqueue_is_size(q2) > 0){linkqueue_dequeue(q2, &value);linkqueue_enqueue(q1, value);}return 0;
}int main(int argc, char const *argv[])
{linkqueue_t *Q1 = create_empty_linkqueue();linkqueue_t *Q2 = create_empty_linkqueue();printf("入栈顺序:");for (int i = 0; i < 32; i++){if (linkstack_push(Q1, Q2, i + 1) == 0) // 表示成功{printf("%d ", i + 1);}}printf("\n");printf("出栈顺序:");for (int i = 0, value; i < 32; i++){if (linkstack_pop(Q1, Q2, &value) == 0){printf("%d ", value);}}printf("\n");return 0;
}

• 运行结果

入栈顺序:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 
出栈顺序:32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1