前言
栈是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。(队列为FIFO)
本文目的：
1.掌握栈的特点及其描述方法
2.掌握链式存储结构实现一个栈
3.掌握链栈的各种基本操作
4.掌握栈的典型应用的算法
栈子系统题目要求：
1.设计一个选择式菜单。
2.设计一个整型数据元素的链栈。
3.编写入栈、出栈和显示栈中全部元素的程序。
4.编写一个把十进制数转换成八进制数的应用程序。
一、栈的顺序结构及其实现
1：顺序栈概念理解
既然栈是线性表的特例，那么栈的顺序存储其实就是线性表的顺序存储的简化，也叫顺序栈。线性表是用数组实现的，那么顺序栈也可以用数组来实现。接下来我们来模拟数组存放数据的情况。
最初，栈是"空栈"，即数组是空的，top 值为初始值 -1(这样当存放数据时top的值总是与其对应的数组角标相等)，如下图所示
首先向栈中添加元素 1，我们默认数组下标为 0 一端表示栈底，因此，元素 1 被存储在数组 a[1] 处，同时 top 值 +1，如下图所示
采用以上的方式，依次存储元素 2、3 和 4，最终，top 值变为 3，如下图所示
2：入栈(压栈)实现方法
根据上面的概念我们可以得出，顺序栈可以简化为一个存放数据的数组，以及指向栈顶位置的top指针(不是真的指针，而是代表一个指向栈顶位置)。
#pragma once #include<iostream> #include <cstdio> #include<cstdlib> typedef int Status; typedef int ElemType; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSIZE 10 #define make (struct student*)malloc(sizeof(struct student)); using namespace std; typedef struct { ElemType stack[MAXSIZE];//构建一个顺序栈存储元素 int top; //默认值为-1而不是0 -1代表代表的是栈空 }Stack; Status push_stack(Stack* s, ElemType e) //入栈 { if (s->top >= MAXSIZE - 1) //栈满退出 return ERROR; s->top++; //增加一位 cout << "要插入的数据是" << e << endl; s->stack[s->top] = e;//赋值 return OK; //返回成功结果 }
3：出栈(弹栈)及其实现方法
其实，top 变量的设置对模拟数据的 “入栈” 操作没有实际的帮助，它是为实现数据的 “出栈” 操作做准备的。
比如，将 下1图 中的元素 2 出栈，则需要先将元素 4 和元素 3 依次出栈。需要注意的是，当有数据出栈时，要将 top 做 -1 操作。因此，元素 4 和元素 3 出栈的过程分别如 下1图 和 下2图 所示：
Status pop_stack(Stack* s, ElemType* e) //出栈 { if (s->top == -1) //空栈 return ERROR; *e = s->stack[s->top]; //取得要删除的值 这里没有-1是因为栈的起始数量是-1哦 cout << "要删除的数据是" << *e << endl; s->top--; //弹栈 return OK; }
4：顺序栈输出其数据
void show_stack(Stack s) { int j; j = s.top; //得到目前已有的数据个数 while (j > -1) { cout << "第"<<j<<"个元素是" << s.stack[j] << endl; j--; } cout << "栈已空" << endl; }
5：主函数
int main() { Stack* head=(Stack*)malloc(sizeof(Stack));//初始化一个栈 head->top = -1;//初始top指针为-1 代表空栈 ElemType e; push_stack(head, 10); push_stack(head, 20); push_stack(head, 30); push_stack(head, 40); show_stack(*head); pop_stack(head, &e); show_stack(*head); }
二、栈的链式存储结构
1.链栈概念理解
链栈的实现思路同顺序栈类似，顺序栈是将数顺序表（数组）的一端作为栈底，另一端为栈顶；链栈也如此，通常我们将链表的头部作为栈顶，尾部作为栈底，如下图
将链表头部作为栈顶的一端，可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。
链表的头部作为栈顶，意味着：
在实现数据"入栈"操作时，需要将数据从链表的头部插入；
在实现数据"出栈"操作时，需要删除链表头部的首元节点；
2.初始化链栈
链栈的初始化与链表的初始化类似，直接上代码
#pragma once #include<iostream> #include <cstdio> #include<cstdlib> typedef int Status; typedef int ElemType; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSIZE 10 #define make (struct student*)malloc(sizeof(struct student)); using namespace std; typedef struct StackNode { ElemType data; //数据 int count; //记录当前栈内数据个数 struct StackNode* next; //指向下一个节点指针 }StackNode; StackNode* init_stack(ElemType e) { StackNode* head = (StackNode*)malloc(sizeof(StackNode));//s是指向结构体StackNode的指针 head->next = NULL; head->data = e; cout << "栈底元素为" << e << endl; head->count = 1; //初始化数据数量为1,头指针自身也算一个数据 return head; }
3.链栈元素入栈
例如，将元素 1、2、3、4 依次入栈，等价于将各元素采用头插法依次添加到链表中，每个数据元素的添加过程如图所示
也就是头指针先指向空，之后随着数据的插入，先插入的数据存在于栈底，而头指针永远指向着栈顶，也就是最新插入的数据。其实和链表的数据插入差不多，只不过不能随意插入位置，而只能插在栈头，当然这样相对于链表反而更简单了。
StackNode* push_stack(StackNode* head, ElemType e)//入栈 在栈L中插入数据e { //StackNode* p=head;//临时指针p StackNode* s = (StackNode*)malloc(sizeof(StackNode));//s是指向结构体StackNode的指针 s->data = e; //添加数据e cout << "插入元素" << e << endl; s->count = ++head->count;//元素数量增加 cout <<"当前元素个数为" << s->count << endl; s->next = head; //指向上一元素 head = s; //头指针指向栈顶 return head;//成功返回 }
4.链表元素出栈
下图所示的链栈中，若要将元素 3 出栈，根据"先进后出"的原则，要先将元素 4 出栈，也就是从链表中摘除，然后元素 3 才能出栈，整个操作过程如图所示：
链栈删除元素的情况也就是栈顶的数据被删除，类似于链表元素的头指针指向下一个数据，然后释放原有头指针指向的数据。即head直接指向下一个节点，然后直接释放原先节点指向的数据。
StackNode* pop_stack(StackNode* head, ElemType* e) { StackNode* p; //临时指针 if (head == NULL) //判断链栈非空 return ERROR; *e = head->data; //取得要删除元素 也就是栈顶元素 cout << "要删除的元素是" << *e << endl;//输出要删除的元素 p = head->next; //p指向将被删除数据的下一个节点，以便头指针移位 free(head); //释放被删除数据的空间 head = p; //头指针指向新位置 head->count--; //头指针指向的数据减少 cout << "当前元素个数为" << head->count << endl; return head; }
5.显示链栈元素
我们在链栈里通过count来记录了链栈中当前元素的数量，一次可以通过count来判断是否还有数据可以输出。
void show_stack(const StackNode *head) { //使用const可以确保head指向的数据不被修改 int num = head->count;//取得元素个数 for (int i = 1; i <= num; i++) { cout << "第" << i << "个元素是" << head->data<<endl;//输出数据 从上至下输出 head = head->next; //指向下一个数据 } }
6.主函数
int main() { StackNode* head; ElemType e; head = init_stack(1); head = push_stack(head, 2); head = push_stack(head, 3); head = push_stack(head, 4); head = pop_stack(head, &e); head = pop_stack(head, &e); head = pop_stack(head, &e); //head = pop_stack(head, &e); //再删除一次就会报错 这是由于head不存在 show_stack(head); }
三、栈子系统
链栈的出栈和入栈上面已经交代清楚了比较难的就是如何把十进制的数据用八进制形式来输出。接下来提供一种方法。
可以发现当数据不能再被整除时，此时形成的数据，就是十进制转换为八进制的结果，例如1201%8=2···2···6··1，也就是2261，通过计算器可以发现这是正确的。那么如何得到每一次数据的最简余数呢------递归。下面来看代码：
void change(int m) //用递归来将十进制换为八进制 { if (0 == m) return; int tmp = m % 8; m = m / 8; change(m); printf("%d", tmp); }
比较简单，不解释了。
那么解决了这个进制转换问题后，栈子系统的代码便直接可以轻松写出。
#include <algo.h> typedef struct StackNode { ElemType data; //数据 int count; //记录当前栈内数据个数 struct StackNode* next; //指向下一个节点指针 }StackNode; StackNode* init_stack(ElemType e) { StackNode* head = (StackNode*)malloc(sizeof(StackNode));//s是指向结构体StackNode的指针 head->next = NULL; head->data = e; cout << "栈底元素为" << e << endl; head->count = 1; //初始化数据数量为1,头指针自身也算一个数据 return head; } StackNode* push_stack(StackNode* head, ElemType e)//入栈 在栈L中插入数据e { //StackNode* p=head;//临时指针p StackNode* s = (StackNode*)malloc(sizeof(StackNode));//s是指向结构体StackNode的指针 s->data = e; //添加数据e cout << "插入元素" << e << endl; s->count = ++head->count;//元素数量增加 cout <<"当前元素个数为" << s->count << endl; s->next = head; //指向上一元素 head = s; //头指针指向栈顶 return head;//成功返回 } StackNode* pop_stack(StackNode* head, ElemType* e) { StackNode* p; //临时指针 if (head == NULL) //判断链栈非空 return ERROR; *e = head->data; //取得要删除元素 也就是栈顶元素 cout << "要删除的元素是" << *e << endl;//输出要删除的元素 p = head->next; //p指向将被删除数据的下一个节点，以便头指针移位 free(head); //释放被删除数据的空间 head = p; //头指针指向新位置 head->count--; //头指针指向的数据减少 cout << "当前元素个数为" << head->count << endl; return head; } void show_stack(const StackNode *head) { //使用const可以确保head指向的数据不被修改 int num = head->count;//取得元素个数 cout << "元素总个数为" << num << endl; for (int i = 1; i <= num; i++) { cout << "第" << i << "个元素是" << head->data<<endl;//输出数据 从上至下输出 head = head->next; //指向下一个数据 } } void change(int m) //用递归来将十进制换为八进制 { if (0 == m) return; int tmp = m % 8; m = m / 8; change(m); printf("%d", tmp); } void transformation_stack(StackNode* head) { int times = 1; cout << "元素个数" << head->count << endl; int num = head->count;//取得当前元素个数 for(times;times<=num;times++) { change(head->data);//调用转换函数 cout << endl;//输出换行符 head = head->next;//指向下一个数据 } } int main() { int choose; ElemType e; cout << "输入栈底元素" << endl; cin >> e; StackNode* head = init_stack(e);//初始化链栈 cout << "*******************" << endl; cout << "*1 ……入栈 *" << endl; cout << "*2 ……出栈 *" << endl; cout << "*3 ……显示 *" << endl; cout << "*4 ……数制转换 *" << endl; cout << "*0 ……返回 *" << endl; cout << "*******************" << endl; while (1) { cout << "请选择功能" << endl; scanf("%d", &choose); switch (choose) { case 1: { ElemType e; cout << "输出要插入的数据" << endl; cin >> e; head = push_stack(head, e); cout << "插入成功" << endl; break; } case 2: { ElemType e; head = pop_stack(head,&e); cout << "删除成功" << endl; break; } case 3: { show_stack(head); break; } case 4: { transformation_stack(head); break; } case 0: { cout << "程序结束" << endl; system("pause"); exit(0); //return 0; } default: break; } } }
完整代码下载：
四、链栈与顺序栈优缺点对比
对比顺序栈和链栈，它们的时间复杂度是一样的，都是O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间的浪费问题，但是它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些的内存开销，但对于栈的长度无限制。所以题目的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预测，有时候小，有时候很大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会好一些。
