Java中栈的实现（数组、链表）

定义

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

入栈

出栈

应用场景

• 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中； (函数栈)
• 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中；(函数栈)
• 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)；
• 二叉树的遍历；
• 图形的深度优先(depth一first)搜索法。

实现

实现方式包括：

• 数组：ArrayStack
• 链表
  • 头插法：LinkedListStackHead (推荐） 
  • 尾插法：LinkedListStackTail

数组

class ArrayStack {
    private int maxSize; //栈大小
    private int[] stack; //数组模拟栈
    private int top = -1; //栈顶
 
    public ArrayStack(int maxSize) {
        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()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }
 
    //    出栈
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
       /* int value = stack[top];
        top--;
        return value;*/
        return stack[top--];
    }
 
    //    遍历
    public void list() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }
}

链表

定义节点

//定义链表节点
class Node {
    public int val;
    public Node next;
 
    public Node(int val) {
        this.val = val;
        this.next = null;
    }
}

头插法

class LinkedListStackHead {
 
    private int maxSize;
    private Node head;
 
    public LinkedListStackHead(int maxSize) {
        this.maxSize = maxSize;
        this.head = null;
    }
 
    //        栈满
    public boolean isFull() {
        boolean flag = false;
        int size = 0;
        Node temp = head;
        while (true) {
            if (temp == null) {
                break;
            }
            size++;
            temp = temp.next;
        }
        if (size == maxSize) {
            flag = true;
        }
        return flag;
    }
 
    //    栈空
    public boolean isEmpty() {
        return head == null;
    }
 
    //    入栈
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        Node node = new Node(value);
        node.next = head;
        head = node;
    }
 
    //    出栈
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int res = head.val;
        head = head.next;
        return res;
    }
 
    //    遍历
    public void list() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.val);
            temp = temp.next;
        }
    }
}
 

尾插法

class LinkedListStackTail {
    private int maxSize;
    private Node bottom = new Node(0); //栈底位置，固定
 
    public LinkedListStackTail(int maxSize) {
        this.maxSize = maxSize;
    }
 
    //    栈满
    public boolean isFull() {
        boolean flag = false;
        int size = 0;
        Node temp = bottom.next;
        while (true) {
            if (temp == null) {
                break;
            }
            size++;
            temp = temp.next;
        }
        if (size == maxSize) {
            flag = true;
        }
        return flag;
    }
 
    //    栈空
    public boolean isEmpty() {
        return bottom.next == null;
    }
 
    //    入栈
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        Node newNode = new Node(value);
        Node temp = bottom;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = newNode;
    }
 
    //    出栈
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        Node temp = bottom;
        int res = 0;
        while (temp != null) {
            if (temp.next.next == null) {
                res = temp.next.val;
                temp.next = null;
                break;
            }
            temp = temp.next;
        }
        return res;
    }
 
    //    遍历-逆序---偷懒操作（利用了java中的stack），也可自行实现
    public void list() {
        if (isEmpty()){
            throw new RuntimeException("栈空");
        }
        Stack<Integer> stack = new Stack<>();
        Node temp = bottom.next;
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
}

 测试

package com.frank.stack;
 
import java.util.Scanner;
import java.util.Stack;
 
public class LinkedStackDemo {
    public static void main(String[] args) {
//        ArrayStack stack = new ArrayStack(4);
//        LinkedListStackHead stack = new LinkedListStackHead(4);
        LinkedListStackTail stack=new LinkedListStackTail(4);
        String key = "";
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);
 
        while (loop) {
            System.out.println("show: 显示");
            System.out.println("exit: 退出");
            System.out.println("push: 入栈");
            System.out.println("pop: 出栈");
 
            key = scanner.next();
            switch (key) {
                case "show":
                    try {
                        stack.list();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "push":
                    System.out.println("输入数：");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.pop();
                        System.out.printf("出栈数据%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}