数据结构学习笔记——队列

发布于：2025-05-28 ⋅ 阅读:(77) ⋅ 点赞:(0)

文章目录

1、队列

队列是限制在两端进行插入操作和删除操作的线性表

允许进行存入操作的一端称为“队尾”

允许进行删除操作的一端称为“队头”

当线性表中没有元素时，称为“空队”

特点 ：先进先出（FIFO）
在这里插入图片描述

双端队列：

在这里插入图片描述

队列的应用：

图片描述

队列顺序如上图为旅游路线规划，A为所在城市，先游玩B、E两个城市，然后再游玩C、F；D、G；H、K。（按顺序）

顺序循环队列的逻辑：
图片描述

  • 规定：front指向队头元素的位置;
  • rear指向队尾元素的下一个位置。
  • 在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间。
  • 为区别空队和满队，满队元素个数比数组元素个数少一个。

2、顺序队列的实现

顺序循环队列：

创建队列 ：CreateQueue ()
清空队列 ：ClearQueue (Q)
判断队列空 ：EmptyQueue(Q)
判断队列满 ：FullQueue(Q)
入队 ：EnQueue (Q, x)
出队 ：DeQueue(Q)

typedef int data_t ; /*定义队列中数据元素的数据类型*/
#define N 64	   	 /*定义队列的容量*/
typedef struct {
data_t data[N] ;  	 /*用数组作为队列的储存空间*/
int front, rear ;    /*指示队头位置和队尾位置的指针*/
}sequeue_t ; 	     /*顺序队列类型定义*/

程序举例：

  • sequeues.h

    typedef int datatype;
#define N 128

typedef struct {
	datatype data[N];
	int front;
	int rear;
}sequeue;

sequeue * queue_create();
int enqueue(sequeue *sq, datatype x);//入队
datatype dequeue(sequeue *sq);//出队
int queue_empty(sequeue *sq);//空队
int queue_full(sequeue *sq); //满队
int queue_clear(sequeue *sq);//清空队列
sequeue * queue_free(sequeue *sq);//

  • sequeues.c

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sequeue.h"

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;
	return sq;
}

int enqueue(sequeue *sq, datatype x) {
	if (sq == NULL) {
		printf("sq is NULL\n");
		return -1;
	}

	if ((sq->rear + 1) % N == sq->front) {
		printf("sequeue is full\n");
		return -1;
	}

	sq->data[sq->rear] = x;
	sq->rear = (sq->rear + 1) % N;

	return  0;
}

datatype dequeue(sequeue *sq) {
	datatype ret;

	ret = sq->data[sq->front];

	sq->front = (sq->front + 1) % 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;
}

sequeue * queue_free(sequeue *sq) {
	if (sq == NULL) {
		printf("sq is NULL\n");
		return NULL;
	}

	free(sq);
	sq = NULL;

	return NULL;
}

  • test.c

    #include <stdio.h>
#include "sequeue.h"

int main(int argc, const char *argv[])
{
	sequeue *sq;

	if ((sq = queue_create()) == NULL) {
		return -1;
	}
	
	enqueue(sq, 10);
	enqueue(sq, 100);
	enqueue(sq, 1000);

	while (!queue_empty(sq)) {
		printf("dequeue:%d\n", dequeue(sq));
	}

	queue_free(sq);

	return 0;
}

3、链式队列

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

typedef int data_t;     
typedef struct node_t
{   
	data_t data ;		
	struct node_t  *next; 	
}linknode_t, *linklist_t;                  

typedef  struct
{  
	linklist_t front, rear; 
} linkqueue_t;

逻辑：
图片描述
图片描述

4、链式队列的实现

创建空队列 ：

linkqueue_t  *CreateQueue()
{ 
      linkqueue_t *lq = (linkqueue_t*)malloc(sizeof(linkqueue_t));
      lq->front = lq->rear = (linklist_t)malloc(sizeof(linknode_t));
      lq->front->next = NULL;	  /*置空队*/
          return lq;     /*返回队列指针*/
}

