第二章 栈和队列
1 顺序栈
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 50
typedef struct {
ElemType data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack& S, ElemType x);
bool Pop(SqStack& S, ElemType &x);
bool GetTop(SqStack S, ElemType& x);
bool DestoryStack(SqStack& S);
// 1、初始化一个空栈
void InitStack(SqStack& S)
{
S.top = -1; // 令栈顶指针top指向-1表示空栈
}
// 2、判断栈是否为空。空则true,不空则false
bool StackEmpty(SqStack S)
{
if (S.top == -1) return true; // 空则true
return false; // 不空则false
}
// 进栈。未满则进,成为新栈顶
bool Push(SqStack& S, ElemType x)
{
if (S.top == MaxSize - 1)
return false; // 如果栈满,则返回false
S.data[++S.top] = x; // 否则将top指针加一,再入栈
return true;
}
// 出栈。非空则弹出栈顶元素
bool Pop(SqStack& S, ElemType& x)
{
if (S.top == -1) return false; // 如果为空栈,则返回false
x = S.data[S.top--]; // 否则,令x为栈顶元素,然后将top指针 --
return true;
}
// 读栈顶元素。非空则返回栈顶元素
bool GetTop(SqStack S, ElemType& x)
{
if (S.top == -1) return false; // 如果为空栈,则返回false
x = S.data[S.top]; // 否则令x等于栈顶元素
return true;
}
// 销毁栈
bool DestroyStack(&S)
// 测试功能
void test() {
SqStack S;
InitStack(S);
for (int i = 0; i <= 5; i++) {
Push(S, i);
}
ElemType x;
GetTop(S, x);
cout << x << endl;
while (!StackEmpty(S)) {
Pop(S, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
2 共享栈
- 两头出发,共享一个数组
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 10
typedef struct // 定义共享栈结构体
{
ElemType data[MaxSize];
int top0; // 定义栈0的指针(数组一头
int top1; // 定义栈1的指针(数组的另一头
}ShStack;
void InitStack(ShStack& S);
bool StackEmpty(ShStack S);
bool StackFull(ShStack S); //判断栈是否满了
bool Push0(ShStack& S, ElemType x);
bool Push1(ShStack& S, ElemType x);
bool Pop0(ShStack& S, ElemType& x);
bool Pop1(ShStack& S, ElemType& x);
bool GetTop0(ShStack S, ElemType& x);
bool GetTop1(ShStack S, ElemType& x);
bool DestoryStack0(ShStack& S);
bool DestoryStack1(ShStack& S);
// 1、初始化。令top0为-1,top1为数组长度(栈顶 + 1)
void InitStack(ShStack& S)
{
S.top0 = -1;
S.top1 = MaxSize;
}
// 2、判断空栈。空则true,否则为false
bool StackEmpty(ShStack S)
{
if (S.top0 == -1 && S.top1 == MaxSize)
return true;
return false;
}
// 判断栈满。满则true
bool StackFull(ShStack S)
{
if (S.top0 + 1 == S.top1) return true; // 如果top0 + 1后和top1重叠,说明栈满
return false;
}
// 向栈0内插入元素
bool Push0(ShStack& S, ElemType x)
{
if (StackFull(S) == true) return false;
S.data[++S.top0] = x; // 插完元素后,指针 + 1
return true;
}
// 向栈1内插入元素
bool Push1(ShStack& S, ElemType x)
{
if (StackFull(S) == true) return false;
S.data[--S.top1] = x; // 插完元素后,指针 - 1
return true;
}
// 删栈0的元素
bool Pop0(ShStack& S, ElemType& x)
{
if (S.top0 == -1) return false;
x = S.data[S.top0--];
return true;
}
// 删栈1的元素
bool Pop1(ShStack& S, ElemType& x) {
if (S.top1 == MaxSize) return false;
x = S.data[S.top1++];
return true;
}
// 获取栈0顶元素
bool GetTop0(ShStack S, ElemType& x)
{
if (S.top0 == -1) return false;
x = S.data[S.top0];
return true;
}
// 获取栈1顶元素
bool GetTop1(ShStack S, ElemType& x)
{
if (S.top1 == MaxSize) return false;
x = S.data[S.top1];
return true;
}
// 测试
void test() {
ShStack S;
InitStack(S);
for (int i = 1; i <= 5; i++) {
Push0(S, i);
}
for (int i = 1; i <= 5; i++) {
Push1(S, i);
}
ElemType x;
GetTop0(S, x);
cout << x << endl;
GetTop1(S, x);
cout << x << endl;
bool f = Push0(S, 6);
if (f) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
f = Push1(S, 6);
if (f) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
while (Pop0(S,x)) {
cout << x << endl;
}
while (Pop1(S, x)) {
cout << x << endl;
}
}
int main() {
test();
return 0;
}
3 链栈(带头)
链栈的操作和链表类似,入栈和出战的操作都在链表的表头进行
对于带头结点和不带头结点的链栈,具体的实现会有所不同
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct LinkNode {
ElemType data; // 数据域
struct LinkNode* next; // 指针域
}*LiStack; // 栈类型定义
bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, ElemType x);
bool Pop(LiStack& S, ElemType& x);
bool GetTop(LiStack S, ElemType& x);
bool DestoryStack(LiStack& S);
bool InitStack(LiStack& S) {
S = (LiStack)malloc(sizeof(LinkNode));
if (S == NULL) return false;
S->next = NULL;
return true;
}
bool StackEmpty(LiStack S) {
if (S->next == NULL) return true;
return false;
}
bool Push(LiStack& S, ElemType x) {
LinkNode* p;
p = (LinkNode*)malloc(sizeof(LinkNode));
if (p == NULL) return false;
p->data = x;
p->next = S->next;
S->next = p;
return true;
}
bool Pop(LiStack& S, ElemType& x) {
if (StackEmpty(S)) return false;
LinkNode* p = S->next;
S->next = p->next;
x = p->data;
free(p);
return true;
}
bool GetTop(LiStack S, ElemType& x) {
if (StackEmpty(S)) return false;
x = S->next->data;
return true;
}
bool DestoryStack(LiStack& S) {
while (S->next != NULL) {
LinkNode* p = S->next;
S->next = p->next;
free(p);
}
free(S);
return true;
}
void test() {
LiStack S;
InitStack(S);
for (int i = 0; i <= 5; i++) {
Push(S, i);
}
ElemType x;
GetTop(S, x);
cout << x << endl;
while (!StackEmpty(S)) {
Pop(S, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
4 链栈(不带头)
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct LinkNode {
ElemType data;
struct LinkNode* next;
}*LiStack, LinkNode;
bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, ElemType x);
bool Pop(LiStack& S, ElemType& x);
bool GetTop(LiStack S, ElemType& x);
bool DestoryStack(LiStack& S);
bool InitStack(LiStack& S) {
S = NULL;
return true;
}
bool StackEmpty(LiStack S) {
if (S == NULL) return true;
return false;
}
bool Push(LiStack& S, ElemType x) {
LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
if (p == NULL) return false;
p->data = x;
p->next = S;
S = p;
return true;
}
bool Pop(LiStack& S, ElemType& x) {
if (StackEmpty(S)) return false;
LinkNode* p = S;
S = S->next;
x = p->data;
free(p);
return true;
}
bool GetTop(LiStack S, ElemType& x) {
if (StackEmpty(S)) {
return false;
}
x = S->data;
return true;
}
bool DestoryStack(LiStack& S) {
while (S != NULL) {
LinkNode* p = S;
S = S->next;
free(p);
}
free(S);
S = NULL;
return true;
}
void test() {
LiStack S;
InitStack(S);
for (int i = 0; i <= 5; i++) {
Push(S, i);
}
ElemType x;
GetTop(S, x);
cout << x << endl;
while (!StackEmpty(S)) {
Pop(S, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
5 顺序队列
顺序队列存在缺点,即无法用Q.rear == Maxsize来判断队满,因为当rear指向数组最后元素位置时,进行出队,元素减少了,但是依旧会判断为队满。
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5 // 定义队列中元素的最大个数
typedef struct {
int front, rear; // 队头指针和队尾指针
ElemType data[MaxSize]; // 存放队列元素
}SqQueue;
void InitQueue(SqQueue &Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue &Q, ElemType x);
bool DeQueue(SqQueue &Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
// 1 初始化队列 - 构造一个空队
void InitQueue(SqQueue &Q) {
Q.front = Q.rear = 0;
}
// 2 判队列空
bool QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear) return true; // 如果队空(头尾指针只在一起)则返回true
return false;
}
// 3 判队列满
bool QueueFull(SqQueue Q) {
if (Q.rear == MaxSize) return true; // 如果尾指针指向队尾(数组最大值的后一个位置)
return false;
}
// 4 入队
bool EnQueue(SqQueue &Q, ElemType x) {
if (QueueFull(Q) == true) return false; //如果队满,则false
Q.data[Q.rear++] = x; // 否则将x加入,并令尾指针向向后加1
return true;
}
// 5 出队
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q) == true) return false; // 如果队空,则false
x = Q.data[Q.front++]; // 否则令x等于源队头元素,并令队头指针向后加1
return true;
}
// 6 读队头元素
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q) == true) return false; // 如果队列为空,则false
x = Q.data[Q.front]; // 否则,将队头元素赋值给x
return true;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
EnQueue(Q, i);
}
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
ElemType x;
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6 循环队列
循环队列就是针对顺序队列存在的缺点进行改进的
6.1 rear指向队尾指针的后一个位置 && 牺牲一个存储空间来区分队空和队满
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
// 1 初始化循环队列
void InitQueue(SqQueue& Q) {
Q.front = Q.rear = 0; // 初始化首尾指针
}
// 2 判断队空
bool QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear) return true; // 队空条件
return false;
}
// 3 判断队满
bool QueueFull(SqQueue Q) {
if ((Q.rear + 1) % MaxSize == Q.front) return true; // *队满条件:队头指针在队尾指针的下一个位置
return false;
}
// 4 入队
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; // 如果队满,则false
Q.data[Q.rear] = x; //
Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针加1取模
return true;
}
// 5 出队
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) return false; // 队空则false
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize; // 队头指针加1取模
return true;
}
// 6 获取队头元素
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q) == true) return false; // 队空则false
x = Q.data[Q.front];
return true;
}
// 7 获取当前队列长度
int GetSize(SqQueue Q) {
return (Q.rear - Q.front + MaxSize) % MaxSize; // 长度公式
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.2 rear指向队尾指针的后一个位置 && 增设size判断
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
int size;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = Q.rear = Q.size = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.size == 0) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if (Q.size == MaxSize) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
Q.size++;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.size--;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return Q.size;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.3 rear指向队尾指针的后一个位置 && 增设tag判断
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
int tag;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = Q.rear = Q.tag = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.tag == 0 && Q.front == Q.rear) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if (Q.tag == 1 && Q.front == Q.rear) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
Q.tag = 1;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.tag = 0;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return (Q.rear - Q.front + MaxSize) % MaxSize;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.4 rear指向队尾 && 牺牲一个存储空间来区分队空和队满
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = 0;
Q.rear = -1;
}
bool QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear+1 ) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if ((Q.rear + 2) % MaxSize == Q.front) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.rear = (Q.rear + 1) % MaxSize;
Q.data[Q.rear] = x;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return (Q.rear - Q.front +1 + MaxSize) % MaxSize;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.5 rear指向队尾 && 增设size判断
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
int size;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = 0;
Q.rear = -1;
Q.size = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.size == 0) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if (Q.size == MaxSize) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.rear = (Q.rear + 1) % MaxSize;
Q.data[Q.rear] = x;
Q.size++;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.size--;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return Q.size;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.6 rear指向队尾 && 增设tag判断
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
int tag;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = 0;
Q.rear = -1;
Q.tag = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear + 1 && Q.tag == 0) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if (Q.front == Q.rear + 1 && Q.tag == 1) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.rear = (Q.rear + 1) % MaxSize;
Q.data[Q.rear] = x;
Q.tag = 1;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.tag = 0;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return (Q.rear - Q.front + 1 + MaxSize) % MaxSize;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
1 链队列(不带头)
#include<iostream>
using namespace std;
typedef int ElemType;
// 定义链队列结点
typedef struct LinkNode {
ElemType data;
struct LinkNode* next;
}LinkNode;
// 定义链队列
typedef struct {
LinkNode* front, * rear;
}LinkQueue;
void InitQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
bool EnQueue(LinkQueue& Q, ElemType x);
bool DeQueue(LinkQueue& Q, ElemType& x);
bool GetHead(LinkQueue Q, ElemType& x);
// 1 初始化
void InitQueue(LinkQueue& Q) {
Q.front = Q.rear = NULL;
}
// 2 判断队空
bool QueueEmpty(LinkQueue Q) {
if (Q.front == NULL) return true;
return false;
}
// 3 入队
bool EnQueue(LinkQueue& Q, ElemType x) {
LinkNode* s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x; s->next = NULL; // 创建新结点,插入到链尾
Q.rear->next = s;
Q.rear = s;
return true;
}
// 出队
bool DeQueue(LinkQueue& Q, ElemType& x) {
if (Q.front == Q.rear) return false; // 如果队空,则false
LinkNode* p = Q.front->next;
x = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.front = Q.rear; // 若原队列只有一个结点,删除后变空
free(p);
return true;
}
bool GetHead(LinkQueue Q, ElemType& x) {
if (QueueEmpty(Q)) return false;
x = Q.front->data;
return true;
}
void test() {
LinkQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
EnQueue(Q, i);
}
ElemType x;
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
7 链队列(带头)
实际是同时带有队头指针和队尾指针的单链表
头指针指向头结点
尾指针指向队尾结点
#include<iostream>
using namespace std;
typedef int ElemType;
// 定义链队列结点
typedef struct LinkNode {
ElemType data;
struct LinkNode* next;
}LinkNode;
// 定义链队列结点
typedef struct {
LinkNode* front, * rear; // 队列的队头和队尾指针
}LinkQueue;
void InitQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
bool EnQueue(LinkQueue& Q, ElemType x);
bool DeQueue(LinkQueue& Q, ElemType& x);
bool GetHead(LinkQueue Q, ElemType& x);
// 1 初始化
void InitQueue(LinkQueue& Q) {
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode)); // 建立头结点
Q.front->next = NULL; // 初始为空
}
// 2 判断队空
bool QueueEmpty(LinkQueue Q) {
if (Q.front == Q.rear) return true; // 如果头尾指针在一起(只有判队空不需要取模)
return false;
}
// 3 入队
bool EnQueue(LinkQueue& Q, ElemType x) {
LinkNode* s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = Q.rear->next;
Q.rear->next = s;
Q.rear = s;
return true;
}
bool DeQueue(LinkQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) return false;
LinkNode* q = Q.front->next;
x = q->data;
Q.front->next = q->next;
if (Q.rear == q) {
Q.rear = Q.front;
}
free(q);
return true;
}
bool GetHead(LinkQueue Q, ElemType& x) {
if (QueueEmpty(Q)) return false;
x = Q.front->next->data;
return true;
}
void test() {
LinkQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
EnQueue(Q, i);
}
ElemType x;
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}