数据结构之栈（stack）的实现

polary 2020-05-11 原文

一、栈

1.定义

栈的英文为(stack)，是一种数据结构
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

2.重要操作

（1）入栈

判断栈是否为已满，若满给出提示信息
若栈有剩余空间，则将数据压入栈顶，并将栈顶指针top上移

（2）出栈

判断栈是否为空栈，若为空栈则不能出栈，需要抛出异常信息
若栈不为空栈，则取栈顶元素，将栈顶指针top下移

二、代码实现

/**
 * @author ymy
 * @date 2020/5/11
 *
 * 使用数组模拟栈
 */
public class SeqStack {

    private int maxSize;//栈的容量
    private int top;//栈顶
    private Object [] data;//用来存放数据的区域
    
    public SeqStack(int maxSize){
        top=-1;
        this.maxSize=maxSize;
        data=new Object[maxSize];
    }

    public void push(Object obj){
        if (isFull()){
            System.out.println("栈已满");
            return;
        }
        data[++top]=obj;
    }

    public Object pop(){
        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return data[top--];
    }

    public boolean isEmpty(){
        return top==-1;
    }

    public boolean isFull(){
        return top==maxSize-1;
    }

}

三、测试

测试代码：

/**
 * @author ymy
 * @date 2020/5/11
 */
public class TestStack {

    public static void main(String[] args) {
        SeqStack stack = new SeqStack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
        System.out.println("===========");
        stack.push(6);
        stack.push(7);
        stack.push(8);
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}

运行结果：