C++实现队列：顺序存储、链式存储_c++队列保存

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。
例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。
当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。
队列的示意图如下：

队列主要是两种实现方式，一是基于数组的顺序存储实现，一是基于链表的链式存储实现。

一、顺序存储实现

在用数组存储队列元素时，通常将队列头放在数组下标小的位置，将队列尾放在数组下标大的位置，并用两个变量Front和Rear分别指示队列的头和尾。可将Front和Rear初始化为0或-1，当有元素入队，Rear向右移动一格，放队尾元素+1；当有元素出队，Front向右移动一格，+1，再删除对头元素。
下图(a)(b)©(d)分别为队列在不同状态时的示意图。（通常，在队列非空的状态下，可使Front始终指向队头元素前一个空间）

从上图的©图可看出，当随着元素入队出队，队列整体向后移动到一定的程度，便无法再插入元素，尽管数组在对头之前还有很多冗余空间。这种现象叫做“假溢出”。
为解决这个问题，可在顺序存储中采用循环队列的方式：Rear和Front到达数组断点后，能折回数组开始处。
可想象循环队列的结构如下：

为使Rear和Front能准确传达队列的状态，在对队列进行各种操作时，需要注意Rear和Front的值如何设置：
队空：Q.front =Q. rear
队满： Q.front =(Q.rear + 1) % maxSize
入队: Q.rear = (Q.rear + 1) % maxSize
出队: Q.front = (front + 1) % maxSize;
求队长:(Q.rear-Q.front+maxSize)%maxSize

顺序队列的存储实现：
0.定义顺序队列结构类型

struct SeqQueue
{
    ElementType data[MaxSize];
    int Front,Rear;
};
1
2
3
4
5

1.初始化队列

void CreateQueue(SeqQueue *Q)
{
    Q->Front=0;
    Q->Rear=0;
}
1
2
3
4
5

2.判断是否队满

bool IsFull(SeqQueue *Q)
{
    return((Q->Rear+1)%MaxSize==Q->Front);
}
1
2
3
4

3.判断是否队空

bool IsEmpty(SeqQueue *Q)
{
    return(Q->Front==Q->Rear);
}
1
2
3
4

4.入队：在对尾插入元素X

void InsertQue(SeqQueue *Q,ElementType X)
{
    if(IsFull(Q))
        cout<<"队列满"<<endl;
    else{
        Q->Rear=(Q->Rear+1)%MaxSize; //避免“假溢出”，同时使两者最初所指的内存为空
        Q->data[Q->Rear]=X;
    }
}
1
2
3
4
5
6
7
8
9

5.出队：返回队头元素

ElementType DeleteQue(SeqQueue *Q)
{
    if(IsEmpty(Q)){
        cout<<"队已空"<<endl;
        return 0;
    }
    else{
        Q->Front=(Q->Front+1)%MaxSize;
        return(Q->data[Q->Front]);
    }
}
1
2
3
4
5
6
7
8
9
10
11

6.求队长

int LengthQue(SeqQueue *Q)
{
    return((Q->Rear-Q->Front+MaxSize)%MaxSize);
}
1
2
3
4

以下为一个完整程序，其功能是在队列中存入1~10这10个元素，并依据其存入的先后顺序，将其输出：

#include <iostream>
#define MaxSize 20
using namespace std;
typedef int ElementType;
/*定义顺序队列结构类型*/
struct SeqQueue
{
    ElementType data[MaxSize];
    int Front,Rear;
};

int main()
{
    void CreateQueue(SeqQueue *Q);
    bool IsFull(SeqQueue *Q);
    bool IsEmpty(SeqQueue *Q);
    void InsertQue(SeqQueue *Q,ElementType X);
    ElementType DeleteQue(SeqQueue *Q);
    int LengthQue(SeqQueue *Q);

    SeqQueue Que,*Q;
    Q=&Que;
    CreateQueue(Q);
    for(int i=1;i<11;i++)   //在队列中输入1~10这10个元素
        InsertQue(Q,i);     //求队长
    cout<<"队长="<<LengthQue(Q)<<endl;
    while(!IsEmpty(Q))     //输出
        cout<<DeleteQue(Q)<<' ';

    return 0;
}

/*初始化队列*/
void CreateQueue(SeqQueue *Q)
{
    Q->Front=0;
    Q->Rear=0;
}

/*判断是否队满*/
bool IsFull(SeqQueue *Q)
{
    return((Q->Rear+1)%MaxSize==Q->Front);
}

/*判断是否队空*/
bool IsEmpty(SeqQueue *Q)
{
    return(Q->Front==Q->Rear);
}

/*入队：在对尾插入元素X*/
void InsertQue(SeqQueue *Q,ElementType X)
{
    if(IsFull(Q))
        cout<<"队列满"<<endl;
    else{
        Q->Rear=(Q->Rear+1)%MaxSize; //避免“假溢出”，同时使两者最初所指的内存为空
        Q->data[Q->Rear]=X;
    }
}

