队列实现及leetcode相关OJ题

上一篇写的是栈这一篇分享队列实现及其与队列相关OJ题


文章目录

  • 一、队列概念及实现
  • 二、队列源码
  • 三、leetcode相关OJ


一、队列概念及实现

1、队列概念

队列同栈一样也是一种特殊的数据结构,遵循先进先出的原则,例如:想象在独木桥上走着的人,先上去的人定是先从独木桥上下来,为啥说是特殊呢?因为它只允许在对尾插入数据 (简称入队然后在对头删除数据(简称出队),只允许在这两端进行插入和删除操作

而基于它的特性选择链表实现还是数组实现更好呢?

当然选链表实现比较好,因为数组在头删除时需要移动大量的数据,时间复杂度为O(N),而用链表头删时间复杂度为O(1),那么有人会说那链表的尾插时间复杂度不也是O(N)吗,因为每次都要找尾节点

其实可以创建两个指针,一个指向对头,一个指向队尾,这样就不用每次都找尾了,时间复杂度也是O(1)。由于是多个数据,选择用结构体将其封装起来,而我们在链表每次访问长度的时候时间复杂度都为O(N),因此再在这个队列结构体中定义一个size表示队列大小

队列结构定义

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

队列中的元素是每个节点,而每个节点又有多个数据存放下一个节点地址的next,存放每个节点数据的data,相当于队列里面它的成员又是一个结构体然后还有表示队列大小的size

typedef struct Queue
{
	//Queue结构体中成员又包含结构体
	QNode* head;//头指针指向头节点
	QNode* tail;//尾指针指向尾节点
	int size;//队列中节点的个数
}Queue;

队列实现

队列初始化

void QInit(Queue* pq)
{
// 传过来的时候就怕传一个空地址过来,那么队列都没有还怎么对其操作
	assert(pq);
	pq->head = pq->tail = NULL;//
	pq->size = 0;
}

队列销毁

void QDestroy(Queue* pq)
{
	assert(pq);
	assert(pq->head!=NULL);//对都为空那么就不用再释放了
	
	while (pq->head)
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

入队

void QPush(Queue* pq, QDataType x)
{
	assert(pq);
	//先创建一个队列里面元素的节点,
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
    //如果队列为空时,那么就直接将节点插入进来即可
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
    
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
    //入队之后队列长度就要增一
	pq->size++;
}

出队

void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//队列不空才出队

	//队列中只有一个元素的时候,这时也就是对头指针和队尾指针指向同一个节点
	if (pq->tail == pq->head)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	
	//找到头节点的下一个节点
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	
	//出队之后队列长度会减一
	pq->size--;
}

判空

bool QEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;//直接返回对头指针,对头指针为空的话队列即为空
}

取对头元素

QDataType QFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

取队尾元素

QDataType QTail(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

获取队列长度

int QSize(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	//由于size直接获得队列大小,因此直接返回size即可
	return pq->size;
}

二、队列源码

Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

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


typedef struct Queue
{
	//Queue结构体中成员又包含结构体
	QNode* head;//头指针
	QNode* tail;
	int size;//队列中节点的个数
}Queue;
//初始化
void QInit(Queue* pq);
//销毁队列
void QDestroy(Queue* pq);
//入队
void QPush(Queue* pq, QDataType x);
//出队
void QPop(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//获取对头
QDataType QFront(Queue* pq);
//队大小
int QSize(Queue* pq);
//返回队尾元素
QDataType QTail(Queue* pq);

queue.c

void QInit(Queue* pq)
{
// 传过来的时候就怕传一个空地址过来,那么队列都没有还怎么对其操作
	assert(pq);
	pq->head = pq->tail = NULL;//
	pq->size = 0;
}
void QDestroy(Queue* pq)
{
	assert(pq);
	//assert(pq->head!=NULL);//对头都为空那么就不用再释放了
	
	while (pq->head)
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QPush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}

	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}

	pq->size++;
}

void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

	if (pq->tail == pq->head)
	{
		free(pq->head);
		pq->head = NULL;
	}

	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->size--;
}

bool QEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

QDataType QFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

int QSize(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->size;
}

