代码随想录第九天 ｜ 栈与队列part01

那很好了，时间来到了第九天，⏰
理论基础
了解一下 栈与队列的内部实现机制，文中是以C++为例讲解的。
文章讲解：https://programmercarl.com/栈与队列理论基础.html
232.用栈实现队列
大家可以先看视频，了解一下模拟的过程，然后写代码会轻松很多。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0232.用栈实现队列.html
题目感想：
1.这里只要求实现四种方法：判空，获取队列首个，移除队列首个，往队尾加入元素；这里使用两个栈来实现，一个输入栈，一个输出栈，具体实现可以看以下代码，值得考虑的是，如果让输出队列中的全部元素该怎么做，我想的是先输出输出栈中的，然后再将输入栈中的元素按要求输出；
点击查看代码

1. class MyQueue {
3.     Stack<Integer> stackIn;
4.     Stack<Integer> stackOut;
6.     /** Initialize your data structure here. */
7.     public MyQueue() {
8.         stackIn = new Stack<>(); // 负责进栈
9.         stackOut = new Stack<>(); // 负责出栈
10.     }
11.    
12.     /** Push element x to the back of queue. */
13.     public void push(int x) {
14.         stackIn.push(x);
15.     }
16.    
17.     /** Removes the element from in front of queue and returns that element. */
18.     public int pop() {   
19.         dumpstackIn();
20.         return stackOut.pop();
21.     }
22.    
23.     /** Get the front element. */
24.     public int peek() {
25.         dumpstackIn();
26.         return stackOut.peek();
27.     }
28.    
29.     /** Returns whether the queue is empty. */
30.     public boolean empty() {
31.         return stackIn.isEmpty() && stackOut.isEmpty();
32.     }
34.     // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
35.     private void dumpstackIn(){
36.         if (!stackOut.isEmpty()) return;
37.         while (!stackIn.isEmpty()){
38.                 stackOut.push(stackIn.pop());
39.         }
40.     }
41. }

复制代码

• 用队列实现栈
  可能大家惯性思维，以为还要两个队列来模拟栈，其实只用一个队列就可以模拟栈了。
  建议大家掌握一个队列的方法，更简单一些，可以先看视频讲解
  题目链接/文章讲解/视频讲解：https://programmercarl.com/0225.用队列实现栈.html
  题目感想：
  1.可以使用两个队列或者一个队列，如果是两个队列，一个主队列进行输入输出，另外一个负责备份，这里指的是每次输入的时候将队伍里面的元素全部转移到备份队伍，然后将新输入的元素排到队首，再将之前的旧元素排入；
  2.如果使用一个队列的话，输入了新的元素后，将前面的元素依次排到新元素后面去，也可以实现；
  

• 有效的括号
  讲完了栈实现队列，队列实现栈，接下来就是栈的经典应用了。
  大家先自己思考一下 有哪些不匹配的场景，在看视频 我讲的都有哪些场景，落实到代码其实就容易很多了。
  题目链接/文章讲解/视频讲解：https://programmercarl.com/0020.有效的括号.html
  题目感想：
  1.首先是思考有哪些不能匹配到的场景，首先是左括号匹配不到右括号，也就是遍历完字符串之后栈不为空，字符串为空了；然后是右括号多了匹配不到，最后是左右括号的数量相等，不匹配；
  2.入栈时可以先将这个的对应的另外一半入栈，遇到相等的就消去；
  3.也可以一匹配就消去；
  

• 删除字符串中的所有相邻重复项
  栈的经典应用。
  要知道栈为什么适合做这种类似于爱消除的操作，因为栈帮助我们记录了 遍历数组当前元素时候，前一个元素是什么。
  题目链接/文章讲解/视频讲解：https://programmercarl.com/1047.删除字符串中的所有相邻重复项.html
  题目感想：
  1.可以使用字符串直接作为栈；
  2.也可以使用双指针进行操作；
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！