java版数据结构：深入理解栈和队列：数据结构与应用（vector,stack,queue）

前言

动态数组类（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<>();// 添加元素到Vectorvector.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");}// 清空Vectorvector.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);}
}
运行结果：

结语

栈和队列作为常见的数据结构，在算法和程序设计中有着重要的应用。通过深入理解栈和队列的概念、使用方法以及相关应用场景，我们可以更好地应用它们解决实际问题。同时，掌握循环队列和双端队列的概念也能够拓展我们对数据结构的认识，提高编程效率和代码质量。

希望本文能够帮助读者更好地理解和运用栈和队列，为日后的算法学习和程序设计提供帮助。