29 线性表 · 队列

目录

一、概念与结构

（一）概念

1、队列

2、入队列

3、出队列

（二）底层结构

二、队列的实现

三、队列的算法题

（一）用队列实现栈

（二）用栈实现队列

（三）设计循环队列

1、循环队列的概念与结构

2、题目 

一、概念与结构

（一）概念

1、队列

        只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的原则。

2、入队列

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

3、出队列

        进行删除操作的一端称为队头。

（二）底层结构

        可以使用数组或者单链表实现队列。

        数组：在队尾使用尾插方便，时间复杂度为O（1），但是队头出数据后，所有数据都要向前移动一位，最差的情况下时间复杂度为O（N）。

        单链表： 以头节点为队头，出数据的时间复杂度为O（1），而在链表插入数据，则要先循环找到最后一个节点，时间复杂度为O（N）。可以改进：设置头指针与尾指针，这样出数据与入数据的时间复杂度均为O（1）。

        综上所述，底层使用多设置一个尾指针的单链表更好。

二、队列的实现

        队列的常用名：Queue。

队列的编写：

① 头文件：定义队列的结构体，声明要提供的操作（起到目录作用）。

② cpp文件：编写具体实现各种操作（起到内容作用）。

③ 测试文件：测试是否可以正常运行。

Queue.h

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<iostream>
#include<stdbool.h>
using namespace std;

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;//储存队列的有效数据
};

//一、初始化队列,判断是否为空,取有效元素个数,销毁队列
//（一）初始化队列
void QueueInit(Queue& q);
//（二）判断是否为空
bool QueueEmpty(Queue& q);
//（三）取有效元素个数
int QueueSize(Queue q);
//（四）销毁队列
void QueueDestroy(Queue& q);

//二、队尾入数据，队头出数据
//（一）队尾入数据
void QueuePush(Queue& q, QDataType num);
//（二）队头出数据
void QueuePop(Queue& q);

//三、取队头、队尾数据
//（一）取队头数据
QDataType QueueGetHead(Queue& q);
//（二）取队尾数据
QDataType QueueGetTail(Queue& q);

Queue.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

//一、初始化队列,判断是否为空,取有效元素个数,销毁队列
//（一）初始化队列
void QueueInit(Queue& q)
{
	q.phead = q.ptail = nullptr;
	q.size = 0;
}
//（二）判断是否为空
bool QueueEmpty(Queue& q)
{
	return q.phead == nullptr && q.ptail == nullptr;
}
//（三）取有效元素个数
int QueueSize(Queue q)
{
	return q.size;
}
//（四）销毁队列
void QueueDestroy(Queue& q)
{
	assert(!QueueEmpty(q));
	QueueNode* pcur = q.phead;
	while (pcur)
	{
		QueueNode* next_node = pcur->next;
		free(pcur);
		pcur = next_node;
	}
	q.phead = q.ptail = nullptr;
	q.size = 0;
}

//二、队尾入数据，队头出数据
//（一）队尾入数据
void QueuePush(Queue& q, QDataType num)
{
	//创建队列节点
	QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
	if (new_node == nullptr)
	{
		perror("QueuePush malloc fail!");
		exit(1);
	}
	new_node->data = num;
	new_node->next = nullptr;

	//插入队尾，尾插有两种情况：头节点为空与不为空
	if (q.phead == nullptr && q.ptail == nullptr)
		q.phead = q.ptail = new_node;
	else
	{
		q.ptail->next = new_node;
		q.ptail = new_node;
	}
	q.size++;
}
//（二）队头出数据
void QueuePop(Queue& q)
{
	assert(!QueueEmpty(q));
	//需要考虑队列中只有一个节点的情况和多个节点的情况
	if (q.phead == q.ptail)
	{
		free(q.phead);
		q.phead = q.ptail = nullptr;
	}
	else
	{
		QueueNode* next_node = q.phead->next;
		free(q.phead);
		q.phead = next_node;
	}
	q.size--;
}

//三、取队头、队尾数据
//（一）取队头数据
QDataType QueueGetHead(Queue& q)
{
	assert(!QueueEmpty(q));
	return q.phead->data;
}
//（二）取队尾数据
QDataType QueueGetTail(Queue& q)
{
	assert(!QueueEmpty(q));
	return q.ptail->data;
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

void QueueTest01()
{
	Queue q;
	QueueInit(q);

	for (int i = 1; i < 11; i++)
	{
		QueuePush(q, i);
	}

	/*for (int i = 1; i < 11; i++)
	{
		QueuePop(q);
	}*/
	cout << "QueueSize: " << QueueSize(q) << endl;

	QueueDestroy(q);
	cout << "QueueSize: " << QueueSize(q) << endl;
}

int main()
{
	QueueTest01();
	return 0;
}

        注意：

                与栈一样，不能通过下标进行随机访问其中的数据，所以不能被遍历。

三、队列的算法题

（一）用队列实现栈

        题目链接如下：

                https://leetcode.cn/problems/implement-stack-using-queues/description/

        解题思路：

                假设队列Q1中有三个数据：

                ① 把队列Q1的前两个数据出队列，插入到Q2队列中，再单独拿出Q1队列的最后一个数据，相当于栈的最后一个元素先出；

                ② 把队列Q2的第一个元素出队列，插入到Q1队列中，再单独拿出Q2队列的最后一个数据，相当于栈的倒数第二个元素出栈。

                ③ 再把队列不为空的Q1出队列。

        总结：

                出栈思路 ：找不为空的队列，将size-1个数据导入到另一个队列中。

                入栈思路：往不为空队列中插入数据。

                取栈顶元素： 与出栈操作的区别就是不需要将栈顶元素出栈，直接返回即可；但这样会导致队列中最后一个元素不出栈，让两个队列都不为空，这样不行。解决：找不为空的队列，取队尾。（必须保证至少一个队列为空）

        答案代码如下：

//定义队列结构
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)
{
	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;

	//ptail newnode
	if (pq->phead == NULL)
	{//队列为空
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		//队列不为空
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;//newnode
	}
	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->ptail == pq->phead)
	{
		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;
}

