目录
前言
动态数组类（vector）
特点：
应用：
栈（Stack）
栈的基础概念：
栈的常用方法：
模拟栈操作：
队列（Queue）
队列的基础概念
队列的常用方法
双端队列（Deque）
双端队列的基础概念：
双端队列的常用方法：
结语
前言
在计算机科学中，栈（Stack）和队列（Queue）是两种常见的数据结构，它们在算法和程序设计中扮演着重要的角色。本文将深入探讨栈和队列的概念、使用方法以及相关的应用场景。
动态数组类（vector）
Vector是Java中的一个动态数组类，它实现了一个可增长的对象数组。与普通数组相比，Vector具有以下特点：特点：
- 动态增长：
Vector可以根据需要动态增长或缩小其大小，无需手动管理数组大小。- 线程安全：
Vector是线程安全的，即可以在多线程环境下使用，但由于同步操作的开销较大，通常不推荐在单线程环境下使用。- 元素访问：可以通过索引访问
Vector中的元素，也可以通过迭代器遍历Vector中的元素。- 实现了List接口：
Vector实现了List接口，因此支持列表操作，如添加、删除、获取元素等。- 遗留类：
Vector是Java早期的遗留类，通常不推荐在新代码中使用。在现代Java中，更推荐使用ArrayList或LinkedList等更高效的集合类。应用：
import java.util.Vector; public class VectorExample { public static void main(String[] args) { // 创建一个Vector对象 Vector<Integer> vector = new Vector<>(); // 添加元素到Vector vector.add(1); vector.add(2); vector.add(3); // 输出Vector的大小 System.out.println("Vector的大小: " + vector.size()); // 获取指定位置的元素 System.out.println("第二个元素: " + vector.get(1)); // 修改指定位置的元素 vector.set(0, 10); // 移除指定位置的元素 vector.remove(2); // 检查Vector是否包含某个元素 if (vector.contains(2)) { System.out.println("Vector包含元素2"); } else { System.out.println("Vector不包含元素2"); } // 清空Vector vector.clear(); // 检查Vector是否为空 if (vector.isEmpty()) { System.out.println("Vector为空"); } else { System.out.println("Vector不为空"); } } }运行结果：
栈（Stack）
栈的基础概念：
栈（Stack）是一种特殊的线性数据结构，具有后进先出（LIFO）的特性，即最后入栈的元素最先出栈。栈的操作主要包括压栈（push）、出栈（pop）、获取栈顶元素（peek）、获取栈中元素个数（size）以及检测栈是否为空（empty）等。
栈的常用方法：
- 创建栈对象：
- 使用
Stack类：可以直接使用Java提供的Stack类来创建栈对象，该类继承自Vector类，提供了压栈、出栈、获取栈顶元素等方法。- 使用自定义栈类：也可以自定义栈类，通过数组或链表实现栈结构，实现压栈、出栈、获取栈顶元素等操作。
- 基本操作方法：
push(E e): 将元素压入栈顶。pop(): 弹出栈顶元素。peek(): 获取栈顶元素但不弹出。size(): 获取栈中元素个数。empty(): 检测栈是否为空。import java.util.Stack; public class StackExample { public static void main(String[] args) { // 创建一个栈对象 Stack<Integer> stack = new Stack<>(); // 压栈操作 stack.push(1); stack.push(2); stack.push(3); // 输出栈的大小 System.out.println("栈的大小: " + stack.size()); // 获取栈顶元素 System.out.println("栈顶元素: " + stack.peek()); // 出栈操作 stack.pop(); System.out.println("出栈元素: " + stack.pop()); //说明输出（出栈元素）的时候，是先打印原来的栈顶元素然后再出栈 System.out.println("重新获得栈顶元素："+stack.peek()); // 检查栈是否为空 if (stack.empty()) { System.out.println("栈为空"); } else { System.out.println("栈的大小: " + stack.size()); } } }运行结果：
模拟栈操作：
- 在
main方法中模拟栈的操作，包括压栈、出栈、获取栈顶元素、检测栈是否为空等操作。- 可以使用Java提供的
Stack类或自定义的栈类进行模拟操作。import java.util.Arrays; public class MyStack { int[] array; int size; public MyStack() { array = new int[3]; } public int push(int e) { ensureCapacity(); array[size++] = e; return e; } public int pop() { int e = peek(); size--; return e; } public int peek() { if (empty()) { throw new RuntimeException("Stack is empty, cannot get top element"); } return array[size - 1]; } public int size() { return size; } public boolean empty() { return size == 0; } private void ensureCapacity() { if (size == array.length) { array = Arrays.copyOf(array, size * 2); } } }
应用场景：
- 改变元素的序列：通过栈可以实现元素序列的逆序。
- 将递归转化为循环：使用栈可以将递归算法转化为迭代算法。
- 括号匹配：栈常用于检测括号是否匹配。
- 逆波兰表达式求值：栈可以用于求解逆波兰表达式的值。
- 出栈入栈次序匹配：栈可以用于检测出栈入栈次序是否匹配。
- 最小栈：实现一个支持常数时间内获取栈中最小元素的栈。
队列（Queue）
队列的基础概念
队列是另一种特殊的线性表，只允许在一端进行插入数据操作，在另一端进行删除数据操作。队列遵循先进先出（FIFO）的原则，即最先入队列的元素最先出队列。在Java中，Queue是一个接口，常通过LinkedList实现。队列的模拟实现可以使用顺序结构或链式结构。
除了普通队列，还有循环队列的概念。循环队列通常使用数组实现，通过特定的下标循环技巧来实现队列的操作。设计循环队列时需要考虑空与满的情况，可以通过添加size属性、保留一个位置或使用标记来实现。
队列的常用方法
import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { // 创建一个队列 Queue<String> queue = new LinkedList<>(); // 向队列中添加元素 queue.offer("元素1"); queue.offer("元素2"); queue.offer("元素3"); // 输出队列中的元素 System.out.println("当前队列中的元素为："); for (String element : queue) { System.out.println(element); } // 出队操作 String firstElement = queue.poll(); System.out.println("出队的元素为：" + firstElement); // 查看队首元素 String peekElement = queue.peek(); System.out.println("当前队首元素为：" + peekElement); // 判断队列是否为空 boolean isEmpty = queue.isEmpty(); System.out.println("队列是否为空：" + isEmpty); // 获取队列大小 int size = queue.size(); System.out.println("当前队列大小为：" + size); } }运行结果：
双端队列（Deque）
双端队列（Deque，全称Double-Ended Queue）是一种具有两端插入和删除操作的数据结构，它同时具备队列和栈的特性。双端队列可以在队列的两端进行元素的插入和删除操作，因此可以高效地支持在队列头部和尾部进行操作。
双端队列的基础概念：
两端操作：双端队列支持在队列的两端进行操作，即可以在队列的头部和尾部同时进行插入和删除操作。这使得双端队列既可以作为队列使用（先进先出），也可以作为栈使用（后进先出）。
插入和删除操作：双端队列提供了插入和删除元素的方法，如在队列头部插入元素、在队列尾部插入元素、在队列头部删除元素、在队列尾部删除元素等操作。
灵活性：双端队列的灵活性使得它在很多场景下都非常有用，比如需要同时支持队列和栈操作的情况，或者需要在队列的两端频繁进行操作的情况。
实现方式：双端队列可以通过数组、链表等数据结构来实现。在Java中，
Deque接口定义了双端队列的基本操作，而LinkedList和ArrayDeque等类提供了Deque接口的实现。双端队列的常用方法：
import java.util.ArrayDeque; import java.util.Deque; public class Main { public static void main(String[] args) { // 创建一个双端队列 Deque<String> deque = new ArrayDeque<>(); // 在队列头部插入元素 deque.addFirst("元素1"); deque.addFirst("元素2"); // 在队列尾部插入元素 deque.addLast("元素3"); // 输出双端队列中的元素 System.out.println("当前双端队列中的元素为："); for (String element : deque) { System.out.println(element); } // 在队列头部删除元素 String firstElement = deque.removeFirst(); System.out.println("删除的队列头部元素为：" + firstElement); // 在队列尾部删除元素 String lastElement = deque.removeLast(); System.out.println("删除的队列尾部元素为：" + lastElement); // 查看双端队列头部元素 String peekFirstElement = deque.peekFirst(); System.out.println("当前双端队列头部元素为：" + peekFirstElement); // 查看双端队列尾部元素 String peekLastElement = deque.peekLast(); System.out.println("当前双端队列尾部元素为：" + peekLastElement); } }运行结果：
结语
栈和队列作为常见的数据结构，在算法和程序设计中有着重要的应用。通过深入理解栈和队列的概念、使用方法以及相关应用场景，我们可以更好地应用它们解决实际问题。同时，掌握循环队列和双端队列的概念也能够拓展我们对数据结构的认识，提高编程效率和代码质量。
希望本文能够帮助读者更好地理解和运用栈和队列，为日后的算法学习和程序设计提供帮助。
