【LeetCode】两道栈相关的题目-394字符串解码，剑指Offer 09两个栈实现队列

本文主要是介绍【LeetCode】两道栈相关的题目-394字符串解码，剑指Offer 09两个栈实现队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第394题：字符串解码

题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = “3[a]2[bc]”
输出：“aaabcbc”

示例 2：

输入：s = “3[a2[c]]”
输出：“accaccacc”

思路：（1）用一个栈来进行控制，每次遇到数字时将其转化为相应的字符串（思考可能遇到连续的两个或三个数字的情况），遇到 ’ [ ’ 或字母的时候直接入栈，遇到 ’ ] '进行弹栈操作；（2）弹栈时，将弹出的字母放入另一个栈中，因为弹栈的顺序不对，弹完后进行栈的翻转操作，继续将 ’ [ '弹出栈，然后弹出数字，并用数字控制字符串的数目。

几个常规操作：

判断是否是数字 Character.isDigit(cur);
判断是否是字母 Character.isLetter(cur);
进栈操作 stack.addLast(digits); （栈选用的是LinkedList）
弹栈 stack.removeLast();
栈反转 Collections.reverse(sub);
获取栈顶元素 stk.peekLast();
字符串解析成数字 int rep = Integer.parseInt(stk.removeLast);

代码：

class Solution {//ptr为当前指针指向的字符串元素位置int ptr;public String decodeString(String s) {ptr = 0;//构造栈LinkedList<String> stack = new LinkedList<>();while(ptr < s.length()){char cur = s.charAt(ptr);//如果是数字，则构造数字的字符串if(Character.isDigit(cur)){String str = getDigit(s);stack.addLast(str);}else if(Character.isLetter(cur) || cur == '['){stack.addLast(String.valueOf(s.charAt(ptr++)));}//碰到了右括号else{++ptr;LinkedList<String> sub = new LinkedList<String>();while(!"[".equals(stack.peekLast())){sub.addLast(stack.removeLast());}//左括号弹栈stack.removeLast();int rep = Integer.parseInt(stack.removeLast());Collections.reverse(sub);String o = getString(sub);StringBuilder sb = new StringBuilder();while(rep>0){sb.append(o);rep--;}stack.addLast(sb.toString());}}return getString(stack);}/*** 将数字转化为字符串*/public String getDigit(String s){StringBuilder sb = new StringBuilder();while(Character.isDigit(s.charAt(ptr))){sb.append(s.charAt(ptr++));}return sb.toString();}/*** 将栈中的元素拼接为一个字符串*/public String getString(LinkedList<String> v){StringBuilder sb = new StringBuilder();for(String s : v){sb.append(s);}return sb.toString();}
}

剑指Offer 09题：两个栈实现队列

题目描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：

示例2：

输入：
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

思路：两个栈S1和S2，S1用来进行入栈操作，S2为辅助栈，当需要出栈时，判断S2是否为空，若S2非空，则将S2中的一个元素弹栈，若S2为空，则继续判断S1是否为空，若S1非空，则将S1中的全部元素压入S2中，否则不能进行弹栈操作。将S1全部压入S2中，能够保证先进先出。

class CQueue {Deque<Integer> stack1;Deque<Integer> stack2;public CQueue() {stack1 = new LinkedList<>();stack2 = new LinkedList<>();}public void appendTail(int value) {stack1.push(value);}public int deleteHead() {if(stack2.isEmpty()){if(stack1.isEmpty()){return -1;}else{while(!stack1.isEmpty()){int temp = stack1.pop();stack2.push(temp);}return stack2.pop();}}else{return stack2.pop();}}
}