数据结构与算法之栈和队列基础——顺序队列、循环队列、链队列（C++）以及栈和队列的应用附解密QQ号

队列基础——顺序队列、循环队列、链队列（C++）以及栈和队列的应用附解密QQ号"/>

数据结构与算法之栈和队列基础——顺序队列、循环队列、链队列（C++）以及栈和队列的应用附解密QQ号

先进先出FIFO

这种先进先出（First In First Out, FIFO）的线性序列，称为“队列”。队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作：一端进，一端出。进的一端称为队尾（rear），出的一端称为队头（front）。队列可以用顺序存储，也可以用链式存储。

顺序队列的定义

队列的顺序存储采用一段连续的空间存储数据元素，并用两个整型变量记录队头和队尾元素的下标。

顺序队列的结构体定义（动态分配）

顺序队列的结构体定义（静态分配）

注意：队列只能在一端进、一端出，不允许在中间查找、取值、插入、删除等操作，先进先出是人为规定的，如果破坏此规则，就不是队列了。

算法图解

这时，虽然队列空间存满了，但是出现了一个大问题！当队满时，Q.front=Q.rear，这和队空的条件一模一样，无法区分到底是队空，还是队满。如何解决呢？

有两种办法：

一种办法是设置一个标志，标记队空和队满；

另一种办法是浪费一个空间，当队尾Q.rear的下一个位置Q.front时，就认为是队满

上述到达尾部又向前存储的队列称为循环队列，为了避免“假溢出”，顺序队列通常采用循环队列。

循环队列的定义

首先简述循环队列队空、队满的判定条件，以及入队、出队、队列元素个数计算等基本操作方法。

队空

无论队头和队尾在什么位置，只要Q.rear和Q.front指向同一个位置，就认为是队空。

循环队列队空的判定条件为：Q.front==Q.rear = 0；

队满

在此采用浪费一个空间的方法，当队尾Q.rear的下一个位置Q.front时，就认为是队满。但是Q.rear向后移动一个位置（Q.rear+1）后，很有可能超出了数组的最大下标，这时它的下一个位置应该为0

在图3-35中，队列的最大空间为Maxsize，当Q.rear=Maxsize-1时，Q.rear+1=Maxsize。而根据循环队列的规则，Q.rear的下一个位置为0才对，怎么才能变成0呢？

可以考虑取余运算，即(Q.rear+1)%Maxsize=0。而此时Q.front=0，即(Q.rear+1)%Maxsize=Q.front，此时为队满的临界状态。

因此，循环队列队满的判定条件为：(Q.rear+1)%Maxsize==Q.front。

入队

出队

注意：循环队列无论是入队还是出队，队尾、队头加1后都要取余运算，主要是为了处理临界状态。

队列元素个数计算

循环队列中到底存了多少个元素呢？循环队列中的内容实际上为Q.front～Q.rear-1这一区间的数据元素，但是不可以直接用两个下标相减得到。因为队列是循环的，所以存在两种情况。

1）Q.rear≥Q.front，如图3-39所示。该队列中元素个数为：Q.rear-Q.front=4-1=3。

2）Q.rear<Q.front

此时，Q.rear=4, Q.front=Maxsize-2, Q.rear-Q.front=6-Maxsize。但是我们可以看到循环队列中的元素实际上为6个，那怎么办呢？当两者之差为负数时，可以将差值加上Maxsize计算元素个数，即Q.rear-Q.front+Maxsize=6-Maxsize+Maxsize=6，元素个数为6。

因此，在计算元素个数时，可以分两种情况判断

• 1）Q.rear≥Q.front：元素个数为Q.rear-Q.front。
• 2）Q.rear<Q.front：元素个数为Q.rear-Q.front+Maxsize。

也可以采用取余的方法把两种情况巧妙地统一为一个语句。队列中元素个数为：(Q.rear-Q.front+Maxsize)%Maxsize。

小结

循环队列的基本操作

循环队列的基本操作包括初始化、入队、出队、取队头元素、求队列长度。

初始化

初始化循环队列时，首先分配一个大小为Maxsize的空间，然后令Q.front=Q.rear=0，即队头和队尾为0，队列为空。

