当前位置：首页 > news >正文

代码随想录算法训练营第九天|232.用栈实现队列，225.用队列实现栈，20.有效的括号，1047.删除字符串中的所有相邻重复项

news 2026/8/16 13:37:16

232.用栈实现队列

看到题目的第一想法

看完代码随想录的第一想法

用栈模拟队列需要定义输入栈和输出栈，将内容放到输入栈中，再将内容放到输出栈中，取出来就是队列的先进先出

用自己的话描述

设置两个栈 stackIn 和 stackOut。push 操作直接压入 stackIn。pop/peek 操作时，如果 stackOut 为空，就把 stackIn 的所有元素依次弹出并压入 stackOut（这样顺序就反转了，相当于队列的先进先出）。然后从 stackOut 弹出/查看顶部元素。关键点是 dumpstackIn() 只在 stackOut 为空时才执行，均摊时间复杂度 O(1)。

代码

classMyQueue{Stack<Integer>stackIn;Stack<Integer>stackOut;publicMyQueue(){stackIn=newStack<>();stackOut=newStack<>();}publicvoidpush(intx){stackIn.push(x);}publicintpop(){dumpstackIn();returnstackOut.pop();}publicintpeek(){dumpstackIn();returnstackOut.peek();}publicbooleanempty(){returnstackIn.isEmpty()&&stackOut.isEmpty();}privatevoiddumpstackIn(){if(!stackOut.isEmpty())return;while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}}

实现过程中遇到哪些困难

没有困难

今日收获，记录一下自己的学习时长

学习时长：18 分钟

225.用队列实现栈

代码

classMyStack{//先创建两个栈Queue<Integer>queue1;Queue<Integer>queue2;publicMyStack(){//堆两个栈进行初始化queue1=newLinkedList<>();queue2=newLinkedList<>();}publicvoidpush(intx){//先放入副队列queue2.offer(x);while(!queue1.isEmpty()){queue2.offer(queue1.poll());}//交换引用Queue<Integer>queueTemp;queueTemp=queue1;queue1=queue2;queue2=queueTemp;}publicintpop(){//直接弹出队头元素returnqueue1.poll();}publicinttop(){//查看队头元素returnqueue1.peek();}publicbooleanempty(){//主队列不为空returnqueue1.isEmpty();}}/** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */

实现过程中遇到哪些困难

没什么困难，就是语法不熟悉

今日收获，记录一下自己的学习时长

收获了队列语法的使用，学习时长：20 分钟

20.有效的括号

看到题目的第一想法

将符号一一对应消除确实是没想法

看完代码随想录的第一想法

用栈这个数据结构确实是可以解决

用自己的话描述

了解了数据结构用简单的if判断一下很快就出来了。总体而言就是，先把内容放进去，然后再判断是否对应然后进行弹出，只不过我代码里的把内容放进去是在判断的字符的后面，不过也必须要在判断字符的后面，因为字符内容需要先判断清楚才能放入

代码

classSolution{publicbooleanisValid(Strings){//先定义一个栈Stack<Character>stack=newStack<>();for(charc:s.toCharArray()){//判断字符的另一半，如果存在就弹出，如果不存在就存入if(c==')'&&!stack.isEmpty()&&stack.peek()=='('){stack.pop();}elseif(c=='}'&&!stack.isEmpty()&&stack.peek()=='{'){stack.pop();}elseif(c==']'&&!stack.isEmpty()&&stack.peek()=='['){stack.pop();}else{stack.push(c);}}//如果stack为空那就正常，返回true反之为falsereturnstack.isEmpty();}}

实现过程中遇到哪些困难

对栈的类不太熟悉，思路不清晰

今日收获，记录一下自己的学习时长

学习到了 Stack 这个栈，学习时长：16 分钟（9:42-9:58）

1047.删除字符串中的所有相邻重复项

看到题目的第一想法

都是消消乐的类型，应该也是用到栈去解决

看完代码随想录的第一想法

确实是用到了栈这个数据结构，消消乐的思想和上一题基本差不多，不过这题学习新的类

用自己的话描述

将字符串拆成一个个字符放入栈，每一次放入都看看栈顶是不是不一样或空，符合就放入，发现一样就拿出栈顶元素，剩下的就是倒序的字符了，然后排个序即可

代码

classSolution{publicStringremoveDuplicates(Strings){//定义一个双端队列来做栈,一个字符变量（用来接单个字符）ArrayDeque<Character>deque=newArrayDeque<>();charc;//遍历字符串，如果栈为空，或栈顶元素不一样就放进去，如果发现一样就消除for(inti=0;i<s.length();i++){c=s.charAt(i);if(deque.isEmpty()||deque.peek()!=c){deque.push(c);}else{deque.pop();}}//剩下的元素就是删除所有相邻重复项之后的元素，但是为倒序Stringstr="";//倒序数特殊处理一下while(!deque.isEmpty()){str=deque.pop()+str;}returnstr;}}