行业知识
数据结构：队列 || oj(l两个队列实现栈)
@[TOC](数据结构：队列 || oj(l两个队列实现栈))
一、队列的概念
1.什么是队列？
//先说一下，队列跟栈一样都是很重要的数据结构，重要的不是说这个数据结构怎么实现，重要的是结构的优势！
//栈：是先入先出，选的最好的是底层用数组，来实现，可以栈顶入，栈顶出，复杂度都是O(1),在就是CPU高速缓存，缓存线取数据（好像一般是64个字节），取数据效率高！，比链表好一点，用链表的话，单链表头做栈顶，用做压数据，和取数据都可以！
//队列：这种数据结构的要求是：先入先出，不能用数组来实现，原因是：如果把数组后面当尾巴，队尾入数据这个可以，队头出数据要挪动数据，时间复杂度是O(n)，因此用链表来实现队列!
2.队列的概念
//队列：只允许在一段插入数据操作，在另一端删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
// 入队列：进行插入操作的一端称为队尾
// 出队列：进行删除操作的一端称为队头
//队尾入，队头出
//队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
//用链表实现队列，链表头用作队列头取数据，链表尾用作队列尾巴，插（放）数据！
//定义节点：
typedef int QDataType ;
typedef struct QListNode{
int val;
struct QListNode* next;
}QLNode;
//这样定义一个链表有个问题，头删当然可以，尾插呢？时间复杂度是O(n),那么可以定义一个头指针（head），一个尾指针(tail)来解决这个问题,还要考虑统计在队列中数据的个数，因此在定义一个int Size;那么把这些数据放在一个结构体中，就很好的解决了这个问题！因此：
typedef struct Queue{
QLNode* head;
QLNode* tail;
int Size;
}Queue;
//这样这个栈就定义好了，这样定义的好处是：只要传Queue的地址，就可以改变head和tail和Size的值了，如果单独写，那么改变head的内容，则要QLNode** 来接受，可以规避这一点，还有就是头，尾都有标记，随便可以搞！
//下面来实现队列
//定义队列
//存储队列的数据typedef int QDataType;typedef struct QListNode {QDataType val;struct QListNode* next;}QLNode;//用结构体来存储队头，队尾，数据个数typedef struct Queue {QLNode* head;QLNode* tail;int size; //存储数据的个数}Queue; //实现的接口如下，虽然有些接口没用到，但是以后肯定用！
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//队尾入数据
void QueuePush(Queue* pq,QDataType x);
//队头出数据
void QueuePop(Queue* pq);
//获取对头数据
QDataType QueueFront(Queue* pq);
//获取对尾数据
QDataType QueueBack(Queue * pq);
//判空
bool QueueEmpty(Queue* pq);
//获取元素个数
int QueueSize(Queue* pq);
//下面实现各个接口
//初始化
//初始化void QueueInit(Queue* pq) {assert(pq);pq->head = pq->tail= NULL;pq->size = 0;} //销毁
//销毁void QueueDestory(Queue* pq) {assert(pq);QLNode* cur = pq->head;while (cur) {QLNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;} //队尾入数据，尾插法！
//分两种情况：初始化时：head=tail=NULL;
//1.那么head为空，则直接申请节点给就行！
//2.其它，正常尾插即可!
//队尾入数据void QueuePush(Queue* pq, QDataType x) {assert(pq);QLNode* newnode =(QLNode*)malloc(sizeof(QLNode));newnode->next = NULL;newnode->val = x;if (pq->head == NULL) {pq->head = pq->tail = newnode;}else {pq->tail->next = newnode;pq->tail = newnode;}pq->size++;} //队头删数据，头删
//考虑，因为头删的话，要存下一个节点，其实最坏情况下一个节点为NULL，也就是只有一个节点，那么head能置空，tail是一个问题，因此分开写！
//1.没有节点，直接断言assert;
//2.一个节点，直接释放，给head,tail置NULL；
//3.至少两个节点：删一个，下一个肯定不问NULL，直接正常情况删除！
//队头出数据void QueuePop(Queue* pq) {//头删assert(pq);//头指针为空，没有数据assert(pq->head);//一个节点//在单链表的头删中，可以直接写//在栈中特殊处理，因为一个节点的时候，要把tail置NULLif (pq->head->next == NULL) {free(pq->head);pq->head = NULL;pq->tail = NULL;}//其它else {QLNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;} //获取队头数据
//获取队头数据QDataType QueueFront(Queue* pq) {assert(pq);assert(pq->head);return pq->head->val;} //获取队尾数据
//获取队尾数据QDataType QueueBack(Queue* pq) {assert(pq);assert(pq->tail);return pq->tail->val;} //判空
//判空bool QueueEmpty(Queue* pq) {assert(pq);return pq->size == 0;} //获取元素个数
//获取元素个数int QueueSize(Queue* pq) {assert(pq);return pq->size;} //下面为整个代码!
//Queue.h
#pragma once#include #include #include #include //存储队列的数据typedef int QDataType;typedef struct QListNode {QDataType val;struct QListNode* next;}QLNode;//用结构体来存储队头，队尾，数据个数typedef struct Queue {QLNode* head;QLNode* tail;int size; //存储数据的个数}Queue;//初始化void QueueInit(Queue* pq);//销毁void QueueDestory(Queue* pq);//队尾入数据void QueuePush(Queue* pq, QDataType x);//队头出数据void QueuePop(Queue* pq);//获取队头数据QDataType QueueFront(Queue* pq);//获取队尾数据QDataType QueueBack(Queue* pq);//判空bool QueueEmpty(Queue* pq);//获取元素个数int QueueSize(Queue* pq); //Queue.c
#include "Queue.h"//初始化void QueueInit(Queue* pq) {assert(pq);pq->head = pq->tail= NULL;pq->size = 0;}//销毁void QueueDestory(Queue* pq) {assert(pq);QLNode* cur = pq->head;while (cur) {QLNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;}//队尾入数据void QueuePush(Queue* pq, QDataType x) {assert(pq);QLNode* newnode =(QLNode*)malloc(sizeof(QLNode));newnode->next = NULL;newnode->val = x;if (pq->head == NULL) {pq->head = pq->tail = newnode;}else {pq->tail->next = newnode;pq->tail = newnode;}pq->size++;}//队头出数据void QueuePop(Queue* pq) {//头删assert(pq);//头指针为空，没有数据assert(pq->head);//一个节点//在单链表的头删中，可以直接写//在栈中特殊处理，因为一个节点的时候，要把tail置NULLif (pq->head->next == NULL) {free(pq->head);pq->head = NULL;pq->tail = NULL;}//其它else {QLNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;}//获取队头数据QDataType QueueFront(Queue* pq) {assert(pq);assert(pq->head);return pq->head->val;}//获取队尾数据QDataType QueueBack(Queue* pq) {assert(pq);assert(pq->tail);return pq->tail->val;}//判空bool QueueEmpty(Queue* pq) {assert(pq);return pq->size == 0;}//获取元素个数int QueueSize(Queue* pq) {assert(pq);return pq->size;} //Test.c
#include "Queue.h"int main() {Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)) {int front = QueueFront(&q);printf("%d ", front);QueuePop(&q);}return 0;} 二、两个队列实现栈问题
//实现思路
//怎么入栈？
//怎么出栈？
//出栈：假设一个队列入 1 2 3 4，那么要求是出4，4在尾巴，怎么出，那么把1,2,3出队列，入一个空的队列，然后在出第一个队列的数据！
//入栈：如果队列不为空，则入数据
//下面实现整个接口
//创建栈
typedef struct { Queue q1; Queue q2;} MyStack; //动态申请创建栈
MyStack* myStackCreate() { MyStack* tmp = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&tmp->q1); QueueInit(&tmp->q2); return tmp;} //入栈
void myStackPush(MyStack* obj, int x) { //队列不为空的入 if(!QueueEmpty(&obj->q1)){ QueuePush(&obj->q1,x); } else{ QueuePush(&obj->q2,x); }} //出栈
int myStackPop(MyStack* obj) { //先把不为空的队列的size-1个元素移到为空的队列 //然后出队列 Queue* NoEmptyQueue = &obj->q1; Queue* EmptyQueue = &obj->q2; if(QueueEmpty(&obj->q1)){ NoEmptyQueue = &obj->q2; EmptyQueue = &obj->q1; } while(QueueSize(NoEmptyQueue)>1){ int front = QueueFront(NoEmptyQueue); QueuePop(NoEmptyQueue); QueuePush(EmptyQueue,front); } int front = QueueFront(NoEmptyQueue); QueuePop(NoEmptyQueue); return front;} //获取栈顶数据
//这个体现接口的优势，在队列中实现了取队列尾的数据！
//直接调用
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) { QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj);} //下面是整体的代码
typedef int QDataType;typedef struct QListNode {QDataType val;struct QListNode* next;}QLNode;//用结构体来存储队头，队尾，数据个数typedef struct Queue {QLNode* head;QLNode* tail;int size; //存储数据的个数}Queue;//初始化void QueueInit(Queue* pq) {assert(pq);pq->head = pq->tail= NULL;pq->size = 0;}//销毁void QueueDestory(Queue* pq) {assert(pq);QLNode* cur = pq->head;while (cur) {QLNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;}//队尾入数据void QueuePush(Queue* pq, QDataType x) {assert(pq);QLNode* newnode =(QLNode*)malloc(sizeof(QLNode));newnode->next = NULL;newnode->val = x;if (pq->head == NULL) {pq->head = pq->tail = newnode;}else {pq->tail->next = newnode;pq->tail = newnode;}pq->size++;}//队头出数据void QueuePop(Queue* pq) {//头删assert(pq);//头指针为空，没有数据assert(pq->head);//一个节点if (pq->head->next == NULL) {free(pq->head);pq->head = NULL;pq->tail = NULL;}//其它else {QLNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;}//获取队头数据QDataType QueueFront(Queue* pq) {assert(pq);assert(pq->head);return pq->head->val;}//获取队尾数据QDataType QueueBack(Queue* pq) {assert(pq);assert(pq->tail);return pq->tail->val;}//判空bool QueueEmpty(Queue* pq) {assert(pq);return pq->size == 0;}//获取元素个数int QueueSize(Queue* pq) {assert(pq);return pq->size;}typedef struct { Queue q1; Queue q2;} MyStack;MyStack* myStackCreate() { MyStack* tmp = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&tmp->q1); QueueInit(&tmp->q2); return tmp;}void myStackPush(MyStack* obj, int x) { //队列不为空的入 if(!QueueEmpty(&obj->q1)){ QueuePush(&obj->q1,x); } else{ QueuePush(&obj->q2,x); }}int myStackPop(MyStack* obj) { //先把不为空的队列的size-1个元素移到为空的队列 //然后出队列 Queue* NoEmptyQueue = &obj->q1; Queue* EmptyQueue = &obj->q2; if(QueueEmpty(&obj->q1)){ NoEmptyQueue = &obj->q2; EmptyQueue = &obj->q1; } while(QueueSize(NoEmptyQueue)>1){ int front = QueueFront(NoEmptyQueue); QueuePop(NoEmptyQueue); QueuePush(EmptyQueue,front); } int front = QueueFront(NoEmptyQueue); QueuePop(NoEmptyQueue); return front;}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) { QueueDestory(&obj->q1); QueueDestory(&obj->q2); 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);*/ 完结!
