1 #包含
2 #包含
3
4 #define OK 1
5 #define ERR 2
6 #define TRUE 1
7 #define FALSE 0
8 #定义定义最大大小4//队列长度
9
10型态输入状态； //定义函数返回的状态，OK ERR
11类型数据类型； //定义队列中各要素的数据类型，在此暂定为字符类型
12
13 typedef struct { 14 datatype data [ maxsize ]； //存储队列的各要素
15 int front，rear； //头指针和尾指针
16 /*
17假设用于模拟队列的数组长度为8，则入队和出队的方向定义在左侧。 (即，下标0的元素总是用于入队)具有指针end，具有永远识别入队末尾元素的下标。 如果end=0，则指示只有一个队列；如果end=-1，则识别队列为空。 与堆栈中的top指针一样，18当前将三个元素入队。 排列如下。 19ABC____指针end=220将一个元素出队。 也就是说，将下标为0的元素出队。 也就是说，如果a，21_BC____指针end=222，则下标元素为空，必须将所有后面的元素向前移动，然后使指针end-1出队。 如果队列很大，因此不应该用堆栈固定思维来考虑队列。 也就是说，队列的开头不需要位于下标为0的位置。 23这样，定义指针front表示队列开头的元素的后缀，定义指针rear表示队列末尾的元素的下一个元素的后缀，front=rear时表示队列为空。 这是队列的初始状态。 24现在，使用上述队列的存储结构创建新队列。 25_______指针front=0指针rear=026入队3元素，27ABC____指针front=0指针rear=328入队1元素。 29_BC___指针front=1指针rear=330还将三个元素入队，31 _ B C D E F _ _指针front=1指针rear=632还将三个元素入队， 33___EF_指针front=4指针rear=634由于新定义的队列存储结构是由指针front唯一确定的，因此您可以看到它不需要很多向前的元素。 因此，入队只需要rear 1，出队只需要front和35。 但是，在继续入队时会出现很大的问题。 h元素成为数组的最后一个元素。 此时，虽然rear=8，但是下标为8的位置越界了，但是排列开头的下标(0(3)空闲而浪费的现象被称为假溢出。 36要解决上述问题，请将队列的开头和结尾连接起来形成循环队列，并将37用作数组的最后一个元素。 此时，38___efgh指针front=4指针rear=039此时，对三个元素进行排队。 数组如下所示。 40 I J K _ E F G H指针front=4指针rear=341循环队列的这种情况称为队列已满(rear和front之间有一个元素空闲)。 42循环队列已满的条件： (rear 1) %QueueSize==front43循环队列长度表达式： (rear-front QueueSize ) %QueueSize44入队(rear后移动一位) 例如，以上所示队列的QueueSize来自847循环队列的长度表达式。 (以下讨论的数量都是整数。 )对于rearfront，队列长度) reaant其中，如果rear-front始终将正数49作为rearfront的矩阵，则得到的矩阵的长度将大于数组的“最大长度”(QueueSize )。 54到底有多大呢？ 实际上，QueueSize已增大，但不能减去QueueSize。 那样的话，rearfront就无法计算了。 虽然之前添加了，但是最后的结果相当于乘坐QueueSize抵消了以前添加的QueueSize58对rearfront的队列60
61 */
62 )序列队列； 63
64 /*函数原型、队列基本操作、与堆栈相同*/
65序列队列*创建序列队列(void； 66状态身份(序列队列* l )； 67语音清除(序列队列* l )； 68 datatype gettop (序列队列* l； 69 int getlength (序列队列* l； 70 status push (序列队列* l，数据类型
node_to_push);71 datatype pop(SequenceQueue *L);72 void showQueue(SequenceQueue *L);7374 intmain(){75 /*测试*/
76 SequenceQueue *root; //指向一个通过createSequenceQueue函数创建的栈
77 root=createSequenceQueue();78 printf("isEmpty = %d",isEmpty(root));79 printf("Length = %d",getLength(root));80 push(root,'1');81 push(root,'2');82 push(root,'3');83 printf("isEmpty = %d",isEmpty(root));84 printf("Length = %d",getLength(root));85 showQueue(root);86 putchar('');87 printf("can continue to push? %d",push(root,'4'));88 printf("getTop = %c",getTop(root));89 printf("pop = %c",pop(root));90 printf("pop = %c",pop(root));91 printf("isEmpty = %d",isEmpty(root));92 printf("Length = %d",getLength(root));93 push(root,'5');94 showQueue(root);95 putchar('');96 clear(root);97 printf("isEmpty = %d",isEmpty(root));98 printf("Length = %d",getLength(root));99
100 return 0;101 }102
103 SequenceQueue *createSequenceQueue(void){104 SequenceQueue *tmp;105 tmp=malloc(sizeof(SequenceQueue)); //void*类型指针能自动转为其他类型的指针
106 tmp->front=tmp->rear=0; //初始化队列的头尾指针
107 returntmp;108 }109 status isEmpty(SequenceQueue *L){110 if (L->front==L->rear) //front=rear表示队列是空的
111 returnTRUE;112 else
113 returnFALSE;114 }115 void clear(SequenceQueue *L){116 L->front=L->rear=0;117 }118 datatype getTop(SequenceQueue *L){119 //返回队头元素的值
120 return L->data[L->front];121 }122 int getLength(SequenceQueue *L){123 return (L->rear-L->front+MAXSIZE)%MAXSIZE;124 }125 status push(SequenceQueue *L, datatype node_to_push){126 //node_to_insert表示想要入队的元素
127 if ((L->rear+1)%MAXSIZE == L->front) return ERR; //队列已满
128 L->data[L->rear]=node_to_push; //将新元素入队
129 L->rear=(L->rear+1)%MAXSIZE; //指针rear后移
130 returnOK;131 }132 datatype pop(SequenceQueue *L){133 datatype q;134 if (isEmpty(L)) return ERR; //队列是空
135 q=L->data[L->front]; //将要出队的元素先赋值给临时变量s
136 L->front=(L->front+1)%MAXSIZE; //指针front后移
137 return q; //返回出队的元素的值
138 }139 void showQueue(SequenceQueue *L){140 inti;141 int total=getLength(L);142 for (i=0; idata[ (L->front+i)%MAXSIZE ]);144 }145 }146 /*
147 队列的定义：只允许在一端进行插入，另一端进行删除的线性表，也是一种操作受限的线性表148 一般，把允许插入的一端叫做队尾，允许删除的一端叫做队头149 不含任何元素的队列就是空队150 所以，队列又称先进先出(First in First out)的线性表151 */
152 /*环境: Code::Blocks with GCC 5.1*/