Stack

栈定义

堆栈（stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，top）进行加入数据（push）和移除数据（pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作，堆栈常用一维数组或链表来实现。常与另一种有序的线性数据集合队列相提并论。

VisualizeStack

栈特点

栈是一种线性数据结构
栈具有后进先出（LIFO）的特性
栈的操作只能在栈顶进行
栈的实现方式有数组和链表两种

栈操作

push: 将元素压入栈顶
pop: 将栈顶元素弹出
peek: 查看栈顶元素
isEmpty: 判断栈是否为空
size: 获取栈中元素个数

栈实现

Java 数组实现

class Stack {
    private int[] array;
    private int top;

    public Stack(int capacity) {
        this.array = new int[capacity];
        this.top = -1;
    }

    public void push(int value) {
        if (top == array.length - 1) {
            throw new StackOverflowError("Stack is full");
        }
        array[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return array[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return array[top];
    }

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

    public int size() {
        return top + 1;
    }
}

Java 链表实现

public class LinkedListStack<T> {
    // 定义节点类
    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node top;  // 栈顶指针
    private int size;  // 栈的大小

    // 构造函数
    public LinkedListStack() {
        top = null;
        size = 0;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 获取栈的大小
    public int size() {
        return size;
    }

    // 入栈
    public void push(T data) {
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
        size++;
    }

    // 出栈
    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        T data = top.data;
        top = top.next;
        size--;
        return data;
    }

    // 查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.data;
    }

    // 清空栈
    public void clear() {
        top = null;
        size = 0;
    }

    // 打印栈中所有元素
    public void print() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return;
        }

        Node current = top;
        System.out.print("Stack: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

use example

public class Main {
    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();

        // 测试入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.print(); // Stack: 3 2 1

        // 测试出栈
        System.out.println("Popped: " + stack.pop()); // Popped: 3
        stack.print(); // Stack: 2 1

        // 测试peek
        System.out.println("Top element: " + stack.peek()); // Top element: 2

        // 测试size
        System.out.println("Stack size: " + stack.size()); // Stack size: 2

        // 测试清空
        stack.clear();
        System.out.println("Is stack empty? " + stack.isEmpty()); // Is stack empty? true
    }
}

栈定义

栈特点

栈操作

栈实现

Java 数组实现

Java 链表实现

Read Next

Array

Linked List