数据结构之队列
1.概述
队列是一种操作受限的线性表,它只允许在一端进行元素插入,而在另一端进行元素删除。允许插入的一端,称为队尾,允许删除的一端,称为队头。 在队列的操作中,插入称为入队,删除称为出队。
新来的成员总是加入队尾,排在队列前面的元素总是最先离开队列,由于这种先进先出的特性,让队列又叫先进先出表。
队列可以用顺序存储,也可以用链式存储,前者叫顺序队列,后者叫链队列。
2.顺序队列与链队列
2.1顺序队列定义
#define QueueSize 100
typedef int DataType;
typedef struct { DataType data[QueueSize]; int front,rear;// 记录头和尾
} SeqQueue;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.1.1顺序队列基本运算
// 置空队列
void initQueue(SeqQueue *Q){ Q->front = Q->rear = 0;
}
// 判队空
int queueEmpty(SeqQueue *Q){ return Q->front == Q->rear;
}
// 判队満
int queueFull(SeqQueue *Q){ if(Q->rear > 0){ // 加1的原因请参考后面讲到的循环队列对边界条件的处理 return (Q->rear+1) % QueueSize == 0; }else{ return 0; }
}
// 入队列
void enQueue(SeqQueue *Q,DataType x){ // 插入元素x为队列新的队尾元素 if(queueFull(Q)){ printf("Queue overflow"); }else{ Q->data[Q->rear] = x; Q->rear = Q->rear + 1; }
}
// 出队列
DataType deQueue(SeqQueue *Q){ DataType x; if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ x = Q->data[Q->front]; Q->front = Q->front+1; return x; }
}
// 取队头
DataType GetFront(SeqQueue *Q){ if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ return Q->data[Q->front];// 返回队头元素 }
}
- 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
2.2链队列定义
typedef int DataType;
// 链队列结点类型
typedef struct qnode{ DataType data; struct qnode* next;
} QueueNode;
// 链队列类型
typedef struct{ QueueNode* front;// 队头指针 QueueNode* rear;// 队尾指针
} LinkQueue;
LinkQueue Q;//定义一个链队列Q
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.2.1链队列基本运算
链队列一般是不带头结点的,为了简化边界条件的处理,在队头结点之前添加了一个头结点,并设头结点指向队头结点,下面的运算也是带有头结点的链队列的运算:
// 构造空队列
void initQueue(LinkQueue *Q){ Q->front = (QueueNode *)malloc(sizeof(QueueNode));// 申请头结点 Q->rear = Q->front; Q->rear->next = NULL;
}
// 判队空
int queueEmpty(LinkQueue *Q){ return Q->rear == Q->front;
}
// 入队列
void enQueue(LinkQueue *Q,DataType x){ QueueNode * p = (QueueNode *)malloc(sizeof(QueueNode));// 申请新结点o p->data = x; p->next = NULL; Q->rear->next = p; // p链到原队尾结点之后 Q->rear = p;// 队尾指针指向新的队尾结点
}
// 出队列
DataType deQueue(LinkQueue *Q){ QueueNode *p; if(queueEmpty(Q)){ printf("Queue underflow"); exit(0); }else{ p = Q->front;// p指向头结点 Q->front = Q->front->next;// 头指针指向原队头结点 free(p);// 删除释放原头结点 return (Q->front->data);// 返回原队头结点的数据 }
}
// 取队头元素
DataType getFront(LinkQueue *Q){ if(queueEmpty(Q)){ printf("Queue underflow"); exit(0); }else{ return Q->front->next->data; }
}
- 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
出队列的操作中:
当队列的长度大于1,则出队操作只需要修改头结点的指针域即可,尾指针不变:
s=Q->front->next;
Q->front->next = s->next;
x=s->data;
free(s);
return x;
- 1
- 2
- 3
- 4
- 5
当队列的长度刚好等于1时,则出队操作不仅要修改头结点还要修改尾指针
s=Q->front->next;
Q->front->next = NULL;
Q->rear=Q->front;
x=s->data;
free(s);
return x;
- 1
- 2
- 3
- 4
- 5
- 6
那么为了统一以上两种操作,就有了我们一开始给出的出队操作。
3.顺序循环队列与循环链队列
在循环队列的运算中,要涉及一些边界条件要处理。由于入队时的尾指针Q->rear向前追赶头指针Q->front,出队时头指针向前追赶尾指针,如果尾指针追赶上头指针说明队满,如果头指针追赶上尾指针,说明队空。因此,无论是空还是满,Q->rear==Q->front都成立。由此可见,仅凭队列的头尾指针是否相等是无法判断队空还是队满。解决方法有多种,我们提供可能的三种:
- 另外设立一个标志位,用来区别队空和队满
- 用计数器记录队列中元素的个数
- 少用一个元素空间,约定入队前,测试尾指针在循环意义下加1后,是否等于头指针,如果相等,则认为队满,即尾指针Q->rear所指向的单元始终是空的。
3.1顺序循环队列定义
与顺序队列的定义是一样的。一般情况下,真正实用的顺序队列是循环队列。
#define QueueSize 100
typedef int DataType;
typedef struct { DataType data[QueueSize]; int front,rear;// 记录头和尾
} CirQueue;
- 1
- 2
- 3
- 4
- 5
- 6
3.1.1顺序循环队列基本运算
// 置空队列
void initQueue(CirQueue *Q){ Q->front = Q->rear = 0;
}
// 判队空
int queueEmpty(CirQueue *Q){ return Q->front == Q->rear;
}
// 判队満
int queueFull(CirQueue *Q){ return (Q->rear + 1) % QueueSize == Q->front;
}
// 入队列
void enQueue(CirQueue *Q,DataType x){ // 插入元素x为队列新的队尾元素 if(queueFull(Q)){ printf("Queue overflow"); }else{ Q->data[Q->rear] = x; Q->rear = (Q->rear + 1) % QueueSize;// 这里是循环的重要部分,这里使用数组可以循环使用 }
}
// 出队列
DataType deQueue(CirQueue *Q){ DataType x; if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ x = Q->data[Q->front]; Q->front = (Q->front+1) % QueueSize;//只有这样才能让头指针回到开始的地方 return x; }
}
// 取队头
DataType GetFront(CirQueue *Q){ if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ return Q->data[Q->front];// 返回队头元素 }
}
- 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
3.2循环链队列定义
与链队列的定义是一样的。
typedef int DataType;
typedef struct qnode{ DataType data; struct qnode * next;
} QueueNode;
typedef struct { QueueNode * front; QueueNode * rear;
} CirLinkQueue;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
3.2.1循环链队列基本运算
// 初始化队列
void initQueue( CirLinkQueue * Q){ Q->front=Q->rear = (QueueNode *)malloc(sizeof(QueueNode)); Q->front->next = Q->front;
}
// 判队空
int queueEmpty(CirLinkQueue *Q){ return Q->front->next == Q->front;
}
// 入队列
// 在队列中插入一个结点是在队尾进行的。过程:
// 1、首先生成一个新结点s,因为链表带头结点,所有队空与否对插入没有影响;
// 2、将尾指针域值赋给新结点的指针域;
// 3、同时将新结点指针赋给尾的指针域
// 4、最后,移动尾指针指向最后一个结点,其实就是将新结点指针赋给尾指针
//
void enQueue(CirLinkQueue *Q,DataType x){ // 插入元素x为队列新的队尾元素 QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode)); p->data = x; p->next = Q->rear->next; Q->rear->next = p; Q->rear = p;
}
// 出队列
DataType deQueue(CirLinkQueue *Q){ DataType x; if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ x = Q->front->next->data; Q->front->next = Q->front->next->next; return x; }
}
// 取队头
DataType GetFront(CirLinkQueue *Q){ if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ return Q->front->next->data;// 返回队头元素 }
}
// 队列长度
int queueLength(CirLinkQueue *Q){ int count; QueueNode *p = Q->front; while(p != Q->rear){ ++count; p=p->next; } return count;
}
- 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
以上就是队列相关的内容,谢谢!
文章来源: blog.csdn.net,作者:WongKyunban,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/weixin_40763897/article/details/105404841
- 点赞
- 收藏
- 关注作者
评论(0)