数据结构（四）栈
栈（Stack）是一种特殊的线性表，是一种操作受限的线性表，所有的插入和删除操作都限定在表尾进行的，是一种后进先出的线性表。
假设栈S = (A1,A2,......,An)，从A1开始入栈直到An结束，则称A1为栈底元素，An为栈顶元素。要是出栈的话又会从最后进栈的An开始，所以可以看出这种结构是后进先出的（简称LIFO结构），如下图所示：
图1 栈示意图
1 栈的表示和实现
和线性表类似，栈也有两种存储表示方式：顺序栈和链式栈。
1.1 顺序栈
定义：
#define MAXSIZE 100
typedef struct
{
DataType Elem[MAXSIZE];
uint8 top; /* 栈顶指针 */
}sqstack;
定义一个sqstack *S; 则：
栈满的条件:S -> top == MAXSIZE - 1
栈空的条件：S -> top == -11.2 链式栈
图2 链式栈示意
定义：
typedef struct
{
DataType Data; /* 数据域 */
struct node *next; /* 指针域 */
}node,*linklist;2
栈的基本算法
由于栈的基本操作除了只能在表的一端进行操作，其他和线性表基本一致，所以这部分内容不提供具体代码或用伪代码来表示，读者可以自行练习。
2.1 顺序栈的基本算法
（1）进栈：
- 判断栈是否满了
- 栈顶指针 + 1：S -> top ++;
- x入栈：S -> Elem[S -> top] = x;
（2）出栈：
- 判断栈是否为空
- 栈顶指针 - 1，出栈
（3）栈的遍历：
void StackTraverse(sqstack *S)
{
while((S -> top) > -1)
{
x = S -> Elem[S -> top];
S -> top --;
printf(x);
}
}2.2 链式栈的基本算法
2.2.1 进栈：
算法思想：
（1）动态分配存储空间
p = (linklist)malloc(sizeof(node));
（2）给数据成员赋值
p -> Data = x;
（3）给指针成员赋值
p -> next = top;
（4）修改栈顶指针
top = p;
代码实现：
void StackPush(linklist top)
{
linklist p;
p = (linklist)malloc(sizaof(node));
p -> Data = x;
p -> next = top;
top = p;
}2.2.2 出栈：
算法思想：
（1）判断栈是否为空
if(top == NULL)
（2）将p指向栈顶
p = top;
（3）栈顶指针下移
top = top -> next;
（4）释放存储空间
free(p);
代码实现：
void StackPop(linklist top)
{
linklist p;
if(top == NULL)
{
printf("Stack is empty.");
}
else
{
p = top;
top = top -> next;
free(p);
}
}3
栈的应用——数制转换
十进制数转换成其他d进制数，是计算机实现计算的基本问题，在学校C语言课程中我们学过十进制数转换二进制数有一个口诀，叫做“除2取余，倒计数”，向其他进制转换也是一样的过程，把其总结为一个公式如下
N = (N / d) * d + N % d
例如：十进制数1348转换为八进制数为2504，转换过程如下：
图3 十进制数转换为八进制数
从上述过程可以看出，十进制数转换为八进制数输出时，符合“后进先出”的规则，与栈的操作是一样的。
对于任意一个非负十进制数，打印其对应的八进制数，代码示意如下：
void ConvertDecToOct(uint8 DecNumber)
{
InitStack(); /* 构造空栈 */
while(DecNumber)
{
Push(S,DecNumber % 8);
DecNumber = DecNumber / 8;
}
while(!isStackEmpty(S))
{
Pop(S,OctNumber);
printf("%d",OctNumber);
}
}腾讯云开发者