判断队列空 ：

int  EmptyQueue(linkqueue_t *lq) { 
   return(lq->front == lq->rear) ;
}

入队 :

void EnQueue(linkqueue_t *lq, data_t x)
{
    lq->rear->next = (linklist_t)malloc(sizeof(linknode_t)) ; 
    lq->rear = lq->rear->next; 	     /*修改队尾指针*/
    lq->rear->data = x ;		     /*新数据存入新节点*/
	lq->rear->next = NULL ;	    	 /*新节点为队尾*/
    return;
}

出队：

data_t DeQueue(linkqueue_t  *lq)
{
    data_t   x;
	linklist_t   p;	       /*定义一个指向队头结点的辅助指针*/
	p = lq->front->next ;    /*将它指向队头结点*/
	lq->front->next ＝ p->next ;     /*删除原先队头结点
    x = p->data;
	free(p) ; 	/*释放原队头结点*/
    if(lq->front->next == NULL) 
    lq->rear = lq->front;
    return x;
}

代码举例：

  • linkqueue.h

    typedef int datatype;

typedef struct node {
	datatype data;
	struct node *next;
}listnode , *linklist;

typedef struct {
	linklist front;
	linklist rear;
}linkqueue;

linkqueue * queue_create();
int enqueue(linkqueue *lq, datatype x);
datatype dequeue(linkqueue *lq);
int queue_empty(linkqueue *lq);
int queue_clear(linkqueue *lq);
linkqueue * queue_free(linkqueue *lq);

  • linkqueue.c

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

linkqueue * queue_create() {
	linkqueue *lq;

	if ((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL) {
		printf("malloc linkqueue failed\n");
		return NULL;
	}

	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;

	return lq;
}

int enqueue(linkqueue *lq, datatype x) {
	linklist p;

	if (lq == NULL) {
		printf("lq is NULL\n");
		return -1;
	}

	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;
	}

	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);
}

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;
}

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;
}

  • test.c

    #include <stdio.h>
#include "linkqueue.h"

int main(int argc, const char *argv[])
{
	linkqueue *lq;

	lq = queue_create();
	if (lq == NULL) 
		return -1;

	enqueue(lq, 10);
	enqueue(lq, 20);
	enqueue(lq, 30);
	enqueue(lq, 40);

	//while (!queue_empty(lq)) {
		//printf("dequeue:%d\n", dequeue(lq));
	//}
	queue_clear(lq);

	lq = queue_free(lq);
	enqueue(lq, 50);

	return 0;
}

5、栈和队列的引用——球钟问题

球钟是一个利用球的移动来记录时间的简单装置它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器

若分钟指示器中有2个球，五分钟指示器中有6个球，小时指示器中有5个球，则时间为5:32

工作原理：

  • 每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可容纳4个球。
  • 当放入第五个球时，在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾。而第五个球就会进入五分钟指示器。按此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球。
  • 当小时指示器放入第12个球时，原来的11个球按照他们被放入时的相反顺序加入球队列的队尾，然后第12个球也回到队尾。这时，三个指示器均为空，回到初始状态，从而形成一个循环。因此，该球钟表示时间的范围是从0：00到11：59。

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

程序举例：

  • linkqueue.h

    typedef int datatype;

typedef struct node {
	datatype data;
	struct node *next;
}listnode , *linklist;

typedef struct {
	linklist front;
	linklist rear;
}linkqueue;

linkqueue * queue_create();
int enqueue(linkqueue *lq, datatype x);
datatype dequeue(linkqueue *lq);
int queue_empty(linkqueue *lq);
int queue_clear(linkqueue *lq);
linkqueue * queue_free(linkqueue *lq);

  • linkqueue.c

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

