[!quote] 逻辑结构

逻辑结构的物理实现，既可以用数组，也可以用链表

普通栈

[!quote] 栈 栈 stack 是一种线性数据结构【它就像放入乒乓球的圆筒容器】，栈中的元素只能先入后出

• 用于面包屑导航：可以使用户在浏览页面时更快的返回上一级

数组实现

public class ArrayStack {  
    private int[] stack; // 用数组模拟栈  
    private int top; // 栈顶指针  

	// 构造方法，初始化栈
    public ArrayStack(int size) {      
        stack = new int[size];  
        top = -1;  
    }
    
    // 判断栈是否为空 
    public boolean isEmpty() {  
	    return top == -1;  
	}  

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

	出栈，入栈，遍历……
}

入栈

public void push(int data) { // 入栈操作
	if (isFull()) {
		System.out.println("栈已满，无法入栈");
		return;  // 遇到return，则不在向下执行
	}
	top++;
	stack[top] = data;
}

出栈

public int pop() { // 出栈操作
	if (isEmpty()) {
		throw new RuntimeException("栈为空，无法出栈");
	}
	int value = stack[top];
	top--;
	return value;
}

[!hint] 其实出栈之后元素还是在数组里，但是后续的入栈会覆盖掉原来的值

遍历

public void show() { 
	if (isEmpty()) {
		System.out.println("栈为空，没有数据");
		return;
	}
	for (int i = top; i >= 0; i--) {
		System.out.println(stack[i]);
	}
}

链表实现

public class LinkedStack {
    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
        }
    }

	private Node top; // 栈顶节点
	public LinkedStack() {       // 初始化栈  
	    top = null;  
	}  
  
	public boolean isEmpty() {    // 判断栈是否为空  
	    return top == null;  
	}
}

入栈

public void push(int data) {
	Node newNode = new Node(data);    // 创建新节点
	newNode.next = top;     // 新节点指向原来的栈顶节点
	top = newNode;      // 新节点成为新的栈顶节点
}

出栈

public int pop() {        
	if (isEmpty()) {
		throw new RuntimeException("栈为空，无法出栈");
	}
	int value = top.data; 
	top = top.next;
	return value;
}

遍历

public void show() {
	if (isEmpty()) {
		System.out.println("栈为空，没有数据");
		return;
	}
	Node temp = top;
	while (temp != null) {
		System.out.println(temp.data);
		temp = temp.next;
	}
}

两栈共享空间