今天是开启栈与队列的第一天！
题目链接：232. 用栈实现队列
状态：多次尝试后取得AC
看到题目时第一想法：思路并不难想，用一次栈就会颠倒一次顺序，那正好两个栈就倒回来了。所以本题主要还是考察栈的基本方法的使用。
熟悉一下stack的几个方法： 以Stack<Integer> stackIn; 为例
stackIn.push(element); // 把element放入栈中
stackIn.pop(element); // 把element弹出栈外
stackIn.peek(); // 读取栈顶元素
stackIn.isEmpty(); // 判断栈是否为空
所以本题思路就是利用两个栈颠倒两次元素来使得出栈的元素顺序与队列相同的目的。除此之外，本题还有个很经典的思路值得学习：代码复用：相同的代码可以抽取为一个方法，然后就可以在多个地方调用。还有个好处就是 当方法需要修改时，改一处就等于改全部。如果没有代码复用，则需要每一处都需要手动修改，很麻烦。完整代码如下：
class MyQueue {
Stack<Integer> stackIn;
Stack<Integer> stackOut;
public MyQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
}
// push element x to the back of queue
public void push(int x) {
stackIn.push(x);
}
// remove the element from in front of queue and returns that element
public int pop() {
dumpstackIn();
return stackOut.pop();
}
// get the front element
public int peek() {
dumpstackIn();
return stackOut.peek();
}
// returns whether the queue is empty
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
// if the stackOut is empty, then put all elements in stackIn to stackOut
private void dumpstackIn(){
if(!stackOut.isEmpty()) return;
while(!stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
时间复杂度: push和empty为O(1), pop和peek为O(n)
空间复杂度: O(n)
题目链接：225. 用队列实现栈
状态：一次性AC
看到题目时第一想法：思路并不难，按照上一题的思路：既然栈和队列的出栈方向不同，那么就用两个队列来调整至与栈相同的方向就好。但是为了节约时间，我直接看了解析，发现了另一种方法。这种方法是每次将元素放入队列中时，都把其前面的元素重新加入到队列中，使得新放入到元素在出口的第一位置。这种做法的好处在于只需用一个queue就可以实现stack。具体动画效果和分析可看这里
完整代码如下：
class MyStack { //Java
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
// put x in the queue
queue.offer(x);
int size = queue.size();
// reload other elements to the back of the queue,
// so that the x become the first one of the front
while(size-- > 1){
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.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();
*/
复杂度分析：除了push方法的时间复杂度是O(n)以外，其他的 无论是时间复杂度或者空间复杂度都是O(1)。这也很好理解，因为每次push都要移动n-1个元素至队列入口处，所以是O(n)级别。
题目链接：20. 有效的括号
状态：多次尝试后AC。
看到题目时第一想法：思路好像有点难，因为要处理的情况挺多的。
但是仔细研究后发现其实一共就三种情况：1. 左括号多了；2. 右括号多了； 3. 括号不匹配（中括号匹配花括号）。所有的情况均可用这三种情况解决，例如 ( [ ) ] 就属于括号不匹配。所以思路就清晰了：每当遇到左括号时，就把对应的右括号加入到双向队列deque中（用栈也可以）。然后每当遇到右括号时，就看右括号是否与deque的顶元素相同，如果相同就弹出元素，如果不相同就是上述情况3，于是就return false；如果当需要判断右括号是否匹配时发现deque为空，则说明右括号多了，触发情况2，也要return false；最后一种情况是当遍历string结束后，发现deque仍有元素，说明触发情况1，也要return false。以下是完整代码：
class Solution { // Java
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList<>();
char ch;
for(int i = 0; i < s.length(); i++){
ch = s.charAt(i);
// when seeing a left bracket, push the corresponding right bracket onto the deque.
if(ch == '('){
deque.push(')');
}else if(ch == '{'){
deque.push('}');
}else if(ch == '['){
deque.push(']');
}else if(deque.isEmpty() || deque.peek() != ch){
// deque is empty means when adding a left bracket, but there is no right bracket in the deque
// top element != ch means the top right bracket isn't the corresponding one
// both cases indicate that this is an invalid string.
return false;
}else{ // right bracket matches the top element
deque.pop();
}
}
return deque.isEmpty();
}
}
复杂度分析：
时间复杂度：O(n). 因为需要遍历整个字符串s，然后遍历的每个元素要么是push，要么是pop，这些都是O(1)。所以总体时间复杂度是O(n)
空间复杂度：O(n). 因为最坏的情况是全是左括号，那么此时deque内需要装 s.length() 个元素。其他的辅助变量例如ch 都是常数级别。因此总体来说空间复杂度是O(n)
题目链接：1047. 删除字符串中的所有相邻重复项
状态：一次性AC。
看到题目时第一想法：好像一个栈就解决了。思路就是遍历每个元素，然后与栈顶元素进行判断，如果相同就弹出，如果不同就放入栈。
需要注意的是，最终要把结果输出成字符串的时候需要注意顺序。完整代码如下：
class Solution { // Java
public String removeDuplicates(String s) {
ArrayDeque<Character> deque = new ArrayDeque<>();
char ch;
for(int i = 0; i < s.length(); i++){
ch = s.charAt(i);
if(deque.isEmpty() || deque.peek() != ch){
deque.push(ch);
}else{
deque.pop();
}
}
String str = "";
while(!deque.isEmpty()){
str = deque.pop() + str;
}
return str;
}
}
复杂度分析：
时间复杂度：O(n). 因为for循环是O(n)，while循环最坏情况也是O(n)，循环内部都是O(1)，所以综合是O(n)
空间复杂度：O(n). 因为最坏情况没有消除的情况下，deque需要装 s.length() 个元素，此时str也需要装这么多个。而其他的都是O(1)， 例如ch。因此，两个O(n)，其余都是O(1)，综合下来还是O(n)。
这里拓展一个方法二 --- 双指针法
思路是快慢双指针，快指针用来遍历字符串，慢指针用来记录有效字符。
快指针从0开始，每次循环稳定+1.
慢指针从0开始，每次循环时先把快指针的元素赋值到当前慢指针的位置，然后需判断：如果当前位置的元素与上一个位置的元素相同，则慢指针退一步，否则就进一步。
当循环结束时，从初始位置到慢指针的位置就是有效字符了。
完整代码如下：
class Solution { // Java
public String removeDuplicates(String s) {
char[] ch = s.toCharArray();
int fast = 0;
int slow = 0;
while(fast < s.length()){
// 直接用fast指针覆盖slow指针的值
ch[slow] = ch[fast];
// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
if(slow > 0 && ch[slow] == ch[slow - 1]){
slow--;
}else{
slow++;
}
fast++;
}
return new String(ch,0,slow);
}
}
复杂度分析：
时间复杂度：O(n). 因为while循环需要遍历整个字符数组char[] ch，其余都是O(1)忽略不计。
时间复杂度：O(n). 字符数组char[] ch是O(n)， 最后new的数组最坏情况也是O(n)，快慢指针是O(1)忽略不计，所以总共是O(n).
