队列
概念
只允许在一端进行插入数据的操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)。
入队列:进行插入操作的一端称为队尾。
出队列:进行删除操作的一端称为队头。
结构
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队 列在数组头上出数据,效率会比较低。
队列基本操作
定义队列结构
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
int size;//保存队列有效数据个数
}Queue;
初始化队列
void QueueInit(Queue* pq);
销毁队列
void QueueDestroy(Queue* pq);
入队列,队尾
void QueuePush(Queue* pq, QDataType x);
出队列,队头
void QueuePop(Queue* pq);
取队头元素
QDataType QueueFront(Queue* pq);
取队尾元素
QDataType QueueBack(Queue* pq);
队列判空
bool QueueEmpty(Queue* pq);
队列有效元素个数
int QueueSize(Queue* pq);
完整代码
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义队列结构
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
int size;//保存队列有效数据个数
}Queue;
void QueueInit(Queue* pq);
// ⼊队列,队尾
void QueuePush(Queue* pq, QDataType x);
// 出队列,队头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
Queue.c
#include"Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
// ⼊队列,队尾
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//申请新结点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
//队列不为空
pq->ptail->next = newnode;
pq->ptail = newnode;//pq->ptail->next
}
pq->size++;
}
//队列判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL && pq->ptail == NULL;
}
// 出队列,队头
void QueuePop(Queue* pq)
{
assert(pq);
assert(QueueEmpty(pq));
//只有一个结点的情况,避免ptail成为野指针
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
//删除队头元素(多个结点的情况)
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
--pq->size;
}
//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
int size = 0;
QueueNode* pcur = pq->phead;
/*while (pcur)
{
size++;
pcur = pcur->next;
}
return size;*/
return pq->size;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
test.c
#include"Queue.h"
void QueueTest01()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
/*QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
*/
/*printf("head:%d\n", QueueFront(&q));
printf("tail:%d\n", QueueBack(&q));*/
/*printf("size :%d\n", QueueBack(&q));
QueueDestroy(&q);*/
}
int main()
{
QueueTest01();
return 0;
}
练习题
习题1
解析:
选项B中,一个栈模拟入队列,一个栈模拟出队列,出队列时直接弹出模拟出队列栈的栈顶元素,当该栈为空时,将模拟入队列栈中所有元素导入即可,不是每次都需要导入元素,故错误
选项A中,栈和队列的特性是相反的,一个栈实现不了队列
选项C中,一个栈模拟入队列,一个栈模拟出队列,入队列时,将元素直接往模拟入队列的栈中存放
选项D中,入队列就是将元素放到栈中,因此时间复杂度就是O(1)
习题2
解析:
答案:C ;出队操作,一定会影响头指针,如果出队之后,队列为空,会影响尾指针。
习题3
解析:
答案:B ; 队列只能从队头删除元素
习题4
解析:
A错误:栈是尾部插入和删除,一般使用顺序表实现,队列是头部删除尾部插入,一般使用链表实现
B错误:栈是后进先出,尾部插入和删除;队列是先进先出,尾部插入头部删除
C正确:栈只能访问栈顶元素,不支持随机访问,队列也不支持
D正确:栈和队列的特性
故错误的是A和B