目录
1.栈
1.1.栈的概念及结构
1.2.栈的实现
2.队列
2.1.队列的概念及结构
2.2.队列的实现
3.运用栈理解一道题
4.使用两个队列实现一个栈
1.栈
1.1.栈的概念及结构
首先，我们来了解一种新的数据结构——栈。栈是一种特殊的线性表，其只允许在固定一端进行插入和删除元素操作。进行数据的插入和删除这一端，称之为栈顶，另一端即栈底。栈中的数据是采取后进先出 LIFO（Last In First Out）的规则。这里有一些更为专业的话术：
压栈：栈的插入操作（也称为进栈/压栈）
出栈：栈的删除操作
栈的导入与导出数据均在栈顶进行。值得注意的是：栈的导出不一定是根据栈的导入时的顺序进行的。
1.2.栈的实现
我们可以使用数组或链表来实现栈，对数组而言，在数组尾部插入数据代价较小，因为其不需要遍历整个数组。下图演示栈的后进先出。
接下来，我们分析栈的实现
Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int STDataType;
typedef struct Stack {STDataType* a;int top;//栈的个数int capacity;//容量：扩容
}ST;//初始化
void STInit(ST* pst);
//销毁
void STDestory(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//取出栈的数据
STDataType STTop(ST* pst)
//判空
bool STEmpty(ST* pst);
//获取数据个数
STDataType STSize(ST* pst);Stack.c
STInit: 对栈进行初始化，该栈使用数组实现，a(数组名)，top(指向栈顶位置的下一个位置)，capacity(容量)。
#include"stack.h"
void STInit(ST* pst) {assert(pst);pst->a = NULL;//top指向栈顶数据的下一个位置pst->top = 0;pst->capacity = 0;
}STPush：将数据导入栈中，首先，将空间进行扩容（防止空间不足引起的越界访问）,并将扩容后的空间传给数组a，然后，再于新空间进行导入数据的操作，结尾记得改变新栈的个数。
//入栈
void STPush(ST* pst, STDataType x) {assert(pst);if (pst->top == pst->capacity) {//扩容int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));if (tmp == NULL) {perror("Realloc failed\n");exit(1);}//将扩容后的地址(指针)传递给 pst->apst->a = tmp;//更新扩容后，容器的大小pst->capacity = newcapacity;}//将 x 插入栈中pst->a[pst->top] = x;pst->top++;
}
STPop：导出栈中的数据，直接传数组的实参，将其栈的个数减少一位，便导出一个数据。
//出栈
void STPop(ST* pst) {assert(pst);assert(pst->top > 0);pst->top--;
}STTop：由于top指向栈顶的下一个位置，使用我们解引用top-1位置，也就是栈顶数据。
//取出栈的数据
STDataType STTop(ST* pst) {assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}
STEmpty： 通过return返回值(bool型)
//判空
bool STEmpty(ST* pst) {assert(pst);return pst->top == 0;
}STSize：top指向栈顶的下一个位置，对应数组的数据个数=下标+1，top即栈的数据个数。
//获取数据个数
STDataType STSize(ST* pst) {assert(pst);return pst->top;
}STDestroy： 将栈内的数据置空或变为0。
//销毁
void STDestroy(ST* pst) {assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}以上便是栈的实现全部过程。
2.队列
2.1.队列的概念及结构
队列与栈不同的是，队列是一种只允许一端进行插入数据，另一端进行删除数据的特殊线性表。队列采取的是先进先出 FIFO(First In First Out) 入队列，在队尾上进行插入数据操作，在队头进行删除数据操作。
2.2.队列的实现
接下来，我们使用具体的代码进行队列的实现。
queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;// 链式结构：表示队列
typedef struct QListNode
{struct QListNode* next;QDataType val;
}QNode;// 队列的结构
typedef struct Queue
{QNode* qhead;QNode* qtail;int size;
}Queue;// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);queue.c
QueueInit: 首先，我们使用了一个Queue的结构体，声明了qhead和qtail两个链表，现在，我们将其进行初始化。
// 初始化队列
void QueueInit(Queue* q)
{assert(q);q->qhead = NULL;q->qtail = NULL;q->size = 0;
}QueuePush：我们可以先开辟链式结构的空间，如果qtail尾有节点，即：先将其next节点的值改为newnode，再将qtail节点与newnode节点相互连接。
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc failed\n");exit(1);}newnode->next = NULL;newnode->val = data;if(q->qtail == NULL){q->qhead = q->qtail = newnode;}else{q->qtail->next = newnode;q->qtail = newnode;}q->size++;
}
QueuePop：如果队列只有一个节点即队头，那我们直接将其free，并置为空；若节点大于一个，那我们可以创建一个QNode*的next节点指向队头指向的下一个节点，然后再将队头的节点free，再重新将队头的节点改为next指针指向的新节点。
// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(q->size!=0);if (q->qhead->next == NULL) {free(q->qhead);q->qhead = q->qtail = NULL;}else {QNode* next = q->qhead->next;free(q->qhead);q->qhead = next;}q->size--;
}以下，获取队头元素、队尾元素、队列中有效元素个数 、判空函数均于栈的实现思想大体一致，在这里就不赘述了。
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);assert(q->qhead);return q->qhead->val;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{assert(q);assert(q->qtail);return q->qtail->val;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);return q->size == 0;
}QueueDestroy：销毁队列，我们可以采取遍历整个队列的方式，将其中的数据从头至尾进行free。
// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->qhead;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->qhead = q->qtail = NULL;q->size = 0;
}3.运用栈理解一道题
首先，我们已经实现好了栈，接下来，我们可以直接使用栈的函数
对于这道题，我们应该先开辟一个栈(st),我们可以先将题目给定(s)的 '(' 、'[' 、 '{' 这三个左括号导入栈(st)中。 然后，我们可以使用STTop取出栈(st)中的数据，进行对栈(s)的左右括号的匹配，如果匹配不成功，则返回false，直到栈(s)为空时，过程结束。代码如下所示：
bool isValid(char* s)
{ ST st;STInit(&st);while(*s){if(*s =='(' || *s == '[' || *s == '{'){STPush(&st,*s); //入栈：让字符串s的括号进入栈st中}else{if(STEmpty(&st)){STDestory(&st);return false;}char top = STTop(&st);//STtop为取栈中数据的函数STPop(&st);//pst->top--;//检验不匹配if((top == '(' && *s != ')')||(top == '[' && *s != ']')||(top == '{' && *s != '}')){STDestory(&st);return false;}}++s;}bool ret = STEmpty(&st);STDestory(&st);return ret;
}4.使用两个队列实现一个栈
为了加深栈和队列的理解，我们来分析这道题
依照题意，我们创建一个栈(MyStack),包含两个队列(Queue q1\q2) ；
然后，我们需要为新创建的栈开辟新的空间(obj)，并将其中的两个队列q1、q2初始化；
设计一个函数myStackPush，用于非空队列尾部添加数据；
在函数myStackPop中，我们将非空队列的size-1个元素移动至空队列中；
然后，使用mytStackTop函数取得栈顶元素；
为了检测我们实现的栈是否为空，我们可以直接使用QueueEmpty返回这两个队列q1、q2；
最后，当我们释放内存的时候，我们应先将这两个队列q1、q2先释放，最后再释放obj这个指向栈(MyStack)的指针。
大致结构如下图所示：
代码实现见下图分析：
typedef struct {Queue q1;Queue q2;//新创建的栈有两个队列q1，q2
} MyStack;//创建新的栈
MyStack* myStackCreate() {MyStack* obj = (MyStack*)malloc(sizeof(MyStack));QueueInit(&(obj->q1));QueueInit(&(obj->q2));return obj;
}//在非空队列尾部添加数据x
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&(obj->q1))){QueuePush(&(obj->q1),x);}else{QueuePush(&(obj->q2),x);}
}int myStackPop(MyStack* obj) {//假设法Queue* empty = &(obj->q1);Queue* nonEmpty = &(obj->q2);if(!QueueEmpty(&(obj->q1))){nonEmpty = &(obj->q1);empty = &(obj->q2);}while(QueueSize(nonEmpty)>1)//把前size-1个元素导走{QueuePush(empty,QueueFront(nonEmpty));//将有非空队列的队列头部元素 导入 空队列中QueuePop(nonEmpty);//然后，删除非空队列的头部元素}int top = QueueFront(nonEmpty);//再取出非空队列的队头元素QueuePop(nonEmpty);//将非空元素的最后一个队头导出队列return top;//此时top就是最开始的最后一个数据：即栈顶数据
}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));//boolean empty() 如果栈是空的，返回 true ；否则，返回 false
}void myStackFree(MyStack* obj) {QueueDestroy(&(obj->q1));QueueDestroy(&(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);
*/ 