bool InitQueue(SqQueue &Q)
{Q.base = new int[MAXSIZE];if(!Q.base){return false;}Q.front = Q.rear = 0;return true;
}

入队

入队时，首先判断队列是否已满，如果已满，则入队失败；如果未满，则将新元素插入队尾，队尾后移一位。

bool EnQueue(SqQueue &Q, int e)
{if((Q.rear + 1) % MAXSIZE == Q.front){return false;}Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXSIZE;return true;
} 

出队

出队时，首先判断队列是否为空，如果队列为空，则出队失败；如果队列不空，则用变量保存队头元素，然后队头后移一位。

bool DeQueue(SqQueue &Q, int &e)
{if(Q.front == Q.rear){return false;}e = Q.base[Q.front];Q.front = (Q.front + 1) % MAXSIZE;return true;
} 

取队头元素

取队头元素时，只是把队头元素数据复制一份即可，并未改变队头位置，因此队列中的内容没有改变

int GetHead(SqQueue Q)
{if(Q.front != Q.rear){return Q.base[Q.front];}return -1;
}

求队列的长度

通过前面的分析，我们已经知道循环队列中元素个数为：(Q.rear-Q.front+Maxsize)% Maxsize，循环队列中元素个数即为循环队列的长度。

int QueueLength(SqQueue Q)
{return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
} 

敲个代码随便玩儿（循环队列）

#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 10 typedef int ElemType;
typedef struct SqQueue{ElemType *base;int front, rear;
}SqQueue;bool InitQueue(SqQueue &Q)
{Q.base = new int[MAXSIZE];if(!Q.base){return false;}Q.front = Q.rear = 0;return true;
}bool EnQueue(SqQueue &Q, int e)
{if((Q.rear + 1) % MAXSIZE == Q.front){return false;}Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXSIZE;return true;
} bool DeQueue(SqQueue &Q, int &e)
{if(Q.front == Q.rear){return false;}e = Q.base[Q.front];Q.front = (Q.front + 1) % MAXSIZE;return true;
} int GetHead(SqQueue Q)
{if(Q.front != Q.rear){return Q.base[Q.front];}return -1;
}int QueueLength(SqQueue Q)
{return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
} int main()
{SqQueue sq;InitQueue(sq);for(int i = 0; i < 6; i++){EnQueue(sq, i);}int tmp;DeQueue(sq, tmp);cout << "删除的结点为：";cout << tmp << endl;cout << "对头结点为：";cout << GetHead(sq) << endl;return 0;
} 

运行结果：

解密QQ号

#include<stdio.h>int main()
{int q[102] = {0, 6, 3, 1, 7, 5, 8, 9, 2, 4}, head, tail;int i;head = 1;tail = 10;while(head < tail){printf("%d ", q[head]);head++;q[tail] = q[head];tail++;head++;}getchar();return 0;
}

队列小程序

#include<stdio.h>typedef struct queue{int data[100];int head;int tail;
}queue; int main()
{queue q;int i;q.head = 1;q.tail = 1;for(i = 1; i <= 9; i++){scanf("%d", &q.data[q.tail++]);}while(q.head < q.tail){printf("%d ", q.data[q.head++]);q.data[q.tail] = q.data[q.head];q.tail++;q.head++; }getchar();return 0;
}

样例运行结果：

链队列

队列除了用顺序存储，也可以用链式存储。顺序队列和链队列如图所示


顺序队列是分配一段连续的空间，用两个整型下标front和rear分别指向队头和队尾。而链队列类似一个单链表，需要两个指针front和rear分别指向队头和队尾。从队头出队，从队尾入队，为了出队时删除元素方便，可以增加一个头节点。

注意：链队列需要头节点。

因为链队列就是一个单链表的形式，因此可以借助单链表的定义。

注意：链队列需要头节点。因为链队列就是一个单链表的形式，因此可以借助单链表的定义

链队列的结构体定义

链队列的操作和单链表一样，只不过它只能队头删除，在队尾插入，是操作受限的单链表。下面讲解链队列的初始化、入队，出队，取队头元素等操作（元素以int类型为例）。

1．初始化

链队列的初始化，即创建一个头节点，头指针和尾指针指向头节点

