数据结构之栈

1.栈的定义

栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端
进行。通常称允许插入、删除操作的这一端为栈顶(Top)，不允许操作的一
端称为栈底(Bottom)。当表中没有元素时称为空栈。

2.栈的操作

入栈:每次插入（称为进栈）操作称为入栈或压入（PUSH）操作，入栈的元素总是当前栈中“最新”的元素
出栈：在空栈中最先插入的元素总被放在栈的底部，只有所有元素被弹出之后它才能被删除。

3.栈的溢出

（1）当栈满时进栈运算称为“上溢”。
（2）当栈空时退栈运算称为“下溢”。
（3）栈上溢是一种出错状态，应该设法避免之；而下溢则可能是正常现象，通常下溢用来作为程序控制转移的条件

4.栈的接口类

public interface Stack<T>
{public abstract boolean isEmpty(); //判空public abstract void push(T x); //x入栈public abstract T peek(); //返回栈顶，未出栈public abstract T pop(); //出栈，返回栈顶
}

5.栈的分类

(1)顺序栈（2）链栈

6顺序栈

6.1 顺序栈定义

栈的顺序存储结构简称为顺序栈（Sequential Stack），它是运算受限的线性表。因此，可用数组来实现顺序栈

6.2 顺序栈实现接口

public final class SeqStack<T> implements Stack<T>
{private SeqList<T> list; //顺序表public SeqStack(int capacity) //构造空栈public SeqStack() //构造空栈public boolean isEmpty() //判空public void push(T x) //x入栈public T peek() //返回栈顶（未出栈）public T pop() //出栈，返回栈顶元素
}

6.3 顺序栈实现类

public class SeqStack<T> implements Stack<T> {private SeqList<T> list; //使用顺序表（第2章）存储栈元素public SeqStack(int length) //构造容量为length的空栈{this.list = new SeqList<T>(length); //执行顺序表构造方法}public SeqStack() //构造默认容量的空栈{this(64);}public boolean isEmpty()//判断栈是否空，若空返回true{return this.list.isEmpty();}public void push(T x) //元素x入栈，空对象不能入栈{this.list.insert(x);//顺序表尾插入元素x，自动扩充容量}public T peek()//返回栈顶元素（未出栈），若栈空返回null{return this.list.get(list.size() - 1);//若栈空，get(i)返回null}public T pop()
//出栈，返回栈顶元素；若栈空返回null{return this.list.remove(list.size() - 1);//若栈不空，顺序表尾删除，返回删除元素}public String toString()//返回栈所有元素的描述字符串，形式为“(,)”{return this.getClass().getName() + " " + this.list.toString();}}

7链栈

链式栈定义：栈的链式存储，称为链栈

7.1 链式栈接口

//链式栈类，最终类，实现栈接口，T表示元素类型
public final class LinkedStack<T> implements
Stack<T>
{private SinglyList<T> list; //单链表public LinkedStack() //构造空栈public boolean isEmpty() //判空public void push(T x) //x入栈public T peek() //返回栈顶（未出栈）public T pop() //出栈，返回栈顶元素
}

7.2 链式栈实现类

public class LinkedStack<T>  implements Stack<T> {private SinglyList<T> list;//使用单链表（第2章）存储栈元素public LinkedStack() //构造空栈{this.list = new SinglyList<T>(); //构造空单链表}public boolean isEmpty()//判断栈是否空，若空返回true{return this.list.isEmpty();}public void push(T x)//元素x入栈，空对象不能入栈{this.list.insert(0, x); //单链表头插入元素x}public T peek()//返回栈顶元素（未出栈）；若栈空返回null{return this.list.get(0);}public T pop() //出栈，返回栈顶元素；若栈空返回null{return this.list.remove(0);//若栈不空，单链表头删除，返回删除元素}public String toString()
//返回栈所有元素的描述字符串，形式为“(,)”{return this.getClass().getName()+" "+this.list.toString();}}

8 顺序栈和链栈区别
（1）顺序栈必须说明一个固定的长度，当栈不够满时，造成一些空间的浪费，而链式栈的长度可变则是长
度不需要预先设定，相对比较节省空间，但是在每个结点中，设置了一个指针域，从而产生了结构开销
（2）当需要多个栈共享时，顺序存储中可以充分利用顺序栈的单向延伸性。可以使用一个数组存储两个栈，使每个栈从各自的端点向中间延伸，这样浪费的空间就会减少。但这种情况只有当两个栈的空间需求有相反的需求时，这种方法才有效。
（3）如果多个顺序栈共享空间，则可能需要大量的数据移动，造成时间的开销增大。而链式栈由于存储的不连续性，一般不存在栈满的问题，所以一般不需要栈的共享。