3.3队列

分类

静态队列-用数组实现

链式队列-用链表实现

一般情况下真正实用的顺序队列是循环队列

队列的具体应用：

所有和时间有关的操作都有队列的影子

 

顺序循环队列

静态队列-用数组实现

#include <stdio.h>
#include <stdlib.h>
#define QueueSize 100
typedef int DataType;

typedef struct
{
	DataType data[QueueSize];
	int front, rear;
}CirQueue;

void InitQueue(CirQueue *Q);//置空队列
int QueueEmpty(CirQueue *Q);//判队空
int QueueFull(CirQueue *Q);//判队满
void EnQueue(CirQueue *Q, DataType x);//入队列
DataType GetFront(CirQueue *Q);//取对头元素
DataType DeQueue(CirQueue *Q);//出队列
int QueueLength(CirQueue *Q);//队列长度

void main()
{
	CirQueue Q;
	int i = 0;

	InitQueue(&Q);//置空队列
	for (i = 0; i < 10; i++)
	{
		EnQueue(&Q, i);//入队列
	}

	printf("%d
", QueueLength(&Q));//队列长度

	while (!QueueEmpty(&Q))//判队空
	{
		printf("%d ", DeQueue(&Q));//出队列
	}
}

void InitQueue(CirQueue *Q)//置空队列
{
	Q->front = Q->rear = 0;
}

int QueueEmpty(CirQueue *Q)//判队空
{
	return Q->rear == Q->front;
}

int QueueFull(CirQueue *Q)//判队满
{
	return (Q->rear + 1) % QueueSize == Q->front;
}

void EnQueue(CirQueue *Q, DataType x)//入队列
{
	if (QueueFull(Q))
	{
		printf("queue overflow
");
	}
	else
	{
		Q->data[Q->rear] = x;
		Q->rear = (Q->rear + 1) % QueueSize;//循环意义下的加1
	}
}

DataType GetFront(CirQueue *Q)//取对头元素
{
	if (QueueEmpty(Q))
	{
		printf("queue empty
");
		exit(0);//出错退出处理
	}
	else
	{
		return Q->data[Q->front];//返回队头元素值
	}
}

DataType DeQueue(CirQueue *Q)//出队列
{
	if (QueueEmpty(Q))
	{
		printf("queue empty
");
		exit(0);//出错退出处理
	}
	else
	{
		DataType x = Q->data[Q->front];//保存待删除元素值
		Q->front = (Q->front + 1) % QueueSize;//头指针加1
		return x;//返回队头元素值
	}
}

int QueueLength(CirQueue *Q)//队列长度
{
	return (QueueSize + (Q->rear) - (Q->front)) % QueueSize;
}

动态数组实现队列

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define QueueSize 6
  5 typedef int DataType;//假设数据为int
  6 
  7 struct queue
  8 {
  9     DataType * base;//数组
 10     int front, rear;
 11 };
 12 
 13 typedef struct queue CirQueue;
 14 
 15 void InitQueue(CirQueue * Q);//置空队列
 16 int QueueEmpty(CirQueue * Q);//判队空
 17 int QueueFull(CirQueue * Q);//判队满
 18 void EnQueue(CirQueue * Q, DataType x);//入队列
 19 DataType GetFront(CirQueue * Q);//取队头元素
 20 DataType DeQueue(CirQueue * Q);//出队列
 21 
 22 void TraverseQueue(CirQueue * Q);//遍历队列
 23 
 24 void main()
 25 {
 26     CirQueue Q;
 27 
 28     InitQueue(&Q);//置空队列
 29 
 30     EnQueue(&Q, 1);//入队列
 31     EnQueue(&Q, 2);
 32     EnQueue(&Q, 3);
 33     EnQueue(&Q, 4);
 34     EnQueue(&Q, 5);
 35 
 36     TraverseQueue(&Q);//遍历队列
 37 
 38     printf("出队列的元素是%d
", DeQueue(&Q));//出队列
 39     printf("出队列的元素是%d
", DeQueue(&Q));
 40     printf("出队列的元素是%d
", DeQueue(&Q));
 41     printf("出队列的元素是%d
", DeQueue(&Q));
 42     printf("出队列的元素是%d
", DeQueue(&Q));
 43     printf("出队列的元素是%d
", DeQueue(&Q));
 44 
 45     system("pause");
 46 }
 47 
 48 void InitQueue(CirQueue * Q)//置空队列
 49 {
 50     Q->base = (DataType *)malloc(sizeof(DataType)*QueueSize);
 51     Q->front = Q->rear = 0;
 52 }
 53 
 54 int QueueEmpty(CirQueue * Q)//判队空
 55 {
 56     return Q->front == Q->rear;
 57 }
 58 
 59 int QueueFull(CirQueue * Q)//判队满
 60 {
 61     return (Q->front + 1) % QueueSize == Q->front;
 62 }
 63 
 64 void EnQueue(CirQueue * Q, DataType x)//入队列
 65 {
 66     if (QueueFull(Q))
 67     {
 68         printf("Queue overflow
");
 69     }
 70     else
 71     {
 72         Q->base[Q->rear] = x;
 73         Q->rear = (Q->rear + 1) % QueueSize;//循环意义下的加1
 74     }
 75 }
 76 
 77 DataType GetFront(CirQueue * Q)//取队头元素
 78 {
 79     if (QueueEmpty(Q))
 80     {
 81         printf("Queue empty
");
 82         exit(0);//出错退出处理
 83     }
 84     else
 85     {
 86         return Q->base[Q->front];//返回队头元素值
 87     }
 88 }
 89 
 90 DataType DeQueue(CirQueue * Q)//出队列
 91 {
 92     DataType x;
 93     if (QueueEmpty(Q))
 94     {
 95         printf("Queue empty
");
 96         exit(0);//出错退出处理
 97     }
 98     else
 99     {
100         x = Q->base[Q->front];//保存待删除元素值
101         Q->front = (Q->front + 1) % QueueSize;//头指针加1
102         return x;//返回队头元素值
103     }
104 }
105 
106 void TraverseQueue(CirQueue * Q)//遍历队列
107 {
108     int i = Q->front;
109 
110     while (i != Q->rear)
111     {
112         printf("%d ", Q->base[i]);
113         i = (i + 1) % QueueSize;
114     }
115     printf("
");
116 }

链式队列-用链表实现

创建一个链队列，实现优先队列

链队列比一般队列的好处，没有范围限制。

1 头文件Queue.h

2 源文件main.c

3 源文件Queue.c

复制代码
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 struct queue
 5 {
 6     int num;
 7     int high;//优先级
 8     struct queue *pNext;//存储下一个结点的地址
 9 };
10 
11 typedef struct queue QUEUDE;//简化队列
12 
13 QUEUDE *init(QUEUDE *queueA);//初始化
14 QUEUDE *EnQueue(QUEUDE *queueA, int num, int high);//顺序入队
15 QUEUDE *DeQuedu(QUEUDE *queueA, QUEUDE *pout);//顺序出队
16 QUEUDE *freeall(QUEUDE *queueA);//清空
17 QUEUDE *insertEnQuedu(QUEUDE *queueA, int num, int high);//队列插入，采用插入排序，不要用冒泡排序，原因：优先级相同，也可能会交换
18 void printall(QUEUDE *queueA);//打印所有数据，递归
复制代码

2 源文件main.c

复制代码
 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 #include "Queue.h"
 6 
 7 main()
 8 {
 9     QUEUDE *phead = NULL;//创建头结点
10     phead = init(phead);//初始化
11 
12     phead = insertEnQuedu(phead, 1, 3);
13     printall(phead);//打印所有数据，递归
14     printf("
");
15 
16     phead = insertEnQuedu(phead, 2, 12);
17     printall(phead);//打印所有数据，递归
18     printf("
");
19 
20     phead = insertEnQuedu(phead, 3, 3);
21     printall(phead);//打印所有数据，递归
22     printf("
");
23 
24     phead = insertEnQuedu(phead, 4, 14);
25     printall(phead);//打印所有数据，递归
26     printf("
");
27 
28     phead = insertEnQuedu(phead, 5, 5);
29     printall(phead);//打印所有数据，递归
30     printf("
");
31 
32     phead = insertEnQuedu(phead, 6, 16);
33     printall(phead);//打印所有数据，递归
34     printf("
");
35 
36     phead = insertEnQuedu(phead, 7, 0);
37     printall(phead);//打印所有数据，递归
38     printf("
");
39 
40     phead = insertEnQuedu(phead, 8, 0);
41     printall(phead);//打印所有数据，递归
42     printf("
");
43 
44     phead = insertEnQuedu(phead, 9, 1);
45     printall(phead);//打印所有数据，递归
46     printf("
");
47 
48     phead = insertEnQuedu(phead, 10, 0);
49     printall(phead);//打印所有数据，递归
50     printf("
");
51 
52     phead = insertEnQuedu(phead, 11, 16);
53     printall(phead);//打印所有数据，递归
54     printf("
");
55 
56     phead = insertEnQuedu(phead, 111, 19);
57     printall(phead);//打印所有数据，递归
58     printf("
");
59 
60     //while (phead != NULL)//出队
61     //{
62     //    QUEUDE *ptemp = (QUEUDE *)malloc(sizeof(QUEUDE));
63     //    phead = DeQuedu(phead, ptemp);
64     //    printf("出队一次
");
65     //    printall(phead);//打印所有数据，递归
66     //    printf("出队的是%d,%d
", ptemp->num, ptemp->high);
67     //}
68     
69     system("pause");
70 }
复制代码

3 源文件Queue.c

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include "Queue.h"
  4 
  5 QUEUDE *init(QUEUDE *queueA)//初始化
  6 {
  7     return NULL;
  8 }
  9 
 10 QUEUDE *EnQueue(QUEUDE *queueA, int num, int high)//顺序入队
 11 {
 12     QUEUDE *pnewnode = (QUEUDE *)malloc(sizeof(QUEUDE));//分配内存
 13     pnewnode->num = num;
 14     pnewnode->high = high;
 15     pnewnode->pNext = NULL;
 16 
 17     if (queueA == NULL)//链表为空
 18     {
 19         queueA = pnewnode;
 20         return queueA;
 21     }
 22     else
 23     {
 24         QUEUDE *p = queueA;//头结点
 25         while (p->pNext != NULL)//确定要插入的位置
 26         {
 27             p = p->pNext;
 28         }
 29         p->pNext = pnewnode;//插入
 30 
 31         return queueA;
 32     }
 33 }
 34 
 35 QUEUDE *DeQuedu(QUEUDE *queueA, QUEUDE *pout)//顺序出队
 36 {
 37     if (queueA == NULL)
 38     {
 39         return NULL;
 40     }
 41     else
 42     {
 43         pout->num = queueA->num;
 44         pout->high = queueA->high;
 45         QUEUDE *ptemp = queueA;//记录要删除的地址
 46         queueA = queueA->pNext;//跳过queueA
 47         free(ptemp);
 48         return queueA;
 49     }
 50 }
 51 
 52 QUEUDE *freeall(QUEUDE *queueA)//清空，与栈一样
 53 {
 54 
 55 }
 56 
 57 QUEUDE *insertEnQuedu(QUEUDE *queueA, int num, int high)//队列插入，采用插入排序，不要用冒泡排序，原因：优先级相同，也可能会交换
 58 {
 59     //实现从大到小插入
 60     QUEUDE *pnewnode = (QUEUDE *)malloc(sizeof(QUEUDE));//分配内存
 61     pnewnode->num = num;
 62     pnewnode->high = high;
 63 
 64     if (queueA == NULL)//原队列为空
 65     {
 66         pnewnode->pNext = NULL;
 67         queueA = pnewnode;
 68         return queueA;
 69     }
 70     else
 71     {
 72         if (pnewnode->high > queueA->high)//头部插入1/3
 73         {
 74             pnewnode->pNext = queueA;
 75             queueA = pnewnode;//指向这个结点
 76             return queueA;
 77         }
 78         else
 79         {
 80             QUEUDE *p = queueA;//头结点
 81             while (p->pNext != NULL)
 82             {
 83                 p = p->pNext;//p循环到尾部
 84             }
 85             if (pnewnode->high <= p->high)//尾部插入2/3
 86             {
 87                 p->pNext = pnewnode;
 88                 pnewnode->pNext = NULL;
 89                 return queueA;
 90             }
 91             else//中间插入3/3
 92             {
 93                 QUEUDE *p1, *p2;
 94                 p1 = p2 = NULL;//避免野指针
 95                 p1 = queueA;//头结点
 96                 while (p1->pNext != NULL)
 97                 {
 98                     p2 = p1->pNext;
 99                     if (p1->pNext >= pnewnode->high  && p2->high <= pnewnode->high)
100                     {
101                         pnewnode->pNext = p2;
102                         p1->pNext = pnewnode;//插入
103                         break;
104                     }
105                     p1 = p1->pNext;
106                 }
107                 return queueA;
108             }
109         }
110     }
111 }
112 
113 void printall(QUEUDE *queueA)//打印所有数据，递归
114 {
115     if (queueA == NULL)
116     {
117         return;
118     }
119     else
120     {
121         printf("%d,%d,%x,%x
", queueA->num, queueA->high, queueA, queueA->pNext);
122         printall(queueA->pNext);//进入下一个
123     }
124 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/denggelin/p/5690261.html