栈是限定仅在表尾进行插入和删除操作的线性表。
我们将允许插入和删除的一端称为栈顶，另一端称为栈底。
不含任何元素的栈称为空栈。
栈又被称为先进后出的线性表。
也就是说栈是一个特殊的线性表，其只在线性表的表尾进行添加删除数据操作，也就是说上边提到的栈底是固定的，添加删除操作只在栈顶进行。
栈的写入操作，叫做进栈，也称压栈或入栈。
栈的删除操作，叫做出栈，也称弹出栈。
栈限定了只在线性表的末尾进行数据写入删除操作，但是这并不意味着最先进栈的元素一定要最后出栈，这个要看具体情况，举个书上的小例子
【进栈出栈的变化形式】
如果3个整数1,2,3依次入栈，会有哪些出栈次序？
第一种：1-2-3进栈，即3-2-1出栈。
第二种：1进，1出，2斤，2出，3进，3出，进一个出一个，即1-2-3出栈。
第三种：1进，2进，2出，1出，3进，3出，即2-1-3出栈。
第四种：1进，1出，2进，3进，3出，2出，即1-3-2出栈。
第五种：1进，2进，2出，3进，3出，2出，即2-3-1出栈
下边我们来定义栈顺序存储结构的接口：
/// <summary> /// 栈接口 /// </summary> /// <typeparam name="T"></typeparam> interface IStack<T> { /// <summary> /// 清空栈 /// </summary> /// <returns></returns> bool ClearStack(); /// <summary> /// 判断栈是否为空 /// </summary> /// <returns>true:空、false：不空</returns> bool IsEmptyStack(); /// <summary> /// 获取栈顶元素 /// </summary> /// <returns></returns> T GetTopStack(); /// <summary> /// 入栈 /// </summary> /// <returns></returns> bool PushStack(T val); /// <summary> /// 出栈 /// </summary> /// <returns></returns> bool PopStack(); /// <summary> /// 获取栈长度 /// </summary> /// <returns></returns> int LengthStack(); /// <summary> /// 判断栈是否已满 /// </summary> /// <returns></returns> bool IsFull(); /// <summary> /// 打印栈 /// </summary> void paint(); }
定义一个类来实现这个接口：
首先定义三个全局变量
/// <summary> /// 顺序栈的容量（数组最大长度） /// </summary> private int maxsize; /// <summary> /// 数组，用于存储顺序栈中的数据元素 /// </summary> private T[] data; /// <summary> /// 指示顺序栈的栈顶(top = -1 时表示栈为空) /// </summary> private int top;
这个和线性表（顺序存储结构）是一致的。
这里要说明一下顶栈top这个变量，当栈为空时，其为值-1，因此当想清空栈的时候，不需要将链表循环清空，只需将顶栈置为-1即可。
下方是我整个类的代码：具体调用的实例在文末，可下载：
public class StackList<T> : IStack<T> { /// <summary> /// 顺序栈的容量（数组最大长度） /// </summary> private int maxsize; /// <summary> /// 数组，用于存储顺序栈中的数据元素 /// </summary> private T[] data; /// <summary> /// 指示顺序栈的栈顶(top = -1 时表示栈为空) /// </summary> private int top; /// <summary> /// 构造函数 /// </summary> public StackList(int size) { data = new T[size]; maxsize = size; top = -1; } /// <summary> /// 清空栈(这里不需要将数组清空，只要将顶栈赋值为-1就好) /// </summary> /// <returns></returns> public bool ClearStack() { top = -1; return true; } /// <summary> /// 获取栈顶 /// </summary> /// <returns></returns> public T GetTopStack() { T res = data[top]; return res; } /// <summary> /// 是否是空栈 /// </summary> /// <returns></returns> public bool IsEmptyStack() { if (top == -1) { return true; } else { return false; } } /// <summary> /// 获取栈的长度 /// </summary> /// <returns></returns> public int LengthStack() { return top + 1; } /// <summary> /// 出栈 /// </summary> /// <returns></returns> public bool PopStack() { if (IsEmptyStack()) { Console.WriteLine("栈为空，无法删除！"); return false; } T temp = default(T); data[top] = temp; top--; return true; } /// <summary> /// 入栈 /// </summary> /// <returns></returns> public bool PushStack(T val) { if (IsFull()) { Console.WriteLine("栈已满，写入失败！"); return false; } top++; data[top] = val; return true; } /// <summary> /// 判断栈是否已满 /// </summary> /// <returns></returns> public bool IsFull() { if (top == maxsize - 1) { return true; } else { return false; } } /// <summary> /// 打印栈 /// </summary> public void paint() { Console.WriteLine("栈顶："+top); for (int i = 0; i < data.Length; i++) { Console.WriteLine("index:"+i + " | data:"+data[i]); } } }
顺序栈的操作和线性表顺序存储结构相比其实要简单，它的写入和删除操作只发生在表尾，因此在使用它的时候，大概参照线性表的顺序存储结构的用法就好了。
下图是具体调用的实例：
两栈共享空间
栈还有一个在我看来比较高级的用法叫两栈共享空间。
大概是一个栈在表首，一个栈在表尾，每个栈都有一个顶栈。
当两个顶栈彼此相遇的时候，就证明两栈已满，无法再继续操作。
具体代码不在这里进行展示，文末有实例，可下载。
共享栈最后效果如下图所示