linkqueue * queue_create() {
	linkqueue *lq;

	if ((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL) {
		printf("malloc linkqueue failed\n");
		return NULL;
	}

	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;

	return lq;
}

int enqueue(linkqueue *lq, datatype x) {
	linklist p;

	if (lq == NULL) {
		printf("lq is NULL\n");
		return -1;
	}

	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;
	}

	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);
}

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;
}

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;
}

  • sqstack.h

    typedef int data_t;

typedef struct {
	data_t *data;
	int maxlen;
	int top;
}sqstack;

sqstack * stack_create(int len);
int stack_push(sqstack * s, data_t value);
int stack_empty(sqstack *s);
int stack_full(sqstack *s);
data_t stack_pop(sqstack *s);
data_t stack_top(sqstack *s);
int stack_clear(sqstack *s);
int stack_free(sqstack *s);

  • sqstack.c

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sqstack.h"

sqstack * stack_create(int len) {
	sqstack * s;

	if ((s =(sqstack *)malloc(sizeof(sqstack))) == NULL) {
		printf("malloc sqstack failed\n");
		return NULL;
	}

	if ((s->data = (data_t *)malloc(len * sizeof(data_t)))==NULL) {
		printf("malloc data failed\n");
		free(s);
		return NULL;
	}

	memset(s->data, 0, len*sizeof(data_t));
	s->maxlen = len;
	s->top = -1;

	return s;
}

int stack_push(sqstack * s, data_t value) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}

	if (s->top == s->maxlen-1) {
		printf("stack is full\n");
		return -1;
	}

	s->top++;
	s->data[s->top] = value;

	return 0;
}

/*
 *@ret 1-empty
 * */
int stack_empty(sqstack *s) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	return (s->top == -1 ? 1 : 0);
}

/*
 * @ret 1-full
 * */
int stack_full(sqstack *s) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	return  (s->top == s->maxlen-1 ? 1 : 0);
}

data_t stack_pop(sqstack *s) {
	s->top--;
	return (s->data[s->top+1]);
}

data_t stack_top(sqstack *s) {
	return (s->data[s->top]);
}

int stack_clear(sqstack *s) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	
	s->top = -1;
	return 0;
}

int stack_free(sqstack *s) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	
	if (s->data != NULL) 
		free(s->data);
	free(s);

	return 0;
}

  • test.c

    #include <stdio.h>
#include "linkqueue.h"
#include "sqstack.h"

int check(linkqueue * lq);

int main(int argc, const char *argv[])
{
	linkqueue *lq;
	sqstack *s_hour, *s_five, *s_min;
	int value;
	int i, min = 0;

	if ((lq = queue_create()) == NULL) {
		return -1;
	}

	for (i = 1; i <= 27; i++) {
		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++;
		if (!queue_empty(lq)) {
			value = dequeue(lq);
			if (!stack_full(s_min)) {
				stack_push(s_min, value);
			} else {
				while (!stack_empty(s_min)) {
					enqueue(lq, stack_pop(s_min));
				}
				if (!stack_full(s_five)) {
					stack_push(s_five, value);
				} else {
					while (!stack_empty(s_five)) {
						enqueue(lq, stack_pop(s_five));
					}
					if (!stack_full(s_hour)) {
						stack_push(s_hour, value);
					} else {
						while (!stack_empty(s_hour)) {
							enqueue(lq, stack_pop(s_hour));
						}
						enqueue(lq, value);
						//0:0
						if (check(lq) == 1) {
							break;
						}
					}
				}

			}
		}
	}
	printf("total:%d\n", min);

	printf("dequeue:");
	while (!queue_empty(lq)) 
		printf("%d ", dequeue(lq));
	
	puts("");

	return 0;
}

int check(linkqueue * lq) {//检查是否为升序
	linklist p;

	if (lq == NULL) {
		printf("lq is NULL\n");
		return -1;
	}

	p = lq->front->next;

	while (p && p->next) {
		if (p->data < p->next->data) {
			p = p->next;
		} else {
			return 0;
		}
	}
	return 1;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布