目录
栈
栈的概念及结构
栈的具体实现
函数1：void StackInit(Stack* pst); //初始化栈
函数2：void StackDestory(Stack* pst); //销毁栈
函数3：void StackPush(Stack* pst,STDataType x); //压栈
剩余函数：
队列
队列的具体实现
函数1：void QueueInit(Queue* q); // 初始化队列
函数2：void QueuePush(Queue* q, QeleType data);// 队尾入队列
函数3：void QueuePop(Queue* q);// 队头出队列
剩下的函数：
栈
栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
压栈动画：
(emmm导出之后可能有些问题，存在重影)
出栈和入栈是刚刚好相反的。我们在这里就不做过多的赘述了。
所以来说，栈的操作是比较简单的。
我们来简单实现一下吧
栈的具体实现
对于栈而言，我们需要的是有一下这么几个东西：
栈顶指针；栈的容量。
所以，我们就能定义出这样的一个“栈结点”
那么我们具体实现的思路是怎样的呢？
我们可以来说明一下：
注意，我们这里的栈顶指针是在最后一个元素的上一个位置。
每当一个元素进来的时候，即压栈的时候，如果capacity > size,那么栈顶指针就向上移动，接着让元素进来就可以。
出栈的过程刚好相反。
我们来看代码实现：
#include<stdio.h> #include<stdbool.h> #include<assert.h> #include<stdlib.h> typedef int STDataType; //上面的都是顺带的内容；主要是头文件和重新命名 typedef struct Stack { STDataType* a; int top; int capaticy; }Stack;
由于栈比较简单，我们主要实现以下几个函数就可以：
void StackInit(Stack* pst); void StackDestory(Stack* pst); void StackPush(Stack* pst,STDataType x); void StackPop(Stack* pst); STDataType StackTop(Stack* pst); bool StackEmpty(Stack* pst); int StackSize(Stack* pst);
具体这些函数是干什么用的，请见下文：
函数1：void StackInit(Stack* pst); //初始化栈
void StackInit(Stack* pst) { assert(pst); //断言 pst->a = (STDataType*)malloc(sizeof(STDataType)*4); //开辟新空间 pst->top = 0; //让其栈顶指针指向0； pst->capaticy = 4; //容量给上开辟的值 }
函数2：void StackDestory(Stack* pst); //销毁栈
void StackDestory(Stack* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capaticy = pst->top = 0; }
函数3：void StackPush(Stack* pst,STDataType x); //压栈
void StackPush(Stack* pst, STDataType x) { assert(pst); //断言 if (pst->top == pst->capaticy) //如果容量和元素的个数一样 { //那就增容 STDataType* tmp = (STDataType*)realloc(pst->a, 2*sizeof(STDataType)*pst->capaticy); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } pst->a = tmp; pst->capaticy =pst->capaticy * 2; } //到此都是增容的内容 pst->a[pst->top] = x; //将数据域放进去 pst->top++; //栈顶指针向上移动一位 }
剩余函数：
后面几个函数我们就一块来看吧：（因为实在是太简单了
void StackPop(Stack* pst) //删除栈顶元素，即出栈 { assert(pst); assert(!StackEmpty(pst)); //两步断言 pst->top--; //直接top--即可 } STDataType StackTop(Stack* pst) //获取栈顶元素 { assert(pst); assert(!StackEmpty(pst)); //两步断言 return pst->a[pst->top - 1]; //直接return 栈顶 } bool StackEmpty(Stack* pst) //判断栈是否为空 { assert(pst); //断言 return pst->top == 0; //return 判断top是否为0 } int StackSize(Stack* pst) { assert(pst); //断言 return pst->top; //返回栈顶指针的下标；这里不需要减1，因为刚好是一一对应的。 }
随便测试一下：
#include"Stack.h" void TestStack() { Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); StackPush(&st, 6); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } StackDestory(&st); } int main() { TestStack(); return 0; }
运行截图：
由于实在实在是太简单，我们就讲到这里。等日后做题的时候再来叙叙。
队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
的特点。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
如下面的草图
对于队列来说，我们仍然建议的是用链式结构来存储。
可以这么认为：队列就是特殊的链表。
在这里的，我们讲解的链表会非常的简单，我们就能带过就带过了。
队列的具体实现
队列的节点是和链表差不多，不过，我们又重新定义了一个结构体用于囊括首位指针。
因为队列相较于链表的特殊之处正是在于，其只能从一边进，从另一边出。
所以，我们定义以下的结构体：
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int QeleType; typedef struct QueueNode { struct QueueNode* next; QeleType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue;
我们主要讲解这样几个接口：
// 初始化队列 void QueueInit(Queue* q); // 队尾入队列 void QueuePush(Queue* q, QeleType data); // 队头出队列 void QueuePop(Queue* q); // 获取队列头部元素 QeleType QueueFront(Queue* q); // 获取队列队尾元素 QeleType QueueBack(Queue* q); // 获取队列中有效元素个数 int QueueSize(Queue* q); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q); // 销毁队列 void QueueDestroy(Queue* q);
还是老样子，我们一边给出函数，一边来分析。
函数1：void QueueInit(Queue* q); // 初始化队列
void QueueInit(Queue* q) { assert(q); q->head = q->tail = NULL; }
so easy的。
函数2：void QueuePush(Queue* q, QeleType data);// 队尾入队列
类似于单向不带头不循环的尾插
// 队尾入队列 void QueuePush(Queue* q, QeleType data) { assert(q);//断言，其为非空 QNode* newnode = (QNode*)malloc(sizeof(QNode));//动态开辟新的空间 if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = data; //将data的值赋给数据域 newnode->next = NULL; //指针域先赋值为空 if (q->tail == NULL) { q->head = q->tail = newnode; //如果只有一个节点，那就直接将其给newnode } else { q->tail->next = newnode; //如果不是，那就先将tail的next给上newnode q->tail = newnode; //再将tail给上newnode } }
函数3：void QueuePop(Queue* q);// 队头出队列
void QueuePop(Queue* q) { assert(q); if (q->head->next == NULL) //同样的道理，如果只有一个节点，那就直接置空就好了 { free(q->head); q->head = q->tail = NULL; } else //如果不是，那就将head的next存储起来， { //然后free head，然后将next的位置给head QNode* next = q->head->next; free(q->head); q->head = next; } }
由于剩下的函数都比较简单，我们还是老样子，放在一块讲解
剩下的函数：
// 获取队列头部元素 QeleType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->head->data; } // 获取队列队尾元素 QeleType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->tail->data; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { int size = 0; QNode* cur = q->head; while (cur) { size++; cur = cur->next; } return size; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q) { assert(q); return q->head == NULL; } // 销毁队列 void QueueDestroy(Queue* q) { QNode* cur = q->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->head = q->tail = NULL; }
笔者觉得，这个真的没什么好说的，如果对链表掌握到位的话，那么上面的这些还是就是小菜了。
基本都是一样的。
最后，我们来玩一玩吧。
void TestQueue() { Queue q ; QueueInit(&q); //初始化队列 QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); //尾插 while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); //依次去出队头打印 QueuePop(&q); //删除队头 } QueueDestroy(&q); //销毁队列 } int main() { TestQueue(); return 0; }
运行一下：
可以看到，程序按照我们想要的运行起来了。我们大功告成。
对于栈和队列，我们在这里只是把 其底层的原理简单的说一下，等到C++说到STL的时候，我们还会详细地说。
