文章目录
- 队列的概念及结构
- 队列的实现
- 1.队列的结构
- 2.初始化
- 3.销毁
- 4.入队
- 5.判断是否为空
- 6.出队
- 7.队头元素
- 8.队尾元素
- 9.元素个数
- 完整代码
- Queue.h
- Queue.c
- test.c
- 队列OJ题
- 用队列实现栈
- 一个队列实现栈
- 用栈实现队列
- 设计循环队列
队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
队列的实现
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低
话不多说,我们直接来实现队列:(一定要记得自己去实现一个队列)
1.队列的结构
队列的初始化是比较简单的:由单链表构成,一个结构体为队列的结点,但是只有一个指针,我们需要队头和队尾,方便队头删除,队尾插入(所以不需要前面那些什么头删、尾删,队列中队头是用来删除的,队尾是用来插入的)所以另一个结构体为队列的头、尾指针
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
在这个地方,这里有两个结构体哦,我们不需要二级指针:
我们只需要改结构体(只需要改变结构体里面的head和tail),我们只需要结构体的指针(一级指针)即可
2.初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
3.销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
}
4.入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
5.判断是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
6.出队
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
7.队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
8.队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
9.元素个数
QDataType QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
/*int n = 0;
while (cur)
{
++n;
cur = cur->next;
}
return n;*/
return pq->size;
}
完整代码
Queue.h
#pragma once
#include
#include
#include
#include
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
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);
QDataType QueueSize(Queue* pq);
Queue.c
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
QDataType QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
/*int n = 0;
while (cur)
{
++n;
cur = cur->next;
}
return n;*/
return pq->size;
}
test.c
//test.c部分这里只是对上面的部分函数进行测试,如果有需要的话也可以自己设计成菜单界面
#include "Queue.h"
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("n");
QueueDestroy(&q);
}
int main()
{
TestQueue();
return 0;
}
对于队列的实现并不难,下面,我们就来做几道有关队列的OJ题目把👇
队列OJ题
用队列实现栈
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(
push
、top
、pop
和empty
)。实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。注意:
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
题目的意思其实很简单:就是让你用两个队列去模拟实现一个栈
思路:思路其实很简单,我们知道队列是先进先出,而栈是后进先出,两个最大的不同在于顺序:
我们假设在队列入了1,2,3,4那么现在要在队列中出一个元素,那就是1
如果在栈中入了1,2,3,4那么现在要在栈中出一个元素,那就是4
我们该怎么改变这种顺序呢?很简单,让有元素队列把前n-1个导入到空的队列,此时取出剩下的元素就是符合栈顺序的元素,我们不妨来画个图:
取出4之后,q1又变成了空队列。继续倒
这道题的思路不难,但是实现起来比较麻烦,可能做的时候多多少少有有一些细节没注意到,导致编译出现错误,不过问题不是很大。话不多说直接搬上我们的代码:
#include
#include
#include
//直接手撸一个队列
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode*next;
}QNode;
typedef struct Queue{
QNode*head;
QNode*tail;
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);
QDataType QueueSize(Queue*pq);
void QueueInit(Queue*pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue*pq)
{
assert(pq);
QNode*cur = pq->head;
while(cur)
{
QNode*del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue*pq,QDataType x)
{
assert(pq);
QNode*newnode = (QNode*)malloc(sizeof(QNode));
if(NULL == newnode)
{
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if(pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue*pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if(pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode*del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
QDataType QueueFront(Queue*pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue*pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
bool QueueEmpty(Queue*pq)
{
assert(pq);
return pq->head == NULL&&pq->tail == NULL;
}
QDataType QueueSize(Queue*pq)
{
return pq->size;
}
//定义了两个队列,一个为q1,另一个为q2
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack*obj = (MyStack*)malloc(sizeof(MyStack));
if(NULL == obj)
{
exit(-1);
}
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
//看哪个是否为空
if(!QueueEmpty(&obj->q1))
{
//谁不为空就插入数据
QueuePush(&obj->q1,x);
}
//q2可能为空或不为空
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
//删除栈顶的元素,先找出那个不为空的队列,在把数据导入
Queue*empty = &obj->q1;
Queue*nonEmpty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
nonEmpty = &obj->q1;
}
//剩下一个元素
while(QueueSize(nonEmpty)>1)
{
//取队头数据存放到空的队列,最后剩下一个,这个就是栈顶的元素
QueuePush(empty,QueueFront(nonEmpty));
QueuePop(nonEmpty);
}
int top = QueueFront(nonEmpty);
QueuePop(nonEmpty);
return top;
}
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);
}
/**
* Your MyStack struct will be instantiated and called as such:
* MyStack* obj = myStackCreate();
* myStackPush(obj, x);
* int param_2 = myStackPop(obj);
* int param_3 = myStackTop(obj);
* bool param_4 = myStackEmpty(obj);
* myStackFree(obj);
*/
一个队列实现栈
还是上面那道题,我们用一个队列来试一试:
#include
#include