赞
踩
队列是限制在两端进行插入操作和删除操作的线性表,允许进行存入操作的一端称为“队尾”,允许进行删除操作的一端称为“队头”,当线性表中没有元素时,称为“空队”,特点 :先进先出(FIFO)。
- typedef int datatype;
- #define N 128
-
- // 当front和rear的值相同时,表示队列为空,但对于循环队列来讲,满队时,front和rear的值也相同
- // 所以对于队列来说,当队列只剩下一个空位置时,即视为满队,即,当(rear+1)%N 等于front时,视为满队
- typedef struct {
- datatype data[N];
- int front; // 队头元素的下标
- int rear; // 队尾元素的下一个位置的下标(待存入值的位置)
- }sequeue;
规定:
1.front指向队头元素的位置; rear指向队尾元素的下一个位置。
2.在队列操作过程中,为了提高效率,以调整指针代替队列元素的移动,并将数组作为循环队列的操作空间。
3.为区别空队和满队,满队元素个数比数组实际能容纳的个数少1。
- sequeue * queue_create() {
- sequeue *sq;
-
- if ((sq = (sequeue *)malloc(sizeof(sequeue))) == NULL) {
- printf("malloc failed\n");
- return NULL;
- }
-
- memset(sq->data, 0, sizeof(sq->data));
- sq->front = sq->rear = 0; // rear指向待插入位置,front指向当前首位置
- return sq;
- }
- sequeue * queue_free(sequeue *sq) {
- if (sq == NULL) {
- printf("sq is NULL\n");
- return NULL;
- }
-
- free(sq); // 如果sq中的data用的是指针,那么data需要在创建时申请内存,在此时释放内存
- sq = NULL;
-
- return NULL;
- }
- int enqueue(sequeue *sq, datatype x) {
- if (sq == NULL) {
- printf("sq is NULL\n");
- return -1;
- }
-
- // 当队列只剩下一个空位置时,即视为满队,此时rear指向最后一个空位置,
- // 若队尾在内存的末端,则此时(rear+1)%N 等于front,若队尾在内存的中间(循环队列),则rear+1等于front
- // 即,当(rear+1)%N 等于front时,视为满队
- if ((sq->rear + 1) % N == sq->front) {
- printf("sequeue is full\n");
- return -1;
- }
-
- sq->data[sq->rear] = x;
- // 这里对N取余是为了应对这种情况:循环队列,rear指向内存末端
- // 同时front指向内存中间,内存的前端还有空余,此时rear+1就超出内存范围了
- // 对N取余后,就会利用上内存前端的空间,构成循环队列
- sq->rear = (sq->rear + 1) % N;
-
- return 0;
- }

