Java 集合框架 Queue 和 Stack 体系

Java 集合框架 Queue 和 Stack 体系

Queue

什么是 Queue

Java 集合框架中的 Queue 接口代表了一种先进先出 (FIFO) 的队列数据结构。该接口继承自 Collection 接口，它是一种有序的集合，允许我们在队尾插入元素，从队头获取元素。在 Queue 中，插入元素的操作称之为 offer()，获取并删除队头元素的操作称之为 poll()。

适用场景

Queue 接口被广泛应用于一些场景，如线程池，消息队列，优先队列等。

示例一：使用 Queue 保存元素并获取

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("element 1");
        queue.offer("element 2");
        queue.offer("element 3");

        System.out.println("队列头元素为：" + queue.peek());
        System.out.println("队列长度为：" + queue.size());

        String head = queue.poll();
        System.out.println("队列弹出的头元素为：" + head);
        System.out.println("队列长度为：" + queue.size());
    }
}

输出：

队列头元素为：element 1
队列长度为：3
队列弹出的头元素为：element 1
队列长度为：2

示例二：使用 Queue 实现消息队列

import java.util.LinkedList;
import java.util.Queue;

public class MessageQueue {
    private Queue<Message> queue;

    public MessageQueue() {
        queue = new LinkedList<>();
    }

    public void addMessage(Message message) {
        queue.offer(message);
        System.out.println("添加消息：" + message);
    }

    public Message getMessage() {
        Message message = queue.poll();
        System.out.println("取出消息：" + message);
        return message;
    }
}

class Message {
    private String content;

    public Message(String content) {
        this.content = content;
    }

    @Override
    public String toString() {
        return "Message{" +
                "content='" + content + '\'' +
                '}';
    }
}

class QueueExample {
    public static void main(String[] args) {
        MessageQueue messageQueue = new MessageQueue();

        for (int i = 0; i < 10; i++) {
            messageQueue.addMessage(new Message("message " + i));
        }

        for (int i = 0; i < 10; i++) {
            messageQueue.getMessage();
        }
    }
}

输出：

添加消息：Message{content='message 0'}
添加消息：Message{content='message 1'}
添加消息：Message{content='message 2'}
添加消息：Message{content='message 3'}
添加消息：Message{content='message 4'}
添加消息：Message{content='message 5'}
添加消息：Message{content='message 6'}
添加消息：Message{content='message 7'}
添加消息：Message{content='message 8'}
添加消息：Message{content='message 9'}
取出消息：Message{content='message 0'}
取出消息：Message{content='message 1'}
取出消息：Message{content='message 2'}
取出消息：Message{content='message 3'}
取出消息：Message{content='message 4'}
取出消息：Message{content='message 5'}
取出消息：Message{content='message 6'}
取出消息：Message{content='message 7'}
取出消息：Message{content='message 8'}
取出消息：Message{content='message 9'}

Stack

什么是 Stack

Java 集合框架中的 Stack 类代表了一种后进先出 (LIFO) 的堆栈数据结构。它是 Vector 类的一个子类，因此它可以使用 Vector 中的所有方法，同时它还有自己的一些独特的方法，如 push() 和 pop() 等。

适用场景

Stack 类不建议用于复杂的数据结构或高性能的应用程序中使用。但是，它可以很好地处理一些简单的场景，如括号匹配、表达式求值等。

示例一：使用 Stack 实现括号匹配

import java.util.Stack;

public class BracketMatching {
    private static final char LEFT_ROUND_BRACKET = '(';
    private static final char RIGHT_ROUND_BRACKET = ')';

    private static final char LEFT_SQUARE_BRACKET = '[';
    private static final char RIGHT_SQUARE_BRACKET = ']';

    private static final char LEFT_CURLY_BRACES = '{';
    private static final char RIGHT_CURLY_BRACES = '}';

    public static boolean isMatch(String str) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            if (c == LEFT_ROUND_BRACKET || c == LEFT_SQUARE_BRACKET || c == LEFT_CURLY_BRACES) {
                stack.push(c);
            } else if (c == RIGHT_ROUND_BRACKET) {
                if (stack.empty() || stack.pop() != LEFT_ROUND_BRACKET) {
                    return false;
                }
            } else if (c == RIGHT_SQUARE_BRACKET) {
                if (stack.empty() || stack.pop() != LEFT_SQUARE_BRACKET) {
                    return false;
                }
            } else if (c == RIGHT_CURLY_BRACES) {
                if (stack.empty() || stack.pop() != LEFT_CURLY_BRACES) {
                    return false;
                }
            }
        }

        return stack.empty();
    }

    public static void main(String[] args) {
        String str = "(1+2*[3-{4/(5+6)}]+7)";

        if (isMatch(str)) {
            System.out.println(str + " 括号匹配成功");
        } else {
            System.out.println(str + " 括号匹配失败");
        }
    }
}

输出：

(1+2*[3-{4/(5+6)}]+7) 括号匹配成功

示例二：使用 Stack 实现表达式求值

import java.util.Stack;

public class ExpressionEvaluation {
    public static int calculate(String str) {
        Stack<Integer> stack = new Stack<>();

        int num = 0;
        int sign = '+';

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }

            if (!Character.isDigit(c) && c != ' ' || i == str.length() - 1) {
                if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '+') {
                    stack.push(num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = c;
                num = 0;
            }
        }

        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(calculate("1 + 2 * 3 - 4 / 2"));  // 输出 5
    }
}

输出：

5