Java顺序栈(栈的顺序存储)用法详解
采用顺序存储结构的栈称为顺序栈。顺序栈利用一组连续的存储单元存放栈中的元素,存放顺序依次从栈底到栈顶。
由于栈中的元素之间的存放地址的连续性,因此 Java 语言中同样采用数组实现栈的顺序存储。另外,增加一个栈顶指针 top,用于指向顺序栈的栈顶元素。
栈的顺序存储结构类型描述如下:

图 1 顺序栈结构
将元素 A、B、C、D、E、F、G、H 依次进栈,栈底元素为 A,栈顶元素为 H。
注意,当栈中的元素个数为 StackSize 时,称为栈满。当栈满时进行入栈操作,将产生上溢错误。若对空栈进行删除操作,则产生下溢错误。因此,在对栈进行进栈或出栈操作前,要判断栈是否已满或已空。
为了解决这个问题,可以让多个栈共享一个足够大的连续存储空间,利用栈的动态特性使栈空间能够互相补充,存储空间得到有效利用,这就是栈的共享,这些栈被称为共享栈。
在栈的共享问题中,最常用的是两个栈的共享。共享栈主要通过栈底固定、栈顶迎面增长的方式实现。让两个栈共享一个一维数组 S[StackSize],两个栈底设置在数组的两端,当有元素进栈时,栈顶位置从栈的两端向中间迎面增长,当两个栈顶相遇时,栈满。
共享栈(两个栈共享一个连续的存储空间)的数据结构类型描述如下:
例如,共享栈的存储表示如下图所示:

图 2 共享栈示意图
共享栈的算法操作如下:
由于栈中的元素之间的存放地址的连续性,因此 Java 语言中同样采用数组实现栈的顺序存储。另外,增加一个栈顶指针 top,用于指向顺序栈的栈顶元素。
栈的顺序存储结构类型描述如下:
public class SeqStack { private static java.lang.Object String; int top; final int StackSize = 50; char stack[]; public SeqStack() { top = 0; stack = new char[StackSize]; } }用数组表示的顺序栈如下图所示:

图 1 顺序栈结构
将元素 A、B、C、D、E、F、G、H 依次进栈,栈底元素为 A,栈顶元素为 H。
说明:在本文中,约定栈顶指针 top 指向栈顶元素的下一个位置(而不是栈顶元素)。
- 初始时,栈为空,栈顶指针为 0,即 S.top=0。
- 栈空条件为 S.top==0,栈满条件为 S.top==StackSize。
- 进栈操作时,先将元素压入栈中,即 S.stack[S.top]=e,然后使栈顶指针加 1,即 S.top+=1。出栈操作时,先使栈顶指针减 1,即 S.top-=1,然后元素出栈,即 e=S.stack[S.top]。
- 栈的长度,即栈中元素的个数为 S.top。
注意,当栈中的元素个数为 StackSize 时,称为栈满。当栈满时进行入栈操作,将产生上溢错误。若对空栈进行删除操作,则产生下溢错误。因此,在对栈进行进栈或出栈操作前,要判断栈是否已满或已空。
顺序栈的基本运算
1) 栈的初始化
public SeqStack() { top = 0; stack = new char[StackSize]; }
2) 判断栈是否为空
public boolean StackEmpty() { if (top == 0) return true; else return false; }
3) 取栈顶元素
public char GetTop() throws Exception { if (StackEmpty()) { throw new Exception("栈为空!"); } else { return stack[top - 1]; } }
4) 入栈操作
public boolean PushStack(char e) { if (top >= StackSize) { System.out.println("栈已满!"); return false; } else { stack[top] = e; top++; return true; } }
5) 出栈操作
public char PopStack() throws Exception { if (StackEmpty()) { throw new Exception("栈为空!"); } else { top--; char x = stack[top]; return x; } }
6) 返回栈的长度
public int StackLength() { return top; }
7) 清空栈
public void ClearStack() { top = 0; }
共享栈
栈的应用非常广泛,经常会出现一个程序需要同时使用多个栈的情况。使用顺序栈会因为栈空间的大小难以准确估计,从而造成有的栈溢出,有的栈还有空闲。为了解决这个问题,可以让多个栈共享一个足够大的连续存储空间,利用栈的动态特性使栈空间能够互相补充,存储空间得到有效利用,这就是栈的共享,这些栈被称为共享栈。
在栈的共享问题中,最常用的是两个栈的共享。共享栈主要通过栈底固定、栈顶迎面增长的方式实现。让两个栈共享一个一维数组 S[StackSize],两个栈底设置在数组的两端,当有元素进栈时,栈顶位置从栈的两端向中间迎面增长,当两个栈顶相遇时,栈满。
共享栈(两个栈共享一个连续的存储空间)的数据结构类型描述如下:
public class SSeqStack<T> { int top; T stack[]; final int StackSize = 50; }其中,top[0] 和 top[1] 分别是两个栈的栈顶指针。
例如,共享栈的存储表示如下图所示:

图 2 共享栈示意图
共享栈的算法操作如下:
1) 初始化操作
SSeqStack() { // 共享栈的初始化操作 top = new int[2]; top[0] = 0; top[1] = StackSize - 1; stack = (T[])new Object[StackSize]; }
2) 进栈操作
public boolean PushStack(T e, int flag) { // 共享栈进栈操作。若入栈成功,则返回 true,否则返回 false if (top[0] == top[1]) { // 在执行进栈操作之前,判断共享栈是否已满 return false; } if (flag == 0) { // 当 flag 为 0 时,表示元素要进左端的栈 stack[top[0]] = e; // 元素进栈 top[0]++; // 修改栈顶指针 } else if (flag == 1) { // 当 flag 为 1 时,表示元素要进右端的栈 stack[top[1]] = e; // 元素进栈 top[1]--; // 修改栈顶指针 } else { return false; } return true; }
3) 出栈操作
public T PopStack(int flag) throws Exception { // 共享栈出栈操作。若出栈成功,则返回出栈元素 if (flag == 0) { // 在执行出栈操作之前,判断是哪个栈要进行出栈操作 if (top[0] == 0) { // 若左端的栈为空,则抛出异常,表示出栈操作失败 throw new Exception("栈1为空,不能出栈操作!"); } top[0]--; // 修改栈顶指针 T e = stack[top[0]]; // 将出栈的元素赋值给 e } else if (flag == 1) { if (top[1] == StackSize - 1) { // 若右端的栈为空,则抛出异常,表示出栈操作失败 throw new Exception("栈2为空,不能出栈操作!"); } top[1]++; // 修改栈顶指针 T e = stack[top[1]]; // 将出栈的元素赋值给 e } else { throw new Exception("参数 flag 错误!"); } return e; }