一、栈与队列 —— 概念解释

栈：又称为后进先出（Last In First Out）的结构，简称LIFO机构。
队列：又称为先进先出（First In First Out）的结构，简称FIFO结构。

二、案例详解 —— 232. 用栈实现队列（简单）

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks

思路分析：

代码：

class MyQueue {public static Stack<Integer> inStack;public static Stack<Integer> outStack;public MyQueue() {inStack = new Stack<Integer>();outStack = new Stack<Integer>();}public void push(int x) {inStack.push(x);}public int pop() {if(outStack.isEmpty()) {inStackToOutStack();}return outStack.pop();}public int peek() {// peek方法是查看栈顶元素，但不取出if(outStack.isEmpty()) {inStackToOutStack();}return outStack.peek();}public boolean empty() {if (inStack.isEmpty() && outStack.isEmpty()) {return true;}return false;}public void inStackToOutStack() {while (!inStack.isEmpty()){outStack.push(inStack.pop());}}
}

三、案例详解 —— 394. 字符串解码（中等）

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string

思路：
0、准备2个栈，字符串栈和数字栈，num表示数字，result表示[ ]之内的字符串
1、是数字，可能是非单个的数字，所以需要重组数字，用num表示
2、是 ‘[’ ，开始压栈，数字进数字栈，字符串进字符串栈，初始化num 和 result
3、是 ‘]’ ，开始出栈，数字出栈，字符串出栈，并且字符串后面拼接n个重复的字符串result
4、其它的情况，则将字符都拼接在result

代码：

    public String decodeString(String s) {Stack<String> stringStack = new Stack<>(); // 字符串栈Stack<Integer> integerStack = new Stack<>(); // 数字栈int num = 0;// 保存数字StringBuilder result = new StringBuilder(); // 保存重复输出的字符串char[] chars = s.toCharArray();for(int i=0;i<chars.length;i++) {if (Character.isDigit(chars[i])) {// 连续的数字，考虑到不止是个位的数字num = num*10 + chars[i]-'0';} else if (chars[i] == '[') {// 开始数字进栈和字符串进栈if (num > 0) integerStack.push(num);stringStack.push(result.toString());// num 和 result重新初始化num = 0;result = new StringBuilder();} else if (chars[i] == ']') {// 数字出栈和字符串出栈int n = integerStack.pop();StringBuilder sb = new StringBuilder(stringStack.pop());// 重复拼接n个result字符串for (int j = 0;j<n;j++) {sb.append(result);}result = sb;} else {// 其他字符都拼接在resultresult.append(chars[i]);}}return result.toString();