【数据结构】栈与队列的“双向奔赴”

目录

前言

1.使用“栈”检查符号是否成对出现

2.使用“栈”实现字符串反转

3.使用“队列”实现“栈”

4.使用“栈”实现“队列” 

---

前言

什么是栈？

• 栈（stack）是一种特殊的线性数据集合，只允许在栈顶按照后进先出LIFO（Last In First Out）进行数据操作；

为什么使用栈？

• 常见应用场景：浏览器的前进与回退操作、虚拟机栈等；

如何使用栈？

• 栈的实现结构可以是一维数组或链表实现
• 用数组实现的栈叫做顺序栈。在Java中，顺序栈使用java.util.Stack类实现
• 用链表实现的栈叫做链式栈。在Java中，链式栈使用java.util.LinkedList类实现；
• 入栈（push）：将新元素放入栈顶，只允许从栈顶一侧放入元素，类似于弹匣装弹，只能从弹匣口依次压入弹匣内；

• 出栈（pop）：只有栈顶元素才允许出栈，类似于枪射出子弹时，子弹从弹匣口依次进入枪体射出；

• 时间复杂度：

1. 访问指定位置的元素：O(n)        ——>需要依次遍历所有元素，所需元素可能在栈底
2. 入栈和出栈：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();}@Overridepublic 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;}@Overridepublic 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());}

• 测试结果