队列
2020-04-16 本文已影响0人
只写Bug程序猿
定义
队列是一种特殊的线性表,其插入和删除操作分别在线性表的两端进行,插入称为入队(enqueue),删除称为出兑(dequeue),允许入队的一端称为队尾(rear),允许出队的一端称为队头(front);
假溢出问题
首先初始化一个空队列,然后c1,c2,c3,c4,c5,c6入队,然后c1,c2,c3,c4相继出队,这就造成了队列已满的假象,其实0-3位置是空的.
为了解决这个问题,我们一般采用循环队列的方法,
循环队列
image.png
我们判空的条件是Q->rear == Q->front,那么循环队列会出现在队满的情况下Q->rear == Q->front,这就造成了无法判空的问题,那么为了解决这个问题,我们可以牺牲一个存储单元,当存储数据数量等于队列最大长度-1的情况下我们就认为已经满了无法在进行入队操作
image.png
所以:
- 判断队空: Q.front = Q.rear
- 判断队满: (Q.rear+1)%maxSize = Q.front
队列同栈一样也分为顺序存储,链式存储
顺序队列
定义
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定,这里假设为int */
typedef struct {
QElemType data[MAXSIZE];
int front; //头
int rear; //尾
}SQueue;
初始化空队列
Status initQueue(SQueue *Q){
Q->front = 0;
Q->rear = 0;
return OK;
}
清空队列
Status clearQueue(SQueue *Q){
Q->front = 0;
Q->rear = 0;
return OK;
}
队列判空
Status queueEmpty(SQueue Q){
return Q.front == Q.rear ? TRUE : FALSE;
}
队列长度
int queueLength(SQueue Q){
return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}
队列入队
Status enQueue(SQueue *Q,QElemType e){
//如果队满直接返回error
if ((Q->rear + 1) % MAXSIZE == Q->front) {
return ERROR;
}
Q->data[Q->rear] = e;
//将队尾往后移
Q->rear = (Q->rear + 1)%MAXSIZE;
return OK;
}
队列出队
Status deQueue(SQueue *Q,QElemType *e){
//如果为空直接返回error
if (Q->rear == Q->front) {
return ERROR;
}
*e = Q->data[Q->front];
//将队头往后移
Q->front = (Q->front + 1)%MAXSIZE;
return OK;
}
队列遍历
Status queueTravel(SQueue Q){
int i = Q.front;
while (i != Q.rear) {
printf("%d \n",Q.data[i]);
i = (i+1)%MAXSIZE;
}
return OK;
}
函数调用
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
QElemType e;
SQueue Q;
initQueue(&Q);
for (int i = 0; i < 11; i++) {
enQueue(&Q, i+1);
}
queueTravel(Q);
printf("队列长度%d\n",queueLength(Q));
printf("队列是否为空%d\n",queueEmpty(Q));
deQueue(&Q, &e);
deQueue(&Q, &e);
queueTravel(Q);
printf("队列长度%d\n",queueLength(Q));
return 0;
}
链式队列
定义
//这里的队列都是带有头结点的,
typedef struct QueueNode{
QElemType data;
struct QueueNode *next;
}QueueNode;
typedef QueueNode * QueuePtr;
typedef struct {
QueueNode *front;
QueueNode *rear;
}LinkQueue;
初始化空队列
Status initQueue(LinkQueue *Q){
Q->front = malloc(sizeof(QueueNode));
Q->rear = Q->front;
//如果没开辟成功返回error
if (Q->front == NULL) {
return ERROR;
}
//将front和rear设置为null
Q->front->next = NULL;
return OK;
}
队列的销毁与清空
Status destoryQueue(LinkQueue *Q){
QueuePtr temp;
while (Q->front) {
temp = Q->front->next;
free(Q->front);
Q->front = temp;
}
return OK;
}
Status clearQueue(LinkQueue *Q){
QueuePtr p,q;
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
while (p) {
q = p;
p = p->next;
free(q);
}
return OK;
}
队列的判空
Status queueEmpty(LinkQueue *Q){
return Q->front == Q->rear;
}
获取队列长度
int queueLength(LinkQueue Q){
int count = 0;
QueuePtr p;
p = Q.front;
while (p != Q.rear) {
count ++;
p = p->next;
}
return count;
}
队列入队
Status enQueue(LinkQueue *Q,QElemType e){
QueuePtr temp = malloc(sizeof(QueueNode));
if (!temp) return ERROR;
temp->data = e;
temp->next = NULL;
//将temp加入队列
Q->rear->next = temp;
//将rear后移
Q->rear = temp;
return OK;
}
队列出队
Status deQueue(LinkQueue *Q,QElemType *e){
if (Q->front == Q->rear) return ERROR;
QueuePtr temp = Q->front->next;
*e = temp->data;
//将front后移
Q->front->next = temp->next;
//若队头就是队尾,则删除后将rear指向头结点.
if (temp == Q->rear) {
Q->rear = temp;
}
free(temp);
return OK;
}
队列遍历
Status queueTravel(LinkQueue Q){
QueuePtr p;
p = Q.front->next;
while (p) {
printf("%d\n",p->data);
p = p->next;
}
return OK;
}
调用
int main(int argc, const char * argv[]) {
// insert code here...
LinkQueue Q;
QElemType e;
initQueue(&Q);
enQueue(&Q, 1);
enQueue(&Q, 2);
enQueue(&Q, 3);
enQueue(&Q, 5);
queueTravel(Q);
deQueue(&Q, &e);
queueTravel(Q);
return 0;
}