撰写
大家好，今天的内容是数据结构中关于栈的部分。前两篇文章分别介绍了线性结构的两种存储方式：数组和链表。我们先来总结一下数组和链表的区别
先来看看数组：在内存中，数组是一块连续的区域。 拿看电影来说，平常和朋友去电影院看电影，和朋友几个人在电影院中必须坐在一起。数组的特点是，在使用数组之前，必须先申请内存空间。这样就存在一种空间浪费的情况，比如几个人看电影，预定了5个座位，可结果只来了3个人，最后两个座位就浪费掉了。随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到下一个地址的数据。但不利于扩展，数组定义的空间不够时要重新定义数组。
其次是链表：在内存中，链表的每个结点不要求连续。还用看电影来举例，这时不要求几个人坐在一起，他们可以坐在电影院的任何位置。但是， 第一个人知道第二个人的座位号，第二个人知道第三个人的座位号。换句话说，每一个数据都保存了下一个数据的内存地址，通过这个地址可以找到下一个数据。
知道了数组和链表的不同，我们就可以把它们应用到实际。栈(Stack)是一种可以实现“先进后出”的存储结构或存储方式。栈类似于没有盖的箱子，当每次往里放书时，最先放进去的总是最后才能拿出来，最后放进去的总是在箱子的顶部。并且规定，不能从箱子的底部放书和拿书。满足这个条件的我们称之为“栈”。
栈分为静态栈与动态栈。静态栈是以“数组”为内核的，动态栈是以”链表”为内核的。这里讨论动态栈。
栈主要有两种操作，出栈和压栈（入栈）
创建一个栈，首先要知道栈里有什么。箱子有顶部和底部，那么栈就有栈顶和栈底；用一个指针指向栈顶，另一个指向栈底。为了方便今后操作整个栈，在栈的底部加一个没有实际意义的结点，并且将栈底指针指向它。
栈用一个结构体来表示，它有两个成员分别是栈顶指针和栈底指针。栈里的每一个结点用一个包含数据域和指针域的结构体来表示，对应到代码，如下所示：
// 结点
typedef struct Node {
int data;
struct Node * pNext;
}NODE, * PNODE;
// 栈
typedef struct Stack {
PNODE pTop;
PNODE pBottom;
}STACK, * PSTACK;这里的pTop指向栈顶元素，pBottom指向最后一个有效元素的下一个元素。现在如果执行一句STACK S内存中的情景为：
这样还不能称为一个栈，栈里必须有元素，也就是要有一个结点。首先初始化出来一个空栈，空栈里只有一个没有意义的栈底元素，也就是最后一个有效元素的下一个元素。此时，pTop和pBottom均应指向该元素，因为，此时它既是栈顶也是栈底。我们希望一个空栈应该是这样的：
代码如下：
pS->pTop = (PNODE) malloc(sizeof(NODE)); // 创建了一个空结点
if(NULL == pS->pTop) {
printf("动态内存分配失败！n");
exit(-1);
}else {
pS->pBottom = pS->pTop;
pS->pTop->pNext = NULL; //pS->pBottom->pNext = NULL
}这样，就完成了初始化栈的操作。
void init(PSTACK);
void push(PSTACK, int ); //压栈
void traverse(PSTACK); //遍历
bool empty(PSTACK); //是否为空
bool pop(PSTACK, int *); //出栈
void clear(PSTACK); //清空
这里，我写了几个栈的基本操作，实现如下：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
// 结点
typedef struct Node {
int data;
struct Node * pNext;
}NODE, * PNODE;
typedef struct Stack {
PNODE pTop;
PNODE pBottom;
}STACK, * PSTACK;
// 函数定义
void init(PSTACK);
void push(PSTACK, int ); //压栈
void traverse(PSTACK); //遍历
bool empty(PSTACK); //是否为空
bool pop(PSTACK, int *); //出栈
void clear(PSTACK); //清空
int main() {
STACK S;
init(&S); // 初始化栈
traverse(&S); //遍历
return 0;
}
void init(PSTACK pS) {
pS->pTop = (PNODE) malloc(sizeof(NODE)); // 创建了一个空结点
if(NULL == pS->pTop) {
printf("动态内存分配失败！n");
exit(-1);
}else {
pS->pBottom = pS->pTop;
pS->pTop->pNext = NULL; //pS->pBottom->pNext = NULL
}
}
void push(PSTACK pS, int val) {
PNODE pNew = (PNODE)malloc(sizeof(NODE));
pNew->data = val;
pNew->pNext = pS->pTop;
pS->pTop = pNew;
return;
}
void traverse(PSTACK pS) {
PNODE p = pS->pTop;
/* while(NULL != p->pNext) {
printf("%d ",p->data);
p = p->pNext;
}*/
while(p != pS->pBottom) {
printf("%d ",p->data);
p = p->pNext;
}
printf("n");
return;
}
bool empty(PSTACK pS) {
if(pS->pTop == pS->pBottom) {
return true;
}else {
return false;
}
}
bool pop(PSTACK pS, int * pVal) {
if (empty(pS)) {
return false;
}else {
PNODE r = pS->pTop;
* pVal = r->data;
pS->pTop = r->pNext;
free(r);
r = NULL;
return true;
}
}
void clear(PSTACK pS) {
if(empty(pS)) {
return;
}else {
PNODE p = pS->pTop;
PNODE q = NULL;
while(p != pS->pBottom) {
q = p->pNext;
free(p);
p = q;
}
pS->pTop = pS->pBottom;
}
}原文始发于微信公众号（代码墙）：数据结构学习笔记(三)