QDataType QTail(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

test.c

#include"Queue.h"

int main()
{
	Queue pq;
	QInit(&pq);
	QPush(&pq, 1);
	QPush(&pq, 2);
	QPush(&pq, 3);
	QPush(&pq, 4);

	/*while (!QEmpty(&pq))
	{
		printf("%d ", QFront(&pq));
		QPop(&pq);
	}*/
	printf("%d ", QTail(&pq));
	printf("%d ", QSize(&pq));

	QDestroy(&pq);
	return 0;
}

三、leetcode相关OJ

1、用队列实现栈
在这里插入图片描述
由于队列是先进先出,栈是先进后出

具体思想那么要用队列来实现栈就要保证最先进栈的要最后出栈,可是队列又是先进先出,要保证队列最后一个先出去的话,那么让那个不为空的队列其队尾为止前面的元素依次倒入另外一个队列中,然后取出这个数据那个那么就用两个队列才能完成

在这里插入图片描述
而队列就是我上面写的咯

QDataType QTail(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
//栈里有两个队列
typedef struct {
  Queue q1;
  Queue q2;
} MyStack;


//创建这个栈是要返回栈的地址的
//那么就malloc一个栈出来
//如果不向内存动态申请一个栈而是直接创建一个栈,那么创建的栈就是一个临时变量,它出了这个函数空间就会自动
MyStack* myStackCreate() {
 MyStack*st = (MyStack*)malloc(sizeof(MyStack));
 if(st == NULL)
 {
     perror("malloc fail\n");
     return NULL;
 }

 else
 {
     //创建栈之后需要将栈结构体成员中的连个队列也初始化而这个队列又是一个结构体,且要改变队列内容就需传结构体地址传过去
     //st是栈的结构体指针村的是栈的地址,对->访问它的成员,得到队列q1,q2,由于是用队列实现栈所以操作其实都是队列实现的,相当于操作的是队列,然后&st->q1就是传队列地址
     QInit(&st->q1);
     QInit(&st->q2);
     return st;
 }
}

//入栈是往队列不为空的那个里面入,
//最开始两个队列都是空就随便入一个,但是后面再入栈时就要往不为空的那个队列里面入数据。
void myStackPush(MyStack* obj, int x) {
   if(!QEmpty(&obj->q1))
   {
       QPush(&obj->q1,x);
   }

   else
   {
       QPush(&obj->q2,x);
   }
}

//栈是一个后进先出的特殊数据结构,且每次要出数据只能从栈顶出
//而队列是一种先进先出的特殊数据结构,且出数据只能在对头出,而我们要用对列来实现这个栈,我们只有将不为空的 那个队列中队尾元素之前的元素倒入那个为空的队列中,然后将原来那个不为空队列的队尾元素保存下来,最后将其出掉,然后如果再次调用出栈这个函数接口,那么也是一样的操作
//这里出队不是将那些元素丢掉,而是将这些出队元素入到原本为空的那个队列中
//
int myStackPop(MyStack* obj) {
   Queue*empty = &obj->q1;//这里先默认q1为空队列
   Queue*nonempty = &obj->q2;
   if(!QEmpty(&obj->q1))//然后再判断队列q1是否为空,队列q1如果不为空,那么队列q2就是空咯
   {
       empty = &obj->q2;
       nonempty = &obj->q1;
   }
  //将不为空的队列nonempty中对头元素先入到原来为空的队列empty中去,然后再将对头元素出掉,出到只剩下一个元素为止
   while(QSize(nonempty)>1)
   {
       //将要出的数据反手就入到empty空的队列中去
        QPush(empty,QFront(nonempty));
        //然后再出数据
        QPop(nonempty);
   }
   int top = QFront(nonempty);
    QPop(nonempty);
    return top;

}

//返回栈顶元素,其实就是返回不为空队列nonempty这个队尾数据
int myStackTop(MyStack* obj) {
  Queue*empty = &obj->q1;
   Queue*nonempty = &obj->q2;
   if(!QEmpty(&obj->q1))
   {
       empty = &obj->q2;
       nonempty = &obj->q1;
   }

   return QTail(nonempty);
}

//判断栈是否为空就是判断两个队列中是否还有元素,其中一个还有都不为空
bool myStackEmpty(MyStack* obj) {
  return QEmpty(&obj->q1) &&QEmpty(&obj->q2);
}

//销毁栈不嫩一下子就将栈释放了,因为如果一下子就将栈释放了的话,你是释放了你这个栈里面的成员q1,q2,但是人家q1,q2里安他自己还有数据啊,这样造成了内存泄漏不得行
//而是一个先销毁队列中的数据然后再释放栈

void myStackFree(MyStack* obj) {
  QDestroy(&obj->q1);
  QDestroy(&obj->q2);
  free(obj);
}

2、leetcode用栈实现队列
在这里插入图片描述

思想:用两个栈实现,一个栈进行入队操作,另一个栈进行出队操作 出队操作:当出队的栈不为空是,直接进行出栈操作,如果为空,需要把入队的栈元素全部导入到出队的栈,然后再进行出栈操作

在这里插入图片描述

//由于栈最先进去的数据要最后才能获得 //假设1,2,3,4是按顺序依次入队那么它的出队顺序也是1,2,3,4
//要用栈来实现队列那么就要让原来的数据以逆序4,3
,2,1的方式存储到栈中然后每次出栈顶的数据就可以实现队列的先进先出,而一个栈明显行不通,这时让一个栈用来实现入队,栈push用来模拟入队,那么进栈也就是1,2,3,4,将从push栈依次得到的数据倒入pop栈中,pop栈中进栈就是4,3,2,1那么从栈pop中拿到的数据也就是同进队时的顺序一样的1,2,3,4,在push栈向pop栈中倒数据时要保证pop栈为空方可倒不然如果pop栈里还有元素4,这时又从push栈中倒数据5,那么这个4就要在5后面出队,这就不符合对的先进先出了;

代码实现

typedef int STDataType;
typedef struct STNode
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* st)
{
	assert(st);
	st->a = (STDataType*)malloc(sizeof(STDataType)*4);

	if (st->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	
	st->capacity = 4;
	st->top = 0;
}
//销毁
void StackDestory(ST* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->top = st->capacity = 0;
}
//进栈
void StackPush(ST* st, STDataType x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(st->a,st->capacity*2*(sizeof(STDataType) ));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			st->a = tmp;
			st->capacity *= 2;
		}
	}
	st->a[st->top] = x;
	st->top++;
}
//出栈
void StackPop(ST* st)
{
	assert(st);
	assert(st->top > 0);
	st->top--;
}
//判空
bool StackEmpty(ST* st)
{
	assert(st);
	return st->top == 0;
}
//获取栈顶元素
STDataType StackTop(ST* st)
{
	assert(st);
	assert(st->top > 0);
	return st->a[st->top-1];
}
//获取栈的大小
int StackSize(ST* st)
{
	assert(st);
	return st->top;
}


