栈（数组、单链表实现栈）

单链表实现栈

思路

使用链表模拟栈
思路：
入栈：当要插入数据时，直接将其放在头节点之后
newNode.next = head.next; head.next = newNode;
出栈：删除返回头节点的下一个节点，
StackNode data = head.next;
head.next = head.next.next;
return data.value;
遍历：list(),从头节点开始遍历

代码实现

class LinkedListStack {
    private StackNode head;//头节点 
    private int maxSize;//容量
    private int size = 0;//元素个数

    //构造器
    public LinkedListStack(int maxSize) {
        this.head = new StackNode(null, 0);
        this.maxSize = maxSize;
    }

    //判断栈是否已满
    public boolean isFull() {
        return size == maxSize;
    }

    //判断栈是否为空
    public boolean isEmpty() {
        return head.next == null;
    }

    //放入元素
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈已满，无法放入！！！！！");
            return;
        }
        StackNode newNode = new StackNode(value);
        if (!isEmpty()) {
            newNode.next = head.next;
        }
        head.next = newNode;
        size++;
    }

    //出栈
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("大兄弟，栈是空的！！！！！");
        }
        StackNode node = head.next;
        head.next = head.next.next;
        size--;
        return node.value;
    }

    //遍历所有元素
    public void list(){
        if (isEmpty()) {
            System.out.println("大兄弟，栈是空的！！！！！");
            return;
        }
        StackNode temp = head.next;
        System.out.println("遍历所有值");
        while (temp!=null) {
            System.out.println("stack:"+temp.value);
            temp = temp.next;
        }
    }

    //节点类
    class StackNode {
        StackNode next;
        int value;
        public StackNode(int value) {
            this.value = value;
        }
        public StackNode(StackNode next, int value) {
            this.next = next;
            this.value = value;
        }
    }
}

数组实现栈

思路

定义一个maxSize，表示栈的大小
使用一个top指针，来表示栈顶元素；
入栈时，top++，arr[top] = 新元素；
出栈时，，arr[top]就是要出栈的元素，然后top–；

代码实现

//使用数组实现栈
class ArrayStack{
    
    private int maxSize;//栈的大小
    private int[] stack;//数组模拟栈 数据旧放在改数组中
    private int top;//表示栈顶

    //构造器
    public ArrayStack(int maxSize){
        if (maxSize<=0) {
            System.out.println("maxSize的值不合法！");
            return;
        }
        this.top = -1;
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    //判断栈是否已满
    public boolean isFull(){
        return top == maxSize - 1;
    }

    //判断栈是否为空
    public boolean isEmpty(){
        return top==-1;
    }

    //入栈
    public void push(int value){
        if (isFull()) {
            throw new RuntimeException("栈已满");
        }
        stack[++top] = value;
    }

    //出栈
    public int pop(){
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        }
        return stack[top--];
    }

    //遍历栈，从顶开始
    public void list(){
        if (isEmpty()) {
            System.out.println("栈是空的，大兄弟！！");
        }
        for (int i = top;i>=0;i--) {
            System.out.printf("stack[%d] = %d\n",i,stack[i]);
        }
    }
}