void InitQueue(LinkQueue &Q)
{Q.front = Q.rear = new Qnode;Q.front->next = NULL;
} 

2．入队

先创建一个新节点，将元素e存入该节点的数值域


然后将新节点插入队尾，尾指针后移

赋值解释
① Q.rear->next=s：把s节点的地址赋值给队列尾节点的next域，即尾节点的next指针指向s。
② Q.rear=s：把s节点的地址赋值给尾指针，即尾指针指向s，尾指针永远指向队尾。

void EnQueue(LinkQueue &Q, int e)
{Qptr s;s = new Qnode;s->data = e;s->next = NULL;Q.rear->next = s;Q.rear = s;
}

3．出队

出队相当于删除第一个数据元素，即将第一个数据元素节点跳过去。首先用p指针指向第一个数据节点，然后跳过该节点，即Q.front->next=p->next

若队列中只有一个元素，删除后需要修改队尾指针

bool DeQueue(LinkQueue &Q, int &e)
{Qptr p;if(Q.front == Q.rear)		//队空 {return false;}p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear == p){Q.rear = Q.front;}delete p;return true;
}

4．取队头元素

队头实际上是Q.front->next指向的节点，即第一个数据节点，队头元素就是将该节点的数据域存储的元素

int GetHead(LinkQueue Q) 
{if(Q.front != Q.rear){return Q.front->next->data;}return -1;
}

例子自己想去吧，我累了。。。

栈和队列的应用

数制的转换

题目：将一个十进制数n转换为二进制数。

解题思路

十进制数转换为二进制，可以采用辗转相除、取余数的方法得到。例如十进制数11转二进制。先求余数11%2=1，求商11/2=5，然后用商5再求余数，求商，直到商为0，结束。

11%2=1 11/2=5
5%2=1 5/2=2
2%2=0 2/2=1
1%2=1 1/2=0

先求出的余数是二进制数的低位，后求出的余数是二进制数的高位，将得到的余数逆序输出就是所要的二进制数，即11的二进制数为1011。如何将余数逆序输出呢？逆序输出正好符合栈的先入后出性质，因此可以借助栈来实现。

算法步骤

• 1）初始化一个栈S。
• 2）如果n! =0，将n%2入栈S，更新n=n/2。
• 3）重复运行第2步，直到n=0为止。
• 4）如果栈不空，弹出栈顶元素e，输出e，直到栈空。

算法图解

十进制数11转二进制的计算步骤如下：

• 1）初始时，n=11；
• 2）n%2=1,1入栈，更新n=11/2=5；
• 3）n %2 =1,1入栈，更新n=5/2=2；
• 4）n %2 =0,0入栈，更新n=2/2=1；
• 5）n %2 =1,1入栈，更新n=1/2=0；
• 6）n=0时，算法停止。

如果栈不空，则一直出栈

出栈结果正好是十进制数11转换的二进制数1011

#include<bits/stdc++.h>
using namespace std;#define Maxsize 10typedef int ElemType;
typedef struct SqStack{ElemType *base;ElemType *top;
//	int stacksize;
}SqStack;bool InitStack(SqStack &S)
{S.base = new int[Maxsize];if(!S.base){return false;}S.top = S.base;
//	S.stacksize = Maxsize;return true;
}bool Push(SqStack &S, int e)
{if(S.top - S.base == Maxsize){return false;}*S.top++ = e;		//等价于*S.top = e;S.top++; return true;
}bool Pop(SqStack &S, int &e)
{if(S.base == S.top){return false;}e = *--S.top;return true; 
} int GetTop(SqStack S)
{if(S.top != S.base){return *(S.top - 1);}else{return -1;}
} void Binaryconversion(int n)
{SqStack S;int e;InitStack(S);while(n){Push(S, n % 2);n /= 2;} while(S.top != S.base){Pop(S, e);cout << e << '\t';}
} int main()
{SqStack sq;InitStack(sq);
//	for(int i = 0; i < 6; i++)
//	{
//		Push(sq, i);
//	}
//	int tmp;
//	Pop(sq, tmp);
//	cout << tmp << endl;
//	cout << GetTop(sq) << endl; int n;cin >> n;Binaryconversion(n);return 0;
} 

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！