//栈的结构体定义
//先定义两个栈出来
//和用对列实现栈类似

typedef struct {
     //push栈用来模拟入队
     //pop栈用来模拟出队

  ST push;
  ST pop;
} MyQueue;

//这里也和用队列实现栈类似
MyQueue* myQueueCreate() {
  MyQueue*pq = (MyQueue*)malloc(sizeof(MyQueue));
  if(pq == NULL)
  {
      perror("malloc fail");
      return NULL;
  }
  StackInit(&pq->push);
  StackInit(&pq->pop);
  return pq;
}

//队列是先进先出的特殊数据结构
//栈是先进后出,并且在栈顶插入和删除

//直接往push中入数据,不用管push是否为空
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->push,x);
}


//导入数据时注意pop栈为空才倒
int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    

    int front = StackTop(&obj->pop);
    StackPop(&obj->pop);
    return front;
}

//每次返回pop栈顶元素就是对头元素
int myQueuePeek(MyQueue* obj) {
  if(StackEmpty(&obj->pop))
 {
   while(!StackEmpty(&obj->push))
    {
        StackPush(&obj->pop,StackTop(&obj->push));
        StackPop(&obj->push);
    }
 }

    return StackTop(&obj->pop);
}

//两个栈为空队列才为空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}

//先销毁栈再释放队列
void myQueueFree(MyQueue* obj) {
    StackDestory(&obj->pop);
    StackDestory(&obj->push);
    free(obj);
}

