数据结构：队列 || 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置NULL
	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;
}

//下面为整个代码!

//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置NULL
	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;
}

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

完结!