1.队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表
2.队列是一种先进先出(First In Fist Out)的线性表,简称FIFO。允许插入的一端为队尾,允许删除的一端为队头。
Q1:假设长度为5的队列中此时情况如下: 问题
即入队时已经越界,而前面还有诸多空间未利用,故使用循环队列,入队元素存入未利用的空间,即下图所示
解决
Q2:我们发现队空时,front==end,队满时也是front==end,如下图所示:
问题
解决办法1:设置标志量flag,
解决办法2:保留一个元素空间,即使得队列中最多存储MAXSIZE-1个元素,这样,队满条件变为(rear+1)%MAXSIZE==front,与队空条件不会冲突,如下图所示
解决
queue.h
#pragma once
#define MAXSIZE 10
// 函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型,其值是函数结果状态代码
typedef int Status;
//数据类型
typedef int QElemType;
//顺序队列定义
typedef struct
{
QElemType* base; //初始化的动态分配存储空间
int front; //头指针
int rear; //尾指针
}SqQueue;
//初始化队列
Status InitSqQueue(SqQueue& Q);
//求队列长度
int QueueLength(SqQueue Q);
//入队
Status EnQueue(SqQueue& Q, QElemType e);
//出队
Status DeQueue(SqQueue& Q, QElemType& e);
//取队头元素
QElemType GetHead(SqQueue Q);
queue.cpp
#include "queue.h"
#include <iostream>
using namespace std;
//初始化队列
Status InitSqQueue(SqQueue& Q)
{
Q.base = new QElemType[MAXSIZE];
if (!Q.base)
{
exit(OVERFLOW);
}
Q.front = Q.rear = 0;
}
//求队列长度
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
//入队
Status EnQueue(SqQueue& Q, QElemType e)
{
if ((Q.rear + 1) % MAXSIZE == Q.front)
{
cout << "队满" << endl;
return ERROR;
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXSIZE;
}
//出队
Status DeQueue(SqQueue& Q, QElemType& e)
{
if (Q.front == Q.rear)
{
cout << "队空" << endl;
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXSIZE;
}
//取队头元素
QElemType GetHead(SqQueue Q)
{
if (Q.front == Q.rear)
{
cout << "队空" << endl;
return ERROR;
}
return Q.base[Q.front];
}
main.cpp
#include <iostream>
#include "queue.h"
using namespace std;
int main(int argc, char** argv)
{
SqQueue Q;
InitSqQueue(Q);
for (int i = 0; i < MAXSIZE + 1; i++) //MAXSIZE为10,只能存9个,会有队满情况发生
{
EnQueue(Q, i);
}
QElemType h = GetHead(Q);
cout << "队头元素:" << h << endl;
int length = QueueLength(Q);
cout << "队列长度:" << length << endl;
QElemType x;
for (int i = 0; i < MAXSIZE + 2; i++) //存了9个,会有队空情况发生
{
DeQueue(Q, x);
cout << x << endl;
}
return 0;
}
网友评论