【数据结构】栈和队列
目录
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->a pst->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); */
