首页 > 编程笔记 > Java笔记 阅读：20

Java顺序栈（栈的顺序存储）用法详解

采用顺序存储结构的栈称为顺序栈。顺序栈利用一组连续的存储单元存放栈中的元素，存放顺序依次从栈底到栈顶。

由于栈中的元素之间的存放地址的连续性，因此 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 指向栈顶元素的下一个位置（而不是栈顶元素）。

说明：
注意，当栈中的元素个数为 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;
}

相关文章