Java中栈和队列（栈跟队列）

一、栈（Stack）

栈是一种后进先出（LIFO，Last In First Out）的数据结构。它就像一个垂直的堆栈，新添加的元素被放在顶部，而移除元素时总是从顶部开始。

栈是限定仅在表尾进行插入或删除操作的 线性表。栈尾称为栈顶（top），表头称为栈底（bottom）。不含元素的空表称为空栈。

栈的基本操作

push(item): 将一个元素压入栈顶。

pop(): 移除栈顶的元素，并返回该元素。

peek(): 返回栈顶的元素，但不移除它。

isEmpty(): 检查栈是否为空。

Java中的java.util.Stack类提供了栈的基本操作，但你也可以通过数组或链表来实现一个自定义的栈。

下面是一个简单的基于数组的栈实现：

public class ArrayStack {  
    private int maxSize;  
    private int top;  
    private int[] stackArray;  
  
    public ArrayStack(int size) {  
        maxSize = size;  
        stackArray = new int[maxSize];  
        top = -1;  
    }  
  
    public void push(int value) {  
        if (!isFull()) {  
            stackArray[++top] = value;  
        } else {  
            System.out.println("栈已满，无法添加元素");  
        }  
    }  
  
    public int pop() {  
        if (!isEmpty()) {  
            return stackArray[top--];  
        } else {  
            System.out.println("栈为空，无法移除元素");  
            return -1;  
        }  
    }  
  
    public int peek() {  
        if (!isEmpty()) {  
            return stackArray[top];  
        } else {  
            System.out.println("栈为空");  
            return -1;  
        }  
    }  
  
    public boolean isEmpty() {  
        return (top == -1);  
    }  
  
    public boolean isFull() {  
        return (top == maxSize - 1);  
    }  
}

二、队列（Queue）

队列是一种先进先出（FIFO，First In First Out）的数据结构。它就像一个水平的队列，新添加的元素被放在队尾，而移除元素时总是从队首开始。

和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾（rear），允许删除的一端则称为对头（front）。一个最典型的例子就是操作系统中的作业排队，在允许多通道程序运行的计算机系统中，同事有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出做输出操作，凡是申请输出的作业都从队尾进入队列。

队列的基本操作

enqueue(item): 将一个元素添加到队尾。

dequeue(): 移除队首的元素，并返回该元素。

peek(): 返回队首的元素，但不移除它。

isEmpty(): 检查队列是否为空。

Java中的java.util.Queue接口和它的实现类（如LinkedList）提供了队列的基本操作。你也可以通过数组或链表来实现一个自定义的队列。

下面是一个简单的基于链表的队列实现：

public class LinkedListQueue {  
    private Node front;  
    private Node rear;  
  
    class Node {  
        int data;  
        Node next;  
  
        Node(int data) {  
            this.data = data;  
            this.next = null;  
        }  
    }  
  
    public void enqueue(int value) {  
        Node newNode = new Node(value);  
        if (rear == null) {  
            front = newNode;  
            rear = newNode;  
        } else {  
            rear.next = newNode;  
            rear = newNode;  
        }  
    }  
  
    public int dequeue() {  
        if (!isEmpty()) {  
            int item = front.data;  
            front = front.next;  
            if (front == null) {  
                rear = null;  
            }  
            return item;  
        } else {  
            System.out.println("队列为空，无法移除元素");  
            return -1;  
        }  
    }  
  
    public int peek() {  
        if (!isEmpty()) {  
            return front.data;  
        } else {  
            System.out.println("队列为空");  
            return -1;  
        }  
    }  
  
    public boolean isEmpty() {  
        return (front == null);  
    }  
}