当前位置: 首页 > news >正文

07 队列

目录

1.队列
2.实现
3.OJ题


1. 队列

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

在这里插入图片描述

2. 实现

队列可以用数组和链表的结构实现,需要从两端出操作数据,所以用链表的结构更优一点

在这里插入图片描述

队列的设计需要两层结构体,一层结构体是节点结构体,另一层是队列结构

头文件

#pragma once
#include <stdbool.h>typedef int DATATYPE;//节点
typedef struct _Node
{DATATYPE data;struct _Node* next;
}Node;//队列
typedef struct _Queue
{struct _Node* head;struct _Node* tail;int size;
}Queue;// 初始化
void Init(Queue* que);
// 入队
void Push(Queue* que, DATATYPE data);
// 出队
void Pop(Queue* que);
// 是否为空
bool Empty(Queue* que);
// 返回队首
DATATYPE Front(Queue* que);
// 返回队尾
DATATYPE Back(Queue* que);
// 队列大小
int Size(Queue* que);
// 销毁
void Destory(Queue* que);

实现文件

#include "Queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>void Init(Queue* que)
{assert(que);//置空que->head = que->tail = NULL;que->size = 0;
}void Push(Queue* que, DATATYPE data)
{assert(que);Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL){perror("malloc fail");return;}newnode->data = data;newnode->next = NULL;//空队,不为空if (que->head == NULL){//防止一个空,另一个不为空assert(que->tail == NULL);que->head = que->tail = newnode;}else{que->tail->next = newnode;que->tail = newnode;}que->size++;
}void Pop(Queue* que)
{assert(que);assert(!Empty(que));//一个节点,多个节点if (que->head->next == NULL){free(que->head);que->head = que->tail = NULL;}else{//头删Node* del = que->head;que->head = que->head->next;free(del);}que->size--;
}bool Empty(Queue* que)
{assert(que);//que.head == NULL && que.tail == NULLreturn que->size == 0;
}DATATYPE Front(Queue* que)
{assert(que);assert(!Empty(que));return que->head->data;
}DATATYPE Back(Queue* que)
{assert(que);assert(!Empty(que));return que->tail->data;
}int Size(Queue* que)
{assert(que);return que->size;
}void Destory(Queue* que)
{assert(que);Node* cur = que->head;while (cur != NULL){Node* del = cur;cur = cur->next;free(del);}que->head = que->tail = NULL;que->size = 0;
}

主文件

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "Queue.h"int main()
{Queue que;Init(&que);Push(&que, 1);Push(&que, 2);Push(&que, 3);Push(&que, 4);printf("%d ", Front(&que));printf("%d \r\n", Back(&que));Pop(&que);while (!Empty(&que)){printf("%d ", Front(&que));printf("%d \r\n", Back(&que));Pop(&que);}Destory(&que);return 0;
}

3. OJ题

3.1 用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/description/
在这里插入图片描述

思路
利用前面写的队列。用队列实现栈的关键点在于,队列是先进先出,栈是先进后出。这时,可以用两个栈,需要出数据时将一个栈的所有数据捯到另一个栈中,留下最后一个数据,然后出队,这个就是栈的栈顶元素。每次需要出数据反复这样。入数据时,找一个不为空的入,不为空的出数据捯一遍后,刚好剩下刚进入的数据,栈为空也可以这样

在这里插入图片描述

//引入队列
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int DATATYPE;//节点
typedef struct _Node
{DATATYPE data;struct _Node* next;
}Node;//队列
typedef struct _Queue
{struct _Node* head;struct _Node* tail;int size;
}Queue;void Init(Queue* que)
{assert(que);//置空que->head = que->tail = NULL;que->size = 0;
}void Push(Queue* que, DATATYPE data)
{assert(que);Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL){perror("malloc fail");return;}newnode->data = data;newnode->next = NULL;//空队,不为空if (que->head == NULL){//防止一个空,另一个不为空assert(que->tail == NULL);que->head = que->tail = newnode;}else{que->tail->next = newnode;que->tail = newnode;}que->size++;
}bool Empty(Queue* que)
{assert(que);//que.head == NULL && que.tail == NULLreturn que->size == 0;
}
void Pop(Queue* que)
{assert(que);assert(!Empty(que));//一个节点,多个节点if (que->head->next == NULL){free(que->head);que->head = que->tail = NULL;}else{//头删Node* del = que->head;que->head = que->head->next;free(del);}que->size--;
}DATATYPE Front(Queue* que)
{assert(que);assert(!Empty(que));return que->head->data;
}DATATYPE Back(Queue* que)
{assert(que);assert(!Empty(que));return que->tail->data;
}int Size(Queue* que)
{assert(que);return que->size;
}void Destory(Queue* que)
{assert(que);Node* cur = que->head;while (cur != NULL){Node* del = cur;cur = cur->next;free(del);}que->head = que->tail = NULL;que->size = 0;
}//------------------------------------------------------------------------
//实现栈
typedef struct {Queue que1;Queue que2;
} MyStack;MyStack* myStackCreate() {MyStack* stk = (MyStack*)malloc(sizeof(MyStack));Init(&stk->que1);Init(&stk->que2);return stk;
}void myStackPush(MyStack* obj, int x) {//往空队列插入if(Empty(&obj->que1))Push(&obj->que1, x);elsePush(&obj->que2, x);
}int myStackPop(MyStack* obj) {//定义空和非空,如果错误交换Queue* empty = &obj->que1;Queue* noempty = &obj->que2;if(Empty(&obj->que2)){empty = &obj->que2;noempty = &obj->que1;}//非空的大于1个往另一个队列捯while(Size(noempty) > 1){Push(empty, Front(noempty));Pop(noempty);}int x = Front(noempty);Pop(noempty);return x;
}int myStackTop(MyStack* obj) {//定义空和非空,如果错误交换Queue* empty = &obj->que1;Queue* noempty = &obj->que2;if(Empty(&obj->que2)){empty = &obj->que2;noempty = &obj->que1;}return Back(noempty);
}bool myStackEmpty(MyStack* obj) {return Empty(&obj->que1) && Empty(&obj->que2);
}void myStackFree(MyStack* obj) {Destory(&obj->que1);Destory(&obj->que2);free(obj);
}/*** 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);
*/

