目录
前言
1.使用“栈”检查符号是否成对出现
2.使用“栈”实现字符串反转
3.使用“队列”实现“栈”
4.使用“栈”实现“队列”
前言
什么是栈？
- 栈（stack）是一种特殊的线性数据集合，只允许在栈顶按照后进先出LIFO（Last In First Out）进行数据操作；
为什么使用栈？
- 常见应用场景：浏览器的前进与回退操作、虚拟机栈等；
如何使用栈？
- 栈的实现结构可以是一维数组或链表实现
- 用数组实现的栈叫做顺序栈。在Java中，顺序栈使用java.util.Stack类实现
- 用链表实现的栈叫做链式栈。在Java中，链式栈使用java.util.LinkedList类实现；
- 入栈（push）：将新元素放入栈顶，只允许从栈顶一侧放入元素，类似于弹匣装弹，只能从弹匣口依次压入弹匣内；
- 出栈（pop）：只有栈顶元素才允许出栈，类似于枪射出子弹时，子弹从弹匣口依次进入枪体射出；
- 时间复杂度：
- 访问指定位置的元素：O(n) ——>需要依次遍历所有元素，所需元素可能在栈底
- 入栈和出栈：O(1) ——>只涉及栈顶
什么是队列？
- 队列（queue）是一种线性数据结构，队列中的元素按照先入先出的规则从队尾进入，队头出队；按照实现机制分为：单队列、循环队列；
为什么使用队列？
- 常见应用场景：KTV点歌列表、阻塞队列、线程池的任务队列等；
如何使用队列？
- 队列的实现结构可以是数组或链表实现
- 用数组实现的队列叫做顺序队列。在Java中，顺序队列使用java.util.ArrayDeque类实现；
- 用链表实现的队列叫做链式队列。在Java中，链式队列使用java.util.LinkedList类实现；
- 入队（enqueue）：只允许从队尾的位置放入元素，类似于银行取号等待叫号办理业务；
- 出队（dequeue）：只允许从队头的位置移出元素；
- 假溢出：使用数组实现队列，执行出队操作时，指向队头和队尾的指针会向后移，队尾指针移动到最后的时候，无法添加数据，即使数组中之前出队的位置还要空闲空间，这种现象就是“假溢出”。
1. 使用“栈”检查符号是否成对出现
public static boolean isValid(String s ){
HashMap<Character, Character> mappings = new HashMap<>();
mappings.put('}','{');
mappings.put(')','(');
mappings.put(']','[');
Stack<Character> stack = new Stack<>();
for(int i=0;i<s.length();i++){
char c =s.charAt(i);
if(mappings.containsKey(c)){
//当前字符是“右括号”
char topElement = stack.isEmpty() ? '#' :stack.pop();
char left = mappings.get(c);
if(left != topElement){
return false;
}
}else {
//当前字符是"左括号"
stack.push(c);
}
}
return stack.isEmpty();
}解读：
- 创建一个HashMap
mappings，用于存储右括号和对应的左括号的映射关系；- 创建一个Stack
stack，用于存储遍历过程中遇到的左括号，以便后续进行匹配检查；- 进入for循环，遍历输入的字符串s。在循环中，取出字符串中的每个字符c；
- 如果当前字符c存在于
mappings中，即为右括号，那么就从栈中弹出栈顶元素，然后检查该右括号对应的左括号是否与弹出的左括号匹配，如果不匹配则返回false；- 如果当前字符c不存在于
mappings中，即为左括号，将其压入栈中；- 循环结束后，检查栈是否为空，如果栈为空则说明所有的括号都匹配，返回true，否则返回false；
- 测试用例
public static void main(String[] args) {
String str ="{[(!)]}";
System.out.println(isValid(str));
}- 测试结果
2. 使用“栈”实现字符串反转
public static void main(String[] args) {
String str ="just do it";
StringBuilder stringBuilder = new StringBuilder(str);
//使用栈实现字符串反转
Stack<Character> stringStack = new Stack<>();
//入栈
for(int i=0;i<str.length();i++){
stringStack.push(str.charAt(i));
}
//出栈
while (!stringStack.empty()){
str +=stringStack.pop();
}
System.out.println(stringBuilder);
}解读：
- 创建一个Stack
stringStack，用于存储字符串中的字符；- 进入for循环，遍历输入的字符串
str，将字符串中的每个字符依次压入栈中；- 使用while循环，当栈不为空时，依次从栈中弹出字符，并将其拼接到原字符串
str的末尾；- 循环结束后，
str中存储的就是原字符串str的反转结果；
- 测试结果
3. 使用“队列”实现“栈”
public class MyStack{
private Queue<Integer> queue1; //出栈队列
private Queue<Integer> queue2; //入栈队列
public MyStack(){
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
public void push(int x){
queue2.offer(x);
while(!queue1.isEmpty()){
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop(){
return queue1.poll();
}
public int top(){
return queue1.peek();
}
public boolean empty(){
return queue1.isEmpty();
}
@Override
public String toString() {
return queue1.toString();
}
}解读：
- 定义了一个名为
MyStack的类，其中包含两个私有属性queue1和queue2，分别表示出栈队列和入栈队列，并在构造函数中对它们进行了初始化；push方法用于入栈操作，将元素加入queue2中，然后通过循环将queue1中的元素逐个转移到queue2中，以确保新入栈的元素位于队列的头部（因为队列的特性是先进先出）。最后交换queue1和queue2的引用，使得queue1始终指向当前栈中的元素所在的队列；pop方法用于出栈操作，直接从queue1中弹出元素即可；top方法用于获取栈顶元素，直接返回queue1的头部元素；empty方法用于判断栈是否为空，直接返回queue1是否为空的结果；用两个队列模拟栈的基本操作，通过不断在两个队列之间转移元素，使得栈的操作可以在队列上进行；
- 测试用例
public static void main(String[] args) {
MyStack myStack = new MyStack();
//入栈
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
System.out.println("入栈后"+myStack);
System.out.println("入栈后栈顶元素:"+myStack.top());
//出栈
myStack.pop();
myStack.pop();
myStack.pop();
myStack.pop();
myStack.pop();
System.out.println("出栈后"+myStack);
System.out.println("出栈后栈是否为空:"+myStack.empty());
}- 测试结果
4. 使用“栈”实现“队列”
public class Queue{
//入队栈
private Stack<Integer> inStack = new Stack<>();
//出队栈
private Stack<Integer> outStack = new Stack<>();
//入队
public void offer(int item){
while(!outStack.empty()){
inStack.push(outStack.pop());
}
//新元素入队
inStack.push(item);
}
//出队
public int poll(){
while(!inStack.empty()){
outStack.push(inStack.pop());
}
return outStack.pop();
}
//判断是否为空
public boolean empty(){
return outStack.size() == 0 && inStack.size() == 0;
}
@Override
public String toString() {
return inStack.toString();
}
}解读：
offer方法用于向队列中添加元素。首先，它会将 outStack 中的元素逐个弹出并压入 inStack 中，这样可以确保之前入队的元素在 inStack 的底部，新的元素可以被放在队列的末尾，接着，将新元素直接入栈到 inStack 中，表示将新元素放入队列中。poll方法用于从队列中取出元素。首先，它会将 inStack 中的元素逐个弹出并压入 outStack 中，这样可以确保队列的头部元素位于 outStack 的栈顶，然后，从 outStack 中弹出栈顶元素，并作为出队操作的结果返回。empty方法用于检查队列是否为空。只有当 inStack 和 outStack 都为空时，才表示整个队列为空；基于两个栈实现队列的方法称为双栈法，通过巧妙地利用栈的特性，可以实现队列的先进先出（FIFO）功能。在实际应用中，双栈法可以用于需要频繁进行队列操作的场景，同时也可以作为栈和队列之间的一个有趣的数据结构转换方式。
- 测试用例
public static void main(String[] args) {
Queue myQueue = new Queue();
//入队
myQueue.offer(1);
myQueue.offer(2);
myQueue.offer(3);
myQueue.offer(4);
myQueue.offer(5);
System.out.println("入队后:"+myQueue);
//出队
myQueue.poll();
myQueue.poll();
myQueue.poll();
myQueue.poll();
myQueue.poll();
System.out.println("出队后是否为空:"+myQueue.empty());
}- 测试结果
