1.栈
1.1 栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
数据进栈出栈遵循后进先出的原则：
下面看两道例题：
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
答案是B。
2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1答案是C。
这道题说可以在进栈的过程中出栈，ABD不用说，只有C，先出栈的是3，说明此时栈里面1和2肯定还在，而1不可能在2之前出栈，所以选C。
1.2 栈的实现
实现栈有两种方式，一种是数组栈，一种是链式栈：
这里我们采用数组栈，因为数组在尾插的代价比较小。
首先，我们来定义一个结构体：
typedef int STDatatype; typedef struct Stack { STDatatype* a; int top;//栈顶元素位置 int capacity;//容量 }ST;
下面我们来实现栈：
初始化栈：
初始化很简单，但要注意断言pst是否为空。（pst是结构体变量的地址，永远不为空，所以需要断言）
void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0;//指向栈顶元素的下一个位置 pst->capacity = 0; }
入栈：
入栈时，我们要为栈开辟空间，然后才能插入数据。由于只有入栈需要开辟空间，所以这里我们并没有封装开辟空间的函数，直接在入栈函数里面开辟空间就行。
当pst->top=pst->capacity=0时，说明此时还没有就开辟空间，所以我们给它开辟4个字节大小。下次再进去，不等于0，空间就增容到上次的2倍。
void STPush(ST* pst, STDatatype x) { //开辟空间 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : (pst->capacity) * 2; STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity); if (tmp == NULL) { perror("malloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } //插入 pst->a[pst->top] = x; pst->top++; }
判空函数：
bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; }
出栈：
出栈只需要将pst->top--即可，但是注意要断言此时的栈不能为空。
STEmpty函数是用来判断栈是否为空，它的返回值类型是bool型，bool型返回true或false，当pst->top=0时，说明此时栈为空，返回true，取反!true为假，断言报错。
bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; }
获取栈顶元素：
直接返回栈顶元素即可，pst->top是栈顶元素的下一个位置，所以要返回pst->top-1处的值。
STDatatype STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; }
获取栈中有效元素的个数：
int STSize(ST* pst) { assert(pst); return pst->top; }
销毁栈：
因为是数组栈，所以直接free数组名即可。
void STDestory(ST* pst) { assert(pst); assert(!STEmpty(pst)); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; }
完整代码：
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" STTest1() { ST st; STInit(&st); STPush(&st, 1); STPush(&st, 2); printf("%d ", STTop(&st)); STPop(&st); STPush(&st, 3); STPush(&st, 4); STPush(&st, 5); while (!STEmpty(&st)) { printf("%d ", STTop(&st)); STPop(&st); } STDestory(&st); } int main() { STTest1(); return 0; }
Stack.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDatatype; typedef struct Stack { STDatatype* a; int top; int capacity; }ST; //初始化栈 void STInit(ST* pst); //入栈 void STPush(ST* pst, STDatatype x); //出栈 void STPop(ST* pst); //判空 bool STEmpty(ST* pst); //获取栈顶元素 STDatatype STTop(ST* pst); //获取栈中有效元素个数 int STSize(ST* pst); //销毁栈 void STDestory(ST* pst);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" //初始化栈 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0; pst->capacity = 0; } //入栈 void STPush(ST* pst, STDatatype x) { //开辟空间 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : (pst->capacity) * 2; STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity); if (tmp == NULL) { perror("malloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } //插入 pst->a[pst->top] = x; pst->top++; } //判空函数 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } //出栈 void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } //获取栈顶元素 STDatatype STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } //获取栈中有效数据的个数 int STSize(ST* pst) { assert(pst); return pst->top; } //销毁栈 void STDestory(ST* pst) { assert(pst); assert(!STEmpty(pst)); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; }
测试：
2. 队列
2.1 队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列中的元素遵循先进先出的原则
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列很好理解，就像在食堂打饭一样，先排进队的先打饭，打完饭先走，
2.2 队列的实现
要实现队列，最好使用链表的方式，因为数组头删效率比较低。
我们先来定义一个结构体：
typedef int QDatatype; typedef struct QueueNode { struct QueueNode* next; QDatatype data; }QNode;
很明显，这是个单链表，我们要实现队列，还要知道队列的头和尾，以及队列中有效数据的个数，所以索性把它们也定义成一个结构体：
typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue;
phead就是队列的头，ptail就是队列的尾
下面我们来实现队列吧。
队列的初始化：
//初始化队列 void QueueInit(Queue* pq) { pq->phead = NULL; pq->ptail = NULL; pq->size = 0; }
队尾入队列：
和栈相似，在入队函数内部开辟空间，这其实就是单链表的尾插（不带哨兵位）。
//队尾入队列 void QueuePush(Queue* pq, QDatatype x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail=newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; }
判空函数：
bool QueueEmpty(Queue* pq) { assert(pq); return pq->size ==0 ; }
队头出队列：
这相当于单链表的头删，注意分情况，一个节点和多个节点要单独写，同时要用判空函数QueueEmpty()断言队列是否为空。
//队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //一个节点 //多个节点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail= NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; }
获取队列头部元素：
//获取队列头部元素 QDatatype QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; }
获取队列尾部元素：
//获取队列尾部元素 QDatatype QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; }
获取队列中有效元素个数：
//获取队列中有效元素个数 int Queuesize(Queue* pq) { assert(pq); return pq->size; }
销毁队列：
//销毁队列 void DestoryQueue(Queue* pq) { assert(pq); while (pq->phead) { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
完整代码：
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" QueueTest1() { Queue pq; QueueInit(&pq); QueuePush(&pq, 1); QueuePush(&pq, 2); QueuePop(&pq); printf("%d ", QueueFront(&pq)); QueuePush(&pq, 3); QueuePush(&pq, 4); printf("%d ", QueueBack(&pq)); while (!QueueEmpty(&pq)) { printf("%d ", QueueFront(&pq)); QueuePop(&pq); } DestoryQueue(&pq); } int main() { QueueTest1(); return 0; }
Queue.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> typedef int QDatatype; typedef struct QueueNode { struct QueueNode* next; QDatatype data; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //初始化队列 void QueueInit(Queue* pq); //队尾入队列 void QueuePush(Queue* pq, QDatatype x); //队头出队列 void QueuePop(Queue* pq); //获取队列头部元素 QDatatype QueueFront(Queue* pq); //获取队列尾部元素 QDatatype QueueBack(Queue* pq); //获取队列中有效元素个数 int Queuesize(Queue* pq); //判空 bool QueueEmpty(Queue* pq); //销毁队列 void DestoryQueue(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" //初始化队列 void QueueInit(Queue* pq) { pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } //队尾入队列 void QueuePush(Queue* pq, QDatatype x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail=newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } //判空函数 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size ==0 ; } //队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //一个节点 //多个节点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail= NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } //获取队列头部元素 QDatatype QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } //获取队列尾部元素 QDatatype QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } //获取队列中有效元素个数 int Queuesize(Queue* pq) { assert(pq); return pq->size; } //销毁队列 void DestoryQueue(Queue* pq) { assert(pq); while (pq->phead) { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
测试：
以上就是栈和队列的实现了，下一节我们讲几个栈和队列QJ题，
未完待续。。。