由于这时用C语言实现的需要自己手写一个栈。


队列是一种特殊的数据结构,在后面学习二叉树还会用到,因此还是要将其掌握熟练

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/1932.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

计算机网络管理 TCP三次握手的建立过程,Wireshark抓包分析并验证TCP三次握手建立连接的报文

⬜⬜⬜ ---&#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea; (*^▽^*)欢迎光临 &#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea;---⬜⬜⬜ ✏️write in front✏️ &#x1f4dd;个人主页&#xff1a;陈丹宇jmu &#x1f381;欢迎各位→…

【Linux入门篇】操作系统安装、网络配置

目录 &#x1f341;Linux详解 &#x1f342;1.操作系统 &#x1f342;2.操作系统组成 &#x1f342;3.操作系统历史 &#x1f342;4.常见的Linux系统 &#x1f342;5.centos7下载 &#x1f342;6.安装centos7 &#x1f341;linux初始化配置 &#x1f343;1.虚拟机系统安装后操作…

从零实现深度学习框架——学习率调整策略介绍

引言 本着“凡我不能创造的,我就不能理解”的思想,本系列文章会基于纯Python以及NumPy从零创建自己的深度学习框架,该框架类似PyTorch能实现自动求导。 要深入理解深度学习,从零开始创建的经验非常重要,从自己可以理解的角度出发,尽量不使用外部完备的框架前提下,实现我…

【微信小程序】-- 案例 - 自定义 tabBar(四十六)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…

kali内置超好用的代理工具proxychains

作者&#xff1a;Eason_LYC 悲观者预言失败&#xff0c;十言九中。 乐观者创造奇迹&#xff0c;一次即可。 一个人的价值&#xff0c;在于他所拥有的。所以可以不学无术&#xff0c;但不能一无所有&#xff01; 技术领域&#xff1a;WEB安全、网络攻防 关注WEB安全、网络攻防。…

31. 下一个排列

题目链接&#xff1a;https://leetcode.cn/problems/next-permutation/解题思路&#xff1a;整数数组的 下一个排列 是指其整数的下一个字典序更大的排列&#xff0c;其实也就是把整数所有数字从左往右组合成一个数&#xff0c;则下一个排列就是将数组中的所有元素重新组合成一…

【跟着chatgpt学go】Gooutine和Channel

Goroutine Goroutine 是 Go 语言中的一种并发机制&#xff0c;它是一种轻量级线程&#xff0c;可以通过关键字 go 启动一个新的 Goroutine。相比传统的线程&#xff0c;Goroutine 拥有更小的栈空间&#xff0c;因此可以创建更多的 Goroutine。 下面是一个简单的 Goroutine 的…

数据结构初阶(顺序表)

文章目录1、时间复杂度1.2、大O渐进表示法1.3、递归算法时间复杂度计算2、空间复杂度3、顺序表1、概念2、静态顺序表3、动态顺序表1、创建结构体&#xff08;头文件中创建&#xff09;2、销毁链表3、初始化结构体4、打印函数5、内存扩容6、顺序表任意位置插入数据7、顺序表任意…

从 hybrid开发----》微前端

为什么开始写关于微前端的一系列博客&#xff1f; 1. 学生时代讨论关于hybrid APP的应用开发&#xff0c;历史的选择总是变化的&#xff0c;需要更进一步深入。 2. 之前工作项目中见到过沙箱隔离之后CSS冲突&#xff0c;需要学一下如何解决 ----------------------------- …

QT CTK插件框架 (一 下载编译)

CTK 为支持生物医学图像计算的公共开发包&#xff0c;其全称为 Common Toolkit。为医学成像提供一组统一的基本功能&#xff1b;促进代码和数据的交互及结合&#xff1b;避免重复开发&#xff1b;在工具包&#xff08;医学成像&#xff09;范围内不断扩展到新任务&#xff0c;而…

ChatGPT助力校招----面试问题分享(四)

