首页 > 编程笔记 > Java笔记 阅读:22

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;
}

相关文章