栈和队列

栈(Stack)

特点:先进后出（LIFO），即最先插入的元素最先被移除。

核心操作:

• 入栈（Push）：将元素添加到栈顶。
• 出栈（Pop）：移除并返回栈顶元素。
• 查看栈顶元素（Peek/Top）：返回栈顶元素但不移除它。 以上操作的时间复杂度均为 O(1)。

实现:栈可以使用数组或链表实现。数组实现的栈具有固定大小，而链表实现的栈可以动态扩展。

class Stack {
    private List<Object> elements;
    private int top;

    public Stack() {
        elements = new ArrayList<>();
        top = -1;
    }

    public void push(Object element) {
        elements.add(element);
        top++;
    }

    public Object pop() {
        if (top == -1) throw new EmptyStackException();
        Object element = elements.get(top);
        elements.remove(top);
        top--;
        return element;
    }

    public Object peek() {
        if (top == -1) throw new EmptyStackException();
        return elements.get(top);
    }
}

应用:

• 函数调用管理：栈用于存储函数调用的上下文信息（如局部变量、返回地址等）。
• 表达式求值：栈用于中缀表达式转后缀表达式（逆波兰表示法）和求值。
• 括号匹配：栈用于检查括号是否匹配。
• 深度优先搜索（DFS）：栈用于实现图的深度优先遍历。

队列(Queue)

特点:先进先出（FIFO），即最先插入的元素最先被移除。

核心操作:

• 入队（Enqueue）：将元素添加到队列尾部。
• 出队（Dequeue）：移除并返回队列头部元素。
• 查看队头元素（Peek/Front）：返回队头元素但不移除它。 以上操作的时间复杂度均为 O(1)。

实现:队列可以使用数组或链表实现。数组实现的队列具有固定大小，而链表实现的队列可以动态扩展。

class Queue {
    private List<Object> elements;
    private int front;
    private int rear;

    public Queue() {
        elements = new ArrayList<>();
        front = 0;
        rear = -1;
    }

    public void enqueue(Object element) {
        elements.add(element);
        rear++;
    }

    public Object dequeue() {
        if (front > rear) throw new NoSuchElementException();
        Object element = elements.get(front);
        front++;
        return element;
    }

    public Object peek() {
        if (front > rear) throw new NoSuchElementException();
        return elements.get(front);
    }
}

应用:

• 任务调度：队列用于管理任务的执行顺序。
• 广度优先搜索（BFS）：队列用于实现图的广度优先遍历。

栈和队列的相互模拟

• 使用两个栈实现队列：可以使用两个栈来模拟队列的行为。一个栈用于入队，另一个栈用于出队。 ```java import java.util.Stack;

public class MyQueue { private final Stack stack1; private final Stack stack2;

public MyQueue() {
    stack1 = new Stack<>();
    stack2 = new Stack<>();
}

public void push(int x) {
    stack1.push(x);
}

public int pop() {
    if (stack2.isEmpty()) {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}

public int peek() {
    if (stack2.isEmpty()) {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.peek();
}

public boolean empty() {
    return stack1.isEmpty() && stack2.isEmpty();
} } ```

• 使用两个队列实现栈：可以使用两个队列来模拟栈的行为。一个队列用于入栈，另一个队列用于出栈。 ```java package StackAndQueue;

import java.util.Queue;

public class MyStack { private Queue queue1; private Queue queue2;

public MyStack() {
    queue1 = new java.util.LinkedList<>();
    queue2 = new java.util.LinkedList<>();
}

public void push(int x) {
    queue1.offer(x);
}

public int pop() {
    if(queue1.isEmpty()) {
        return -1; // or throw an exception
    }
    while (queue1.size() > 1) {
        queue2.offer(queue1.poll());
    }
    int top = queue1.poll();
    Queue<Integer> temp = queue1;
    queue1 = queue2;
    queue2 = temp;
    return top;
}

public int top() {
    if(queue1.isEmpty()) {
        return -1; // or throw an exception
    }
    while (queue1.size() > 1) {
        queue2.offer(queue1.poll());
    }
    int top = queue1.peek();
    queue2.offer(queue1.poll());
    Queue<Integer> temp = queue1;
    queue1 = queue2;
    queue2 = temp;
    return top;
}
public boolean empty() {
    return queue1.isEmpty();
} } ``` 使用一个队列实现栈 ```java import java.util.Queue;

public class MyStack { private Queue queue1; private int topElement;

public MyStack() {
    queue1 = new java.util.LinkedList<>();
    topElement = -1;
}

public void push(int x) {
    queue1.offer(x);
    topElement = x;
}

public int pop() {
    if(queue1.isEmpty()) {
        return -1; // or throw an exception
    }
    int size = queue1.size();
    for (int i = 0; i < size - 2; i++) {
        queue1.offer(queue1.poll());
    }
    topElement = queue1.peek();
    queue1.offer(queue1.poll());
    return queue1.poll();
}

public int top() {
    if(queue1.isEmpty()) {
        return -1; // or throw an exception
    }
    return topElement;
}
public boolean empty() {
    return queue1.isEmpty();
}

} ```

习题

1. 有效的括号(简单)
2. 简化路径(中等)
3. 用栈实现队列(简单)
4. 用队列实现栈(简单)
5. 最小栈(中等)
6. 逆波兰表达式求值(中等)
7. 基本计算器(困难)
8. 设计循环队列(中等)