文章目录
- 1.队列的概念
- 2.队列的设计
- 3.队列的实现
-
- 3.1初始化
- 3.2销毁
- 3.3入队列
- 3.4出队列
- 3.5获取队头元素
- 3.6获取队尾元素
- 3.7队中元素个数
- 3.8检测队是否为空
- 4.相关题目
-
- 4.1用队列实现栈
- 4.2用栈实现队列
1.队列的概念
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
- 入队列:进行插入操作的一端称为队尾
- 出队列:进行删除操作的一端称为队头
2.队列的设计
- 队列也可以数组和链表的结构实现,使用链表的结构实现更优一些。因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低,时间复杂度为O(n)。
- 若单独使用链表,那在队尾插入数据时,由于需要找队尾,复杂度也为O(n)。所以我们干脆定义两个指针,指针指向链表的头尾,在对队列进行操作时,仅操作这两个指针即可。
- 在求队列的长度时,我们能否直接用尾指针 – 头指针呢?
很明显是不可以的,因为我们的队列使用的是链表实现,链表中的每一个节点都是在堆上申请的,不一定连续。所以不能直接使用两个指针相减。因此我们直接在队列中设计一个变量size直接记录当前队列中元素的个数。
//链表的节点
typedef int QueueDataType;
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QNode;
//队列
typedef struct Queue
{
QNode* head;//指向队头的指针
QNode* tail;//指向队尾的指针
int size; //记录当前队中元素的个数
}Queue;
3.队列的实现
3.1初始化
最开始时,队头指针与队尾指针均指向空,队列中没有元素。
//初始化
void QueueInit(Queue* q)
{
assert(q);
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
3.2销毁
//销毁
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->head; //cur应该为节点类型,而不是队列
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
3.3入队列
入队列非常简单,只需向队尾后插入数据,然后队尾后移,队列元素个数加一。
- 若是第一次入队,队尾与队头均指向入队节点
- 不是第一次入队,直接向队尾插入
//入队列
void QueuePush(Queue* q, QNodeDataType x)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
//若是第一次入队
if (q->head == NULL)
{
q->head = q->tail = newnode;
}
else
{
//不是第一次
q->tail->next = newnode;
q->tail = q->tail->next;
}
q->size++;//队列元素个数加一
}
3.4出队列
出队列有几个需要注意的地方:
- 队列不能为空
- 只有一个元素时,队头元素出队列后,队头、队尾指针置空
- 多个元素,队头元素出队列后,队头后移
//出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->head);//队不能为空
//只有一个节点
if (q->head->next == NULL)
{
free(q->head);
q->head = q->tail = NULL;
}
else
{
//多个节点
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
q->size--;
}
3.5获取队头元素
//获取队头元素
QNodeDataType QueueFront(Queue* q)
{
assert(q);
assert(q->head);//队列不为空
return q->head->data;
}
3.6获取队尾元素
QNodeDataType QueueBack(Queue* q)
{
assert(q);
assert(q->tail);
return q->tail->data;
}
3.7队中元素个数
//队中元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
3.8检测队是否为空
//队是否为空
bool QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
4.相关题目
4.1用队列实现栈
本题的解题思路是这样的:
- 让一个队列为空,一个队列存数据
- 入栈时,向不为空的队列中入数据
- 出栈时
- 将不为空队列中的n-1个数据入到另一个为空的队列中
- 然后再将该队列第n个数据出队
这样我们就利用两个队列来回的导数据实现了栈的效果。
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* ps = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&ps->q1);
QueueInit(&ps->q2);
return ps;
}
void myStackPush(MyStack* obj, int x) {
//哪个不为空就往哪个里面入
if(QueueEmpty(&obj->q1))
{
QueuePush(&obj->q2,x);
}
else
{
QueuePush(&obj->q1,x);
}
}
int myStackPop(MyStack* obj) {
Queue* emptyQueue = &obj->q1;
Queue* NonEmptyQueue = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
NonEmptyQueue = &obj->q1;
emptyQueue = &obj->q2;
}
//将n-1个到入空队列
while(QueueSize(NonEmptyQueue) > 1)
{
//非空队列出
QNodeDataType front = QueueFront(NonEmptyQueue);
QueuePop(NonEmptyQueue);
//向空队列中入
QueuePush(emptyQueue,front);
}
//第n个数据出队列(出栈)
int front = QueueFront(NonEmptyQueue);
QueuePop(NonEmptyQueue);
return front;
}
//取栈顶数据==取队尾数据
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
//两个队列都为空,栈才为空
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
4.2用栈实现队列
解题思路:
将一个栈当作输入栈,用于压入传入的数据;另一个栈当作输出栈,用于pop 和 peek 操作。
每次 pop 或 peek时,只有输出栈为空才将输入栈的全部数据依次弹出并压入输出栈,这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
typedef struct {
Stack input;
Stack output;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&pq->input);
StackInit(&pq->output);
return pq;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->input,x);
}
int myQueuePop(MyQueue* obj) {
//输出栈为空,倒数据
if(StackEmpty(&obj->output))
{
while(!StackEmpty(&obj->input))
{
int top = StackTop(&obj->input);
StackPop(&obj->input);
StackPush(&obj->output,top);
}
}
//输出栈不为空,直接出栈顶数据
int front = StackTop(&obj->output);
StackPop(&obj->output);
return front;
}
int myQueuePeek(MyQueue* obj) {
//输出栈为空,倒数据
if(StackEmpty(&obj->output))
{
while(!StackEmpty(&obj->input))
{
int top = StackTop(&obj->input);
StackPop(&obj->input);
StackPush(&obj->output,top);
}
}
return StackTop(&obj->output);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->input) && StackEmpty(&obj->output);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->input);
StackDestroy(&obj->output);
free(obj);
}
版权声明:本文为博主作者:戴墨镜的恐龙原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/weixin_69380220/article/details/136377271