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