- datatype dequeue(sequeue *sq) {
- datatype ret; // 用于返回出队的值
-
- ret = sq->data[sq->front];
- // 队首到队尾索引从低到高,所以这里是+1不是-1
- sq->front = (sq->front + 1) % N; // 同时,对N取余也是为了适应循环队列
-
- return ret;
- }
- int queue_empty(sequeue *sq) {
- if (sq == NULL) {
- printf("sq is NULL\n");
- return -1;
- }
-
- return (sq->front == sq->rear ? 1 : 0);
- }
- int queue_full(sequeue *sq) {
- if (sq == NULL) {
- printf("sq is NULL\n");
- return -1;
- }
-
- if ((sq->rear + 1) % N == sq->front) {
- return 1;
- }
- else {
- return 0;
- }
- }
- int queue_clear(sequeue *sq) {
- if (sq == NULL) {
- printf("sq is NULL\n");
- return -1;
- }
-
- sq->front = sq->rear = 0;
-
- return 0;
- }
插入操作在队尾进行,删除操作在队头进行,由队头指针和队尾指针控制队列的操作。
- typedef int data_t;
-
- typedef struct node {
- data_t data;
- struct node_t *next;
- } listnode, *linklist;
-
- typedef struct {
- linklist_t front, rear; // 这里front和rear还是对应位置的索引,不过是以指针的形式,指向节点类型的变量
- } linkqueue;
- linkqueue * queue_create() {
- linkqueue *lq;
-
- if ((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL) {
- printf("malloc linkqueue failed\n");
- return NULL;
- }
- // 创建时,front和rear都指向同一个节点,即头节点,而不是队头节点
- lq->front = lq->rear = (linklist)malloc(sizeof(listnode));
- if (lq->front == NULL) {
- printf("malloc node failed\n");
- return NULL;
- }
- lq->front->data = 0;
- lq->front->next = NULL; //此时rear也指向头节点,而不是头节点中的next,这两句话用lq->rear代替lq->front依然正确
-
- return lq;
- }

- linkqueue * queue_free(linkqueue *lq) {
- linklist p;
-
- if (lq == NULL) {
- printf("lq is NULL\n");
- return NULL;
- }
-
- while (lq->front) { // 和清空队列的不同之处在于,头指针也释放
- p = lq->front;
- lq->front = p->next;
- printf("free:%d\n", p->data);
- free(p);
- }
-
- free(lq); // 和清空队列的不同之处在于,用于描述队列信息的结构体也被释放
- lq = NULL;
-
- return NULL;
- }

- int enqueue(linkqueue *lq, datatype x) {
- linklist p;
-
- if (lq == NULL) {
- printf("lq is NULL\n");
- return -1;
- }
- // 先新建一个节点:1.申请内存 2.初始化data和*next
- if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {
- printf("malloc node failed\n");
- return -1;
- }
- p->data = x;
- p->next = NULL;
-
- lq->rear->next = p; // 连上
- lq->rear = p; // 移动指针
-
- return 0;
- }

- datatype dequeue(linkqueue *lq) {
- linklist p;
-
- if (lq == NULL) {
- printf("lq is NULL\n");
- return -1;
- }
- // 这里涉及到一个思想,因为链式队列涉及到头节点,和队头可能冲突
- // 出队其实出的应该是队头,不应该出头节点,这里出队时,出的是头节点
- // 思想就是:出了头节点后,认为队头就是新的头节点,队列中的第二个元素成为新的队头
- // 如此一来,就相当于把队头出掉了,真实情况是队头被当作了新的头节点,它的data值也就每人在乎了
- p = lq->front;
- lq->front = p->next; // 队头成为新的头节点
- free(p);
- p = NULL;
-
- return (lq->front->data);
- }

- int queue_empty(linkqueue *lq) {
- if (lq == NULL) {
- printf("lq is NULL\n");
- return -1;
- }
-
- return (lq->front == lq->rear ? 1 : 0); // front和rear指向的节点相同,视为空
- }
- // 由于这是链式队列,所以清空队列应该是把头节点外的所有节点都释放
- int queue_clear(linkqueue *lq) {
- linklist p;
-
- if (lq == NULL) {
- printf("lq is NULL\n");
- return -1;
- }
-
- while (lq->front->next) { // 这里保留了头节点,从队头开始释放
- p = lq->front;
- lq->front = p->next;
- printf("clear free:%d\n", p->data);
- free(p);
- p = NULL;
- }
- return 0;
- }

为什么队列中球数为27:小时容器11个 + 5分钟容器11个 + 1分钟容器4个 = 26个,第27个球的作用很特殊,作用是把这26个清空,实现11:59到00:00的转变。
容器:是栈,有最大容量,故选择顺序栈。
由于循环队列涉及到取余操作,链式队列用起来相对简单,故选择链式队列。
- #include <stdio.h>
- #include "linkqueue.h"
- #include "sqstack.h"
-
- int check(linkqueue * lq);
-
- int main(int argc, const char *argv[])
- {
- linkqueue *lq; // 描述链式队列的结构体,里面有front,rear
- sqstack *s_hour, *s_five, *s_min; // 定义了3个结构体指针,指向顺序栈对象
- int value;
- int i, min = 0;
-
- if ((lq = queue_create()) == NULL) { // 创建链式队列
- return -1;
- }
-
- for (i = 1; i <= 27; i++) { // 将27个球入队
- enqueue(lq, i);
- }
-
- if ((s_hour = stack_create(11)) == NULL) { // 创建特定容量的顺序栈
- return -1;
- }
-
- if ((s_five = stack_create(11)) == NULL) {
- return -1;
- }
-
- if ((s_min = stack_create(4)) == NULL) {
- return -1;
- }
-
- while (1) {
- min++; // 这里记录次数,因为题目问的就是min有多少次
- if (!queue_empty(lq)) { // 如果队列还有数
- value = dequeue(lq); // 出队一个数给value,利用value将这个数送入栈
- if (!stack_full(s_min)) {
- stack_push(s_min, value); // 后面代码不再执行
- } else { // 此时value中的球还没入栈,else执行,说明min栈满了,这个球会在后面给到5min栈
- while (!stack_empty(s_min)) {
- enqueue(lq, stack_pop(s_min)); //*将min栈出栈 同时入队到队列,直到栈空为止
- }
- if (!stack_full(s_five)) { // 这里注意括号,这个if是在else里面的,即此时min栈满了,但又被清空了
- stack_push(s_five, value); // min栈满了,清空min栈后,5min栈入栈一元素,后面代码不再执行
- } else { // else执行,说明min栈、5min栈都满了
- while (!stack_empty(s_five)) { // while循环,开始清理5min栈
- enqueue(lq, stack_pop(s_five)); // 出栈后入队
- }
- if (!stack_full(s_hour)) {
- stack_push(s_hour, value); // 之前的5min栈满了,小时栈自然要push一个值,后面不再执行
- } else { // 此时的value是第27个球,else执行,说明min栈、5min栈、小时栈都满了
- while (!stack_empty(s_hour)) {
- enqueue(lq, stack_pop(s_hour)); // 清空小时栈后入队
- }
- enqueue(lq, value); // 这个第27个球,不会入栈,在外边溜达一圈后直接归队
- //上面语句执行完后,27个球全部归队,时间置为00:00
- if (check(lq) == 1) {
- break; // 这个break跳出的是while(1)循环,其他while循环均不在break外层
- }
- }
- }
-
- }
- }
- } // while(1)的回括号
- printf("total:%d\n", min);
-
- printf("dequeue:");
- while (!queue_empty(lq))
- printf("%d ", dequeue(lq));
- puts("");
-
- return 0;
- } // main的回括号
-
- // 检查传入的链式队列,是否为升序,若是返回1,不是返回0
- int check(linkqueue * lq) {
- linklist p;
-
- if (lq == NULL) {
- printf("lq is NULL\n");
- return -1;
- }
-
- p = lq->front->next; // p指向队头
-
- while (p && p->next) { // 队头和队头后面一个元素均非空时
- if (p->data < p->next->data) {
- p = p->next;
- } else {
- return 0;
- }
- }
- return 1;
- }

1、链式队列有假溢出么?链式队列需要判空判满么?为什么?
2、代码实现链式队列,输入数字入队,输入字符出队。
1、链式队列没有假溢出,链式队列可以判空,不需要判满,链式队列每次入队会新建节点,每次出队会释放节点,没有明确的长度限制,故不涉及溢出和满队列,当链式队列的front和rear指向同一个节点时,视链式队列为空队列。
2、可以尝试下实现输入多位数。用%d,判断scanf的返回值就知道输入的是字符还是数字了。
- int main()
- {
- int value;
- //char ch;
- linkqueue lp = listqueue_create();
- printf("Please enter a character or a number from 0 to 9:\nEnter '?' to stop.\n");
- while (1) {
- char ch;
- scanf("%c", &ch);
-
- if (isalpha(ch))
- printf("%d has dequeued.\n", dequeue(lp));
-
- if (isdigit(ch)) {
- ch = (int)(ch - '0');
- printf("%d has enqueued.\n", ch);
- enqueue(lp, ch);
- }
- if (ch == '?')
- break;
- }
- while (lp->front->next!= NULL) {
- printf("%d ", dequeue(lp));
- }
- puts("");
- return 0;
- }

赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。