当前位置:   article > 正文

【数据结构笔记】数据结构基础—队列_代码实现链式队列,输入数字入队,输入字符出队。

代码实现链式队列,输入数字入队,输入字符出队。

1.顺序队列的原理

        队列是限制在两端进行插入操作和删除操作的线性表,允许进行存入操作的一端称为“队尾”,允许进行删除操作的一端称为“队头”,当线性表中没有元素时,称为“空队”,特点 :先进先出(FIFO)。

  1. typedef int datatype;
  2. #define N 128
  3. // 当front和rear的值相同时,表示队列为空,但对于循环队列来讲,满队时,front和rear的值也相同
  4. // 所以对于队列来说,当队列只剩下一个空位置时,即视为满队,即,当(rear+1)%N 等于front时,视为满队
  5. typedef struct {
  6. datatype data[N];
  7. int front; // 队头元素的下标
  8. int rear; // 队尾元素的下一个位置的下标(待存入值的位置)
  9. }sequeue;

规定:

        1.front指向队头元素的位置; rear指向队尾元素的下一个位置。
        2.在队列操作过程中,为了提高效率,以调整指针代替队列元素的移动,并将数组作为循环队列的操作空间。
        3.为区别空队和满队,满队元素个数比数组实际能容纳的个数少1。

2.顺序队列的实现

创建队列与释放队列

  1. sequeue * queue_create() {
  2. sequeue *sq;
  3. if ((sq = (sequeue *)malloc(sizeof(sequeue))) == NULL) {
  4. printf("malloc failed\n");
  5. return NULL;
  6. }
  7. memset(sq->data, 0, sizeof(sq->data));
  8. sq->front = sq->rear = 0; // rear指向待插入位置,front指向当前首位置
  9. return sq;
  10. }
  1. sequeue * queue_free(sequeue *sq) {
  2. if (sq == NULL) {
  3. printf("sq is NULL\n");
  4. return NULL;
  5. }
  6. free(sq); // 如果sq中的data用的是指针,那么data需要在创建时申请内存,在此时释放内存
  7. sq = NULL;
  8. return NULL;
  9. }

入队与出队

  1. int enqueue(sequeue *sq, datatype x) {
  2. if (sq == NULL) {
  3. printf("sq is NULL\n");
  4. return -1;
  5. }
  6. // 当队列只剩下一个空位置时,即视为满队,此时rear指向最后一个空位置,
  7. // 若队尾在内存的末端,则此时(rear+1)%N 等于front,若队尾在内存的中间(循环队列),则rear+1等于front
  8. // 即,当(rear+1)%N 等于front时,视为满队
  9. if ((sq->rear + 1) % N == sq->front) {
  10. printf("sequeue is full\n");
  11. return -1;
  12. }
  13. sq->data[sq->rear] = x;
  14. // 这里对N取余是为了应对这种情况:循环队列,rear指向内存末端
  15. // 同时front指向内存中间,内存的前端还有空余,此时rear+1就超出内存范围了
  16. // 对N取余后,就会利用上内存前端的空间,构成循环队列
  17. sq->rear = (sq->rear + 1) % N;
  18. return 0;
  19. }
  1. datatype dequeue(sequeue *sq) {
  2. datatype ret; // 用于返回出队的值
  3. ret = sq->data[sq->front];
  4. // 队首到队尾索引从低到高,所以这里是+1不是-1
  5. sq->front = (sq->front + 1) % N; // 同时,对N取余也是为了适应循环队列
  6. return ret;
  7. }

判断空队与满队

  1. int queue_empty(sequeue *sq) {
  2. if (sq == NULL) {
  3. printf("sq is NULL\n");
  4. return -1;
  5. }
  6. return (sq->front == sq->rear ? 1 : 0);
  7. }
  1. int queue_full(sequeue *sq) {
  2. if (sq == NULL) {
  3. printf("sq is NULL\n");
  4. return -1;
  5. }
  6. if ((sq->rear + 1) % N == sq->front) {
  7. return 1;
  8. }
  9. else {
  10. return 0;
  11. }
  12. }

清空队列

  1. int queue_clear(sequeue *sq) {
  2. if (sq == NULL) {
  3. printf("sq is NULL\n");
  4. return -1;
  5. }
  6. sq->front = sq->rear = 0;
  7. return 0;
  8. }

3.链式队列的原理与实现

        插入操作在队尾进行,删除操作在队头进行,由队头指针和队尾指针控制队列的操作。

  1. typedef int data_t;
  2. typedef struct node {
  3. data_t data;
  4. struct node_t *next;
  5. } listnode, *linklist;
  6. typedef struct {
  7. linklist_t front, rear; // 这里front和rear还是对应位置的索引,不过是以指针的形式,指向节点类型的变量
  8. } linkqueue;