//两个队列实现一个栈
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

//初始化
MyStack* myStackCreate() {
    MyStack* obj= (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);

    return obj;
}

//入栈
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
        QueuePush(&obj->q1, x);
    else
        QueuePush(&obj->q2, x);
}

//出栈
int myStackPop(MyStack* obj) {
    //找不为空的队列
    Queue* empQ = &obj->q1;//队列为空的指针
    Queue* noneQ = &obj->q2;//队列不为空的指针
    if(!QueueEmpty(&obj->q1))
    {
        empQ = &obj->q2;
        noneQ = &obj->q1;
    }

    //将size-1个数据插入到另一个队列中
    while(QueueSize(noneQ) > 1)
    {
        QDataType Front = QueueFront(noneQ);
        QueuePush(empQ, Front);
        QueuePop(noneQ);
    }

    //记录返回队头元素，然后出队队头元素
    QDataType re = QueueFront(noneQ);
    QueuePop(noneQ);
    return re;
}

//取栈顶元素
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);
    obj = NULL;
}

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

（二）用栈实现队列

        题目链接如下：

                https://leetcode.cn/problems/implement-queue-using-stacks/description/

        解题思路：        

                ① 入队：往pushST中插入数据

                ② 出队：判断popST是否为空或，不为空直接pop；为空则将pushST导入到popST中再pop。

                ③ 跟出队一样，但是步pop数据

        注意点：

                必须保证至少一个队列为空。

        答案代码如下：

typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int capacity;     //栈的空间大小
	int top;          //栈顶
}ST;

//栈的初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

//销毁栈
void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	
	//1.判断空间是否足够
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	--ps->top;
}

//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

typedef struct {
    ST pushST;
    ST popST;
} MyQueue;

//初始化队列
MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushST);
    STInit(&obj->popST);

    return obj;
}

//插入数据
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST, x);
}

//删除数据
int myQueuePop(MyQueue* obj) {
    //popST有数据则直接删，若没有则从pushST中导入数据再删
    //① 导数据
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }

    //② 删
    STDataType re = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return re;
}

//取队头元素
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->popST) && StackEmpty(&obj->pushST);
}

//销毁队列
void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->popST);
    STDestroy(&obj->pushST);
    free(obj);
    obj = NULL;
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

（三）设计循环队列

1、循环队列的概念与结构

                ① 概念：有一种特殊的队列叫环形队列，环形队列首位相连成环，环形队列可以使用数组或者链表进行实现。

                ② 结构：如下所示：

2、题目 

        题目链接如下：

                https://leetcode.cn/problems/design-circular-queue/description/

        解题思路：

                ① 循环队列更推荐使用数组，因为若是使用单链表来实现要申请多个空间并且有指针的消耗。链表的节点还要多设置一个状态属性来标明该节点是否为空以判断能否插入，这样会很麻烦。

                ② front == rear 既可以判断空间为满和空间为空，怎么区分？多申请一块空间。假设能存放数据的空间大小为4（k = 4），申请5块空间，当 (rear + 1) % (k + 1) == front 则空间已满（5%5 = 0），这里取余是为了rear到了最后一个元素的时候 + 1 会超出申请空间的个数，取余可以解决这个问题，让超出的位置循环回到数组对应的位置。所以用 rear == front 判断为空。        

        注意点：

                ① 循环队列空间固定。

                ② 循环队列满了，就不能插入数据。

         答案代码如下：

//定义循环队列的结构
typedef struct {
    int* arr;
    int front;//头下标
    int rear;//尾下标
    int capecity;//数组最大元素个数

} MyCircularQueue;

//初始化空间大小 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = obj->rear = 0;
    obj->capecity = k;

    return obj;
}

//判断队列是否满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1)%(obj->capecity + 1) == obj->front; 
}

//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //需要先判断空间是否已经满了 
    if(myCircularQueueIsFull(obj))
        return false;
    else
    {
        obj->arr[obj->rear++] = value;
        obj->rear %= obj->capecity + 1;
        return true;
    }
}

//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->rear == obj->front;
}

//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    else
    {
        obj->front++;
        obj->front %= obj->capecity + 1;
        return true;
    }
}

//取队首元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->arr[obj->front];
}

//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
    {
        int pre = obj->rear - 1;
        if(obj->rear == 0)
            pre = obj->capecity;
        return obj->arr[pre];
    }
}

//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    obj->arr = NULL;
    free(obj);
    obj = NULL;
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

        以上内容仅供分享，若有错误，请多指正。