1. Toy模板网首页
  2. > Toy博客

队列实现及leetcode相关OJ题

10月前 作者：青山与你 分类：Toy博客 阅读(38) 违法举报

这篇具有很好参考价值的文章主要介绍了队列实现及leetcode相关OJ题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

上一篇写的是栈这一篇分享队列实现及其与队列相关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、用队列实现栈
leecode 队列,leetcode,数据结构,链表,c语言
由于队列是先进先出，栈是先进后出

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

leecode 队列,leetcode,数据结构,链表,c语言
而队列就是我上面写的咯

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用栈实现队列
leecode 队列,leetcode,数据结构,链表,c语言

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

leecode 队列,leetcode,数据结构,链表,c语言

//由于栈最先进去的数据要最后才能获得 //假设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语言实现的需要自己手写一个栈。

队列是一种特殊的数据结构，在后面学习二叉树还会用到，因此还是要将其掌握熟练文章来源地址https://www.toymoban.com/news/detail-778710.html

到了这里，关于队列实现及leetcode相关OJ题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】数据结构题解（11）[用队列实现栈]

    【LeetCode】数据结构题解（11）[用队列实现栈]

    所属专栏：玩转数据结构题型❤️ 🚀 博主首页：初阳785❤️ 🚀 代码托管：chuyang785❤️ 🚀 感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️ 🚀 博主也会更加的努力，创作出更优质的博文！！❤️ 🚀 关注我，关注我，关注我，重要的事情说三遍！！！！！

    2024年02月13日
    浏览(39)
  • 数据结构OJ：设计循环队列

    数据结构OJ：设计循环队列

    本题为LeetCode上的经典题目，题目要求我们设计一种循环队列，满足FIFO原则且队尾被连接在队首之后。 题目中介绍循环队列的好处是可以重复利用空间，所以我们很容易想到在初始化时即开辟指定大小的空间，之后便不需要再开辟空间，只需后续销毁即可。 首先我们要选择

    2024年04月17日
    浏览(66)
  • 【算法与数据结构】232、LeetCode用栈实现队列

    【算法与数据结构】232、LeetCode用栈实现队列

    所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 ：这道题要求我们用栈模拟队列（工作上一定没人这么搞）。程序当中，push函数很好解决，直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作，而栈是先进后出。只

    2024年02月12日
    浏览(44)
  • 【数据结构】如何用栈实现队列？图文解析（LeetCode）

    【数据结构】如何用栈实现队列？图文解析（LeetCode）

    LeetCode链接：232. 用栈实现队列 - 力扣（LeetCode） 注：本文默认读者已掌握栈与队列的基本操作 可以看这篇文章熟悉知识点：【数据结构】栈与队列_字节连结的博客-CSDN博客 目录 做题思路 代码实现 1. MyQueue 2. myQueueCreate 3. myQueuePush 4. myQueuePeek 5. myQueuePop 6. myQueueEmpty 7. myQueueF

    2024年02月11日
    浏览(33)
  • 【数据结构】如何用队列实现栈？图文详解（LeetCode）

    【数据结构】如何用队列实现栈？图文详解（LeetCode）

    LeetCode链接：225. 用队列实现栈 - 力扣（LeetCode） 本文默认读者已经掌握栈与队列的基本知识 或者先看我的另一篇博客：【数据结构】栈与队列_字节连结的博客-CSDN博客 由于我们使用的是C语言，不能直接使用队列的操作， 所以做这道题得先把我们之前实现的队列复制过来：

    2024年02月12日
    浏览(37)
  • 【Java数据结构 -- 队列:队列有关面试oj算法题】

    【Java数据结构 -- 队列:队列有关面试oj算法题】

    只允许在一端进行插入数据操作，在另一端进行删除数据操作得特殊线性表，队列是 先进先出 ，入队：进行插入操作得一端称为 队尾（rear） ，出队：进行删除操作的一端称为 队头(front) 。队列Queue是个接口， 底层通过链表实现的 。 boolean offer(E e) – 入队列 E poll() – 出队

    2024年01月25日
    浏览(48)
  • 栈和队列OJ题：LeetCode--225.用队列实现栈

    栈和队列OJ题：LeetCode--225.用队列实现栈

     朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode--225.用队列实现栈 数 据 结 构 专 栏：数据结构 个    人   主    页 ：stackY、 LeetCode 专  栏 ：LeetCode刷题训练营 LeetCode--225.用队列实现栈：https://leetcode.cn/problems/implement-stack-using-queues/ 目录 1.题目介绍 2.实例演

    2024年02月06日
    浏览(38)
  • 栈和队列OJ题：LeetCode--232.用栈实现队列

    栈和队列OJ题：LeetCode--232.用栈实现队列

    朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode--232.用栈实现队列 数 据 结 构 专 栏：数据结构 个    人   主    页 ：stackY、 LeetCode 专  栏 ：LeetCode刷题训练营 LeetCode--232.用栈实现队列：https://leetcode.cn/problems/implement-queue-using-stacks/ 目录 1.题目介绍 2.实例演示

    2024年02月05日
    浏览(49)
  • 数据结构OJ题——栈和队列

    数据结构OJ题——栈和队列

    题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty） void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 fal

    2024年04月11日
    浏览(40)
  • 数据结构——栈和队列OJ题

    数据结构——栈和队列OJ题

    欢迎来到专项提升小课堂！ 今天的题目稍稍有难度哦！ 但是只要用心，是难不倒同学们的！ 题目链接：OJ链接 提示： 1 = x = 9； 最多调用100 次 push、pop、top 和 empty ； 每次调用 pop 和 top 都保证栈不为空； 核心思想： 用队列模拟出栈的先入后出这一特性！ 解题思路： 此题可

    2024年02月11日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包