栈的知识基础

定义

作为一种限定性线性表被定义时，则是将线性表中的插入与删除操作限制为仅能发生在列表的一端。该数据结构中的两端分别被称为栈顶与栈底的位置。
其中，在栈的操作中被称作进栈或入栈的行为是指元素被添加到顶端位置上；而出栈或退栈则是指元素从顶端位置上被移除的操作。
其特点在于遵循先进后出的原则（即后进的数据会被优先于先进数据进行处理）。

顺序栈

顺序存储结构的实现过程如下：其中一种方法是利用一组地址连续的存储单元依次存放自下而上的数据元素，并采用一个位置索引变量top（称为栈顶指针）来动态指示当前顶端元素在顺序数组中的具体位置。通常情况下，默认设置为\text{top} = -1以表示空的状态。

C语言描述：

    #define Stack_Size 50
    typedef struct
    {
    	StackElementType elem[Stack_Size];
    	int top;
    }SeqStack;

基本操作：

1. InitStack(S)初始化一个新的栈；

    void InitStack(SeqStack *S)
    {
    	S->top=-1;
    }

2. Empty(S)栈的非空判断，栈S不空，返回true，否则返回false；