网络知识 娱乐 【数据结构】队列

【数据结构】队列

文章目录

    • 队列的概念及结构
    • 队列的实现
        • 1.队列的结构
        • 2.初始化
        • 3.销毁
        • 4.入队
        • 5.判断是否为空
        • 6.出队
        • 7.队头元素
        • 8.队尾元素
        • 9.元素个数
    • 完整代码
        • Queue.h
        • Queue.c
        • test.c
    • 队列OJ题
        • 用队列实现栈
        • 一个队列实现栈
        • 用栈实现队列
        • 设计循环队列

队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

image-20220804162855428

队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低

image-20220804170034552

话不多说,我们直接来实现队列:(一定要记得自己去实现一个队列)

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)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 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个导入到空的队列,此时取出剩下的元素就是符合栈顺序的元素,我们不妨来画个图:

image-20220805154451427

取出4之后,q1又变成了空队列。继续倒

image-20220805154814863

这道题的思路不难,但是实现起来比较麻烦,可能做的时候多多少少有有一些细节没注意到,导致编译出现错误,不过问题不是很大。话不多说直接搬上我们的代码:

#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);
*/

image-20220805160953150

一个队列实现栈

image-20220806133528269

还是上面那道题,我们用一个队列来试一试:

#include 
#include