数据结构（四）：栈及通过数组实现

栈Stack

1.栈是一个先进后出（first in last out）的有序列表
2.栈的插入删除只能在线性表的同一端进行，允许插入删除的一端叫栈顶，另一端固定的叫栈底。

我们先演示下通过数组实现栈

package com.study;

public class TestStack {

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.print();
        System.out.println("===========================");
        stack.pop();
        stack.print();
        System.out.println("===========================");

    }

}
class ArrayStack{
    private int size;//栈的大小
    private int[] stack;//数组
    private int top = -1;//辅助，指向栈顶，初始化的时候为-1,
    public ArrayStack(int size){
        this.size = size;
        stack = new int[size];
    }
    /*
    *判断是否为空
    * */
    public boolean isEmpty(){
        if(top == -1){
            return true;
        }
        return false;
    }
    /*
    * 栈满
    * */
    public boolean isFull(){
        if(top == size-1){
            return true;
        }
        return false;
    }

    /*
    * 入栈
    * */
    public void push(int x){
        if(isFull()){
            System.out.println("栈满了");
            return;
        }
        top++;
        stack[top] = x;
    }
    /*
    * 出栈
    * */
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("栈为空");
        }
        int temp = stack[top];
        top--;
        return temp;
    }
    /*
    * 遍历
    * */
    public void print(){
        if(isEmpty()){
            throw new RuntimeException("栈为空，无数据");
        }
        int i = top;
        while(i!=-1){
            System.out.println(stack[i]);
            i--;
        }
    }
}

通过代码，我们可以看到：要实现栈，重要的一点就是有个辅助元素，帮助指向栈顶。