创建和释放队列

  1. linkqueue * queue_create() {
  2. linkqueue *lq;
  3. if ((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL) {
  4. printf("malloc linkqueue failed\n");
  5. return NULL;
  6. }
  7. // 创建时,front和rear都指向同一个节点,即头节点,而不是队头节点
  8. lq->front = lq->rear = (linklist)malloc(sizeof(listnode));
  9. if (lq->front == NULL) {
  10. printf("malloc node failed\n");
  11. return NULL;
  12. }
  13. lq->front->data = 0;
  14. lq->front->next = NULL; //此时rear也指向头节点,而不是头节点中的next,这两句话用lq->rear代替lq->front依然正确
  15. return lq;
  16. }
  1. linkqueue * queue_free(linkqueue *lq) {
  2. linklist p;
  3. if (lq == NULL) {
  4. printf("lq is NULL\n");
  5. return NULL;
  6. }
  7. while (lq->front) { // 和清空队列的不同之处在于,头指针也释放
  8. p = lq->front;
  9. lq->front = p->next;
  10. printf("free:%d\n", p->data);
  11. free(p);
  12. }
  13. free(lq); // 和清空队列的不同之处在于,用于描述队列信息的结构体也被释放
  14. lq = NULL;
  15. return NULL;
  16. }

入队和出队

  1. int enqueue(linkqueue *lq, datatype x) {
  2. linklist p;
  3. if (lq == NULL) {
  4. printf("lq is NULL\n");
  5. return -1;
  6. }
  7. // 先新建一个节点:1.申请内存 2.初始化data和*next
  8. if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {
  9. printf("malloc node failed\n");
  10. return -1;
  11. }
  12. p->data = x;
  13. p->next = NULL;
  14. lq->rear->next = p; // 连上
  15. lq->rear = p; // 移动指针
  16. return 0;
  17. }
  1. datatype dequeue(linkqueue *lq) {
  2. linklist p;
  3. if (lq == NULL) {
  4. printf("lq is NULL\n");
  5. return -1;
  6. }
  7. // 这里涉及到一个思想,因为链式队列涉及到头节点,和队头可能冲突
  8. // 出队其实出的应该是队头,不应该出头节点,这里出队时,出的是头节点
  9. // 思想就是:出了头节点后,认为队头就是新的头节点,队列中的第二个元素成为新的队头
  10. // 如此一来,就相当于把队头出掉了,真实情况是队头被当作了新的头节点,它的data值也就每人在乎了
  11. p = lq->front;
  12. lq->front = p->next; // 队头成为新的头节点
  13. free(p);
  14. p = NULL;
  15. return (lq->front->data);
  16. }

队列是否为空

  1. int queue_empty(linkqueue *lq) {
  2. if (lq == NULL) {
  3. printf("lq is NULL\n");
  4. return -1;
  5. }
  6. return (lq->front == lq->rear ? 1 : 0); // front和rear指向的节点相同,视为空
  7. }

清空队列

  1. // 由于这是链式队列,所以清空队列应该是把头节点外的所有节点都释放
  2. int queue_clear(linkqueue *lq) {
  3. linklist p;
  4. if (lq == NULL) {
  5. printf("lq is NULL\n");
  6. return -1;
  7. }
  8. while (lq->front->next) { // 这里保留了头节点,从队头开始释放
  9. p = lq->front;
  10. lq->front = p->next;
  11. printf("clear free:%d\n", p->data);
  12. free(p);
  13. p = NULL;
  14. }
  15. return 0;
  16. }

4.栈和队列的应用

球钟问题

工作原理

问题

 为什么队列中球数为27:小时容器11个 + 5分钟容器11个 + 1分钟容器4个 = 26个,第27个球的作用很特殊,作用是把这26个清空,实现11:59到00:00的转变。

 容器:是栈,有最大容量,故选择顺序栈。

 由于循环队列涉及到取余操作,链式队列用起来相对简单,故选择链式队列。

  1. #include <stdio.h>
  2. #include "linkqueue.h"
  3. #include "sqstack.h"
  4. int check(linkqueue * lq);
  5. int main(int argc, const char *argv[])
  6. {
  7. linkqueue *lq; // 描述链式队列的结构体,里面有front,rear
  8. sqstack *s_hour, *s_five, *s_min; // 定义了3个结构体指针,指向顺序栈对象
  9. int value;
  10. int i, min = 0;
  11. if ((lq = queue_create()) == NULL) { // 创建链式队列
  12. return -1;
  13. }
  14. for (i = 1; i <= 27; i++) { // 将27个球入队
  15. enqueue(lq, i);
  16. }
  17. if ((s_hour = stack_create(11)) == NULL) { // 创建特定容量的顺序栈
  18. return -1;
  19. }
  20. if ((s_five = stack_create(11)) == NULL) {
  21. return -1;
  22. }
  23. if ((s_min = stack_create(4)) == NULL) {
  24. return -1;
  25. }
  26. while (1) {
  27. min++; // 这里记录次数,因为题目问的就是min有多少次
  28. if (!queue_empty(lq)) { // 如果队列还有数
  29. value = dequeue(lq); // 出队一个数给value,利用value将这个数送入栈
  30. if (!stack_full(s_min)) {
  31. stack_push(s_min, value); // 后面代码不再执行
  32. } else { // 此时value中的球还没入栈,else执行,说明min栈满了,这个球会在后面给到5min栈
  33. while (!stack_empty(s_min)) {
  34. enqueue(lq, stack_pop(s_min)); //*将min栈出栈 同时入队到队列,直到栈空为止
  35. }
  36. if (!stack_full(s_five)) { // 这里注意括号,这个if是在else里面的,即此时min栈满了,但又被清空了
  37. stack_push(s_five, value); // min栈满了,清空min栈后,5min栈入栈一元素,后面代码不再执行
  38. } else { // else执行,说明min栈、5min栈都满了
  39. while (!stack_empty(s_five)) { // while循环,开始清理5min栈
  40. enqueue(lq, stack_pop(s_five)); // 出栈后入队
  41. }
  42. if (!stack_full(s_hour)) {
  43. stack_push(s_hour, value); // 之前的5min栈满了,小时栈自然要push一个值,后面不再执行
  44. } else { // 此时的value是第27个球,else执行,说明min栈、5min栈、小时栈都满了
  45. while (!stack_empty(s_hour)) {
  46. enqueue(lq, stack_pop(s_hour)); // 清空小时栈后入队
  47. }
  48. enqueue(lq, value); // 这个第27个球,不会入栈,在外边溜达一圈后直接归队
  49. //上面语句执行完后,27个球全部归队,时间置为00:00
  50. if (check(lq) == 1) {
  51. break; // 这个break跳出的是while(1)循环,其他while循环均不在break外层
  52. }
  53. }
  54. }
  55. }
  56. }
  57. } // while(1)的回括号
  58. printf("total:%d\n", min);
  59. printf("dequeue:");
  60. while (!queue_empty(lq))
  61. printf("%d ", dequeue(lq));
  62. puts("");
  63. return 0;
  64. } // main的回括号
  65. // 检查传入的链式队列,是否为升序,若是返回1,不是返回0
  66. int check(linkqueue * lq) {
  67. linklist p;
  68. if (lq == NULL) {
  69. printf("lq is NULL\n");
  70. return -1;
  71. }
  72. p = lq->front->next; // p指向队头
  73. while (p && p->next) { // 队头和队头后面一个元素均非空时
  74. if (p->data < p->next->data) {
  75. p = p->next;
  76. } else {
  77. return 0;
  78. }
  79. }
  80. return 1;
  81. }

相关题目

1、链式队列有假溢出么?链式队列需要判空判满么?为什么?
2、代码实现链式队列,输入数字入队,输入字符出队。

1、链式队列没有假溢出,链式队列可以判空,不需要判满,链式队列每次入队会新建节点,每次出队会释放节点,没有明确的长度限制,故不涉及溢出和满队列,当链式队列的front和rear指向同一个节点时,视链式队列为空队列。

2、可以尝试下实现输入多位数。用%d,判断scanf的返回值就知道输入的是字符还是数字了。

  1. int main()
  2. {
  3. int value;
  4. //char ch;
  5. linkqueue lp = listqueue_create();
  6. printf("Please enter a character or a number from 0 to 9:\nEnter '?' to stop.\n");
  7. while (1) {
  8. char ch;
  9. scanf("%c", &ch);
  10. if (isalpha(ch))
  11. printf("%d has dequeued.\n", dequeue(lp));
  12. if (isdigit(ch)) {
  13. ch = (int)(ch - '0');
  14. printf("%d has enqueued.\n", ch);
  15. enqueue(lp, ch);
  16. }
  17. if (ch == '?')
  18. break;
  19. }
  20. while (lp->front->next!= NULL) {
  21. printf("%d ", dequeue(lp));
  22. }
  23. puts("");
  24. return 0;
  25. }
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/706910
推荐阅读
相关标签
  

闽ICP备14008679号