队列的比较和存储方式

笔记和代码的思路来源：

好大学慕课浙江大学陈越、何钦铭的《数据结构》

队列：
   1.介绍
   一种数据结构，遵循先进先出的原则，插入只能在一端进行，删除必须在另一端
   数据插入：入队列
   数据删除：出队列

   2.数据抽象
   队列的抽象数据类型：
       类型名称：队列(Queue)
       数据对象集：一个有0个或者多个元素的又穷线性表

       操作集：长度为maxSize的队列 Q 属于 Queue 队列元素item 属于 elementType

       1.Queue createQueue(int maxSize)       生成长度为maxSize的空队列
       2.int isFullQueue(Queue q ,int maxSize)       判断队列是否满了
       3.void addQueue(Queue q,elementType item)   将数据元素item插入到队列中
       4.int isEmptyQueue(Queue q)           判断队列是否为空
       5.elementType delete(Queue q)           将对头元素进行删除

   3.队列的表现形式
       3.1使用数组来表示
           一般可以选择将队列的头放在数组下标小的位置，将队尾放在数组角标比较大的位置，并使用两个变量font和rear分别
           表示队列的头和尾。一般初始化font和rear为-1，当有元素入队列时，rear+1，出队列时font+1,在删除对头元素
           但是使用上面的存储会存在一个问题，
           ...| | | | | | | | |
                   f       r
           如果此时r=maxSize-1,就无法在向队列里面添加元素了，但是队列实际上在f之前，还是可以插入元素的
           这个现象称为假溢出

           为了解决这样的问题，我们使用循环队列的方式。详细的可以参考书上的图片或者视频
           使用循环队列还是有一个问题，当队列为空时rear==font,当队列满时，read==font
           那么这样就产生了歧义，如何区分队列是空还是满呢。

           方法一：使用一个flag变量记录最后一次操作是入队列还是出队列，如果是入队列导致rear==font,那么队列是满的
               如果是出队列导致rear==font，那么队列是空大。
           方法二：少用一个元素空间，当(rear+1)%maxSize == font 时，我们认为队列就满了。
           队列空的判断条件仍然为 rear==font
           我们的代码演示是基于方法二的。

       3.2 队列的链式存储
           队列的链式存储我们只要确定用哪个指针指向头结点，哪个指针指向尾节点即可
           对于头节点，添加删除均可
           对于尾节点，只能做添加操作，不方便做删除操作

           所有我们这里用font指针指向头节点，用rear指针指向尾结点




    代码：

循环队列的数组存储：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define MAXSIZE 100
 4 
 5 //定义一个循环队列的数组存储。
 6 typedef struct node{
 7     int data[MAXSIZE];
 8     int rear;
 9     int font;
10 }que,*pQueue;
11 
12 
13 pQueue createEmptyQueue(){
14     pQueue queue;
15     queue =(pQueue)malloc(sizeof(que));
16     if(queue){
17         queue->font=-1;
18         queue->rear=-1;
19     }
20     return queue;
21 }
22 
23 int isQueueFull(pQueue queue){
24     return ((queue->rear+1)%MAXSIZE) == (queue->font);
25 }
26 
27 int isQueuempty(pQueue queue){
28     return queue->font == queue->rear;
29 }
30 
31 void addQueue(pQueue queue,int element){
32     if(isQueueFull(queue)){
33         printf("the queue has been filled,don't allow to put other elememt
");
34     }else{
35         queue->rear = (queue->rear+1)%MAXSIZE;
36         queue->data[queue->rear]=element;
37     }
38 }
39 
40 int deleteQueue(pQueue queue){
41     if(isQueuempty(queue)){
42         printf("the queue is null,don't allow delete element from it");
43         return;
44     }else{
45         queue->font = (queue->font+1)%MAXSIZE;
46         return queue->data[queue->font];
47     }
48 }
49 
50 
51 void toString(pQueue queue){
52     int i=queue->font+1;
53     while(i<=queue->rear){
54         printf("%d ",queue->data[i%MAXSIZE]);
55         i++;
56     }
57 }
58 
59 
60 void main(){
61     pQueue queue = createEmptyQueue();
62     addQueue(queue,1);
63     addQueue(queue,2);
64     addQueue(queue,3);
65     addQueue(queue,4);
66     addQueue(queue,5);
67     deleteQueue(queue);
68     toString(queue);
69 }

Queue stored in array

队列的比较和存储方式

相关推荐