1 ChatGPT每日一题&#xff1a;电阻如何选型 问题&#xff1a;电阻如何选型 ChatGPT&#xff1a;电阻的选型通常需要考虑以下几个方面&#xff1a; 额定功率&#xff1a;电阻的额定功率是指电阻能够承受的最大功率。在选型时&#xff0c;需要根据电路中所需要的功率确定所选…

【JavaEE】Thread 类及常用方法

一、Thread 类Thread 类我们可以理解为是 java 用于管理线程的一个类&#xff0c;里面封装了操作系统提供的线程管理这一方面的 API &#xff08;Thread 是优化后的结果&#xff09;, Java 代码创建的每一个线程&#xff0c;可以理解为为 Thread 实例化的对象&#xff0c;Threa…

JUC是什么?

JUC 简介 在 Java 中&#xff0c;线程部分是一个重点&#xff0c;本篇文章说的 JUC 也是关于线程的。JUC 就是 java.util .concurrent 工具包的简称。这是一个处理线程的工具包&#xff0c;JDK 1.5 开始出现的。 进程与线程 进程&#xff08;Process&#xff09; 是计算机中…

Java基础:笔试题

文章目录Java 基础题目1. 如下代码输出什么&#xff1f;2. 当输入为2的时候返回值是多少?3. 如下代码输出值为多少?4. 给出一个排序好的数组&#xff1a;{1,2,2,3,4,5,6,7,8,9} 和一个数&#xff0c;求数组中连续元素的和等于所给数的子数组解析第一题第二题第三题第四题方案…

[ 云计算 | Azure ] Chapter 05 | 核心体系结构之管理组、订阅、资源和资源组以及层次关系

本文主要对如下内容进行讲解&#xff1a;Azure云计算的核心体系结构组件中的&#xff1a;资源、订阅和资源组&#xff0c;以及了解 Azure 资源管理器 (ARM) 如何部署资源。 本系列已经更新文章列表&#xff1a; [ 云计算 | Azure ] Chapter 03 | 描述云计算运营中的 CapEx 与…

面试了8家软件公司测试岗位,面试题大盘点,我真的尽力了

包含的模块&#xff1a;本文分为十九个模块&#xff0c;分别是&#xff1a;软件测试 基础、liunx、MySQL、web测试、接口测试、APP测试 、管理工具、Python、性能测试、selenium、lordrunner、计算机网络、组成原理、数据结构与算法、逻辑题、人力资源需要的可以看文末获取方式…

Qt基础之三十三:海量网络数据实时显示

开发中我们可能会遇到接收的网络数据来不及显示的问题。最基础的做法是限制UI中加载的数据行数,这样一来可以防止内存一直涨,二来数据刷新非常快,加载再多也来不及看。此时UI能看到数据当前处理到什么阶段就行,实时性更加重要,要做数据分析的话还得查看日志文件。 这里给出…

【蓝桥杯专题】枚举、模拟与排序 (C++ | 洛谷 | acwing | 蓝桥)

菜狗现在才开始备战蓝桥杯QAQ 文章目录【蓝桥杯专题】 &#xff08;C | 洛谷 | acwing | 蓝桥&#xff09;回文日期纸张尺寸 蓝桥杯真题错误票据AcWing 788. 逆序对的数量航班时间移动距离连号区间1236. 递增三元组PPPPP【蓝桥杯专题】 &#xff08;C | 洛谷 | acwing | 蓝桥&a…

腾讯云轻量应用服务器、CVM云服务器和GPU云服务器价格表(2023版)

这是腾讯云GPU云服务器、CVM云服务器、轻量应用服务器配置价格表&#xff0c;最近整理的。目前腾讯云服务器分为轻量应用服务器、CVM云服务器和GPU云服务器&#xff0c;首先介绍一下这三种服务器。 1、GPU 云服务器&#xff08;Cloud GPU Service&#xff0c;GPU&#xff09;是…

苹果发布无线充新专利,苹果Find My技术成为近几年苹果的重要创新

根据美国商标和专利局公示的清单&#xff0c;苹果公司近日获批了编号为 US 20230080598 A1 新专利。该专利主要为各种类型的无线充电器制造配件盒。 苹果表示近年来无线充电市场得到了快速发展&#xff0c;但目前市场尚未规范&#xff0c;可能使用不同的无线充电标准。这就导…