3.2 栈实现队列

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

在这里插入图片描述

思路
利用实现的栈。栈实现队列同样需要两个栈,由于栈是先进后出,当我们捯一遍数据后,刚好会把所有数据顺序反过来,所以只需要捯一次。利用这种特性,可以将两个栈分为只仅数据的和出数据的。刚开始出栈为空,需要出数据时,从入栈捯数据过来然后出栈顶元素

在这里插入图片描述

//引用栈结构
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int DATATYPE;typedef struct _Stack
{DATATYPE* ary;int top;        //指向下一个存放数据的位置int capacity;
}Stk;void Init(Stk* stack)
{assert(stack);stack->ary = NULL;stack->top = 0;   //指向栈顶下一个位置stack->capacity = 0;
}void Push(Stk* stack, DATATYPE data)
{assert(stack);//需要扩容if (stack->top == stack->capacity){int newcap = stack->capacity == 0 ? 4 : stack->capacity * 2;DATATYPE* temp = (DATATYPE*)realloc(stack->ary, sizeof(DATATYPE) * newcap);if (temp == NULL){perror("realloc fail");return;}stack->ary = temp;stack->capacity = newcap;  }//存数据stack->ary[stack->top] = data;stack->top++;
}bool Empty(Stk* stack)
{assert(stack);return stack->top == 0;
}void Pop(Stk* stack)
{assert(stack);assert(!Empty(stack));stack->top--;
}DATATYPE Top(Stk* stack)
{assert(stack);assert(!Empty(stack));return stack->ary[stack->top - 1];
}int Size(Stk* stack)
{assert(stack);return stack->top;
}void Destory(Stk* stack)
{assert(stack);free(stack->ary);stack->ary = NULL;stack->capacity = 0;stack->top = 0;
}//------------------------------------------------------------------------
//实现队列
typedef struct {Stk stpush;Stk stpop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));Init(&obj->stpush);Init(&obj->stpop);return obj;
}void myQueuePush(MyQueue* obj, int x) {Push(&obj->stpush, x);
}int myQueuePop(MyQueue* obj) {int ch = myQueuePeek(obj);Pop(&obj->stpop);return ch;
}int myQueuePeek(MyQueue* obj) {if(Empty(&obj->stpop)){while(!Empty(&obj->stpush)){Push(&obj->stpop, Top(&obj->stpush));Pop(&obj->stpush);}}return Top(&obj->stpop);
}bool myQueueEmpty(MyQueue* obj) {return Empty(&obj->stpush) && Empty(&obj->stpop);
}void myQueueFree(MyQueue* obj) {Destory(&obj->stpush);Destory(&obj->stpop);free(obj);
}/*** 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);
*/
http://www.lryc.cn/news/287253.html

相关文章:

  • 产品面试题2
  • [NSSCTF]-Web:[SWPUCTF 2021 新生赛]easy_md5解析
  • 嵌入式解惑——串口通信中的流控制有什么作用?
  • Kubernetes-Taint (污点)和 Toleration(容忍)
  • python三数之和
  • uniapp 用css animation做的鲤鱼跃龙门小游戏
  • JeecgBoot 3.6.1实现Modal对话框,以为审核数据为例
  • Spring基于dynamic-datasource实现MySQL多数据源
  • JS高频面试题(下)
  • 单点登陆(SSO)基于CAS实现前后端分离的SSO系统开发「IDP发起」
  • 二叉树
  • 边缘计算:挑战与机遇的平衡艺术
  • Windows11 Copilot助手开启教程(免费GPT-4)
  • 【Golang入门教程】如何使用Goland创建并运行项目
  • 鸿蒙开发实战-手写文心一言AI对话APP
  • 鸿蒙常用UI效果及一些处理方式总结
  • dataGrip连接数据库mysql和intersystems的iris
  • 【51单片机】点亮第一个LED灯
  • ubuntu20.04 格式化 硬盘 扩展硬盘
  • openssl3.2/test/certs - 031 - purpose variants: clientAuth
  • ubuntu下docker卸载和重新安装
  • 搭建k8s集群实战(一)系统设置
  • go-carbon v2.3.6 发布,轻量级、语义化、对开发者友好的 golang 时间处理库
  • 力扣2859-计算k置位下标对应元素的和
  • [计算机提升] 切换(域)用户
  • 蓝桥杯练习题dfs与bfs
  • 软件游戏提示msvcp140.dll丢失的解决方法,全面分析msvcp140.dll文件
  • LandrayOA内存调优 / JAVA内存调优 / Tomcat web.xml 超时时间调优实战
  • 免费SSL数字证书申请,免费数字证书使用教程
  • 深入理解Flutter中的GlobalKey与LocalKey(ValueKey、ObjectKey、UniqueKey)及其使用方法