/*出队：返回队头元素*/
ElementType DeleteQue(SeqQueue *Q)
{
    if(IsEmpty(Q)){
        cout<<"队已空"<<endl;
        return 0;
    }
    else{
        Q->Front=(Q->Front+1)%MaxSize;
        return(Q->data[Q->Front]);
    }
}

/*求队长*/
int LengthQue(SeqQueue *Q)
{
    return((Q->Rear-Q->Front+MaxSize)%MaxSize);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

二、链式存储实现

队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。
下图为链队在非空和空状态下的示意图：

如图示，可设链栈的结点类型为QueNode，Front和Rear皆为指向QueNode结点的指针，可设置一个为空的结点（上图紫色结点），初始化时Front和Rear皆指向它，插入和删除操作皆在该节点之后的队列中执行。
所以，定义链队的结构类型有两步：
（1）定义结点类型

struct QueNode
{
    ElementType data;
    QueNode *next;
};
1
2
3
4
5

（2）定义指向结点的指针类型

struct LinkQueue
{
    QueNode *Front;
    QueNode *Rear;
};
1
2
3
4
5

链队的主要操作如下：
1.初始化

void CreateQueue(LinkQueue *Q)
{
    Q->Front->next=NULL;
    Q->Rear->next=NULL;
}
1
2
3
4
5

初始化后的队列大致如上图中的空队列。
需要注意的是，在初始化之前，需要对LinkQueue类型的指针对象的Front和Rear所指向的结点作出声明，如下：

QueNode node;
    LinkQueue *Q;
    Q->Front=&node;
    Q->Rear=&node;
1
2
3
4

2.判断是否队空

bool IsEmpty(LinkQueue *Q)
{
    return(Q->Front->next==NULL && Q->Rear->next==NULL);
}
1
2
3
4

3.入队：在队尾插入元素X

void InsertQue(LinkQueue *Q,ElementType X)
{
    QueNode *p;
    p=new QueNode;
    p->data=X;
    p->next=NULL;
    if(IsEmpty(Q))
        Q->Front->next=Q->Rear=p;
    else{
        Q->Rear->next=p;
        Q->Rear=p;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.出队：返回队头元素

ElementType DeleteQue(LinkQueue *Q)
{
    ElementType x;
    QueNode *p;
    if(IsEmpty(Q)){
        cout<<"队空"<<endl;
        return 0;
    }
    p=Q->Front->next;
    x=p->data;
    Q->Front->next=p->next;
    if(Q->Rear==p)
        Q->Rear=Q->Front;
    delete p;
    return(x);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

以下为一个完整程序，其功能是在队列中存入1~10这10个元素，并依据其存入的先后顺序，将其输出：

#include <iostream>
using namespace std;
typedef int ElementType;
/*定义链队结构类型*/
struct QueNode
{
    ElementType data;
    QueNode *next;
};
struct LinkQueue
{
    QueNode *Front;
    QueNode *Rear;
};

int main()
{
    void CreateQueue(LinkQueue *Q);
    bool IsEmpty(LinkQueue *Q);
    void InsertQue(LinkQueue *Q,ElementType X);
    ElementType DeleteQue(LinkQueue *Q);

    QueNode node;
    LinkQueue *Q;
    Q->Front=&node;
    Q->Rear=&node;
    CreateQueue(Q);
    for(int i=1;i<11;i++)   //在队列中输入1~10这10个元素
        InsertQue(Q,i);     //求队长
    while(!IsEmpty(Q))     //输出
        cout<<DeleteQue(Q)<<' ';

    return 0;
}

/*初始化队列*/
void CreateQueue(LinkQueue *Q)
{
    Q->Front->next=NULL;
    Q->Rear->next=NULL;
}


/*判断是否队空*/
bool IsEmpty(LinkQueue *Q)
{
    return(Q->Front->next==NULL && Q->Rear->next==NULL);
}

/*入队：在对尾插入元素X*/
void InsertQue(LinkQueue *Q,ElementType X)
{
    QueNode *p;
    p=new QueNode;
    p->data=X;
    p->next=NULL;
    if(IsEmpty(Q))
        Q->Front->next=Q->Rear=p;
    else{
        Q->Rear->next=p;
        Q->Rear=p;
    }
}

/*出队：返回队头元素*/
ElementType DeleteQue(LinkQueue *Q)
{
    ElementType x;
    QueNode *p;
    if(IsEmpty(Q)){
        cout<<"队空"<<endl;
        return 0;
    }
    p=Q->Front->next;
    x=p->data;
    Q->Front->next=p->next;
    if(Q->Rear==p)
        Q->Rear=Q->Front;
    delete p;
    return(x);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82