栈和队列

栈：FILO先入后出。

队列: FIFO先入先出。

1. 设计循环队列

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/kzlb5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class MyCircularQueue { int head; int tail; int size; int[] tab;
public MyCircularQueue(int k) { tab = new int[k]; head = 0; tail = -1; } public boolean enQueue(int value) { if(isFull()) { return false; } tail++; tail = tail % tab.length; tab[tail] = value; size++; return true; } public boolean deQueue() { if(isEmpty()){ return false; } tab[head++] = -1; head = head % tab.length; size--; return true; } public int Front() { if(isEmpty()){ return -1; } return tab[head]; } public int Rear() { if(isEmpty()){ return -1; } return tab[tail]; } public boolean isEmpty() { return size == 0; } public boolean isFull() { return size >= tab.length; } }
2. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/g9d0h/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路：此题可以用栈来解，把左括号压入栈中，碰到右括号就从栈中弹出进行匹配，如果不匹配就返回false.

class Solution { public boolean isValid(String s) { ArrayDeque stack = new ArrayDeque<>(); for(int i = 0; i < s.length(); i++) { char ch = s.charAt(i); if(stack.isEmpty()) { stack.push(ch); continue; } switch(ch){ case '}' : if(stack.poll() != '{') return false; break; case ']' : if(stack.poll() != '[') return false; break; case ')' : if(stack.poll() != '(') return false; break; default : stack.push(ch); } ; } if(stack.isEmpty()) { return true; } return false; } } 3. 每日温度

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/genw3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {     public int[] dailyTemperatures(int[] T) {         ArrayDeque arrayDeque = new ArrayDeque();         int[] result = new int[T.length];
        for(int i = 0; i < T.length; i++) {             if(arrayDeque.isEmpty() || T[arrayDeque.peek()] >= T[i]) {                 arrayDeque.push(i);             } else{                 while(!arrayDeque.isEmpty() && T[arrayDeque.peek()] < T[i] ){                     int index = arrayDeque.pop();                     result[index] = i - index;                 }                 arrayDeque.push(i);             }         }
        return result;     } } 4. 逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/gomvm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路：碰到算术题，使用栈解决。碰到数字就压栈，碰到运算符，就弹出栈中的两个数字进行运算，把运算结果压入栈。

class Solution { public int evalRPN(String[] tokens) { ArrayDeque arrayDeque = new ArrayDeque<>(); int num2; int num1; for(String s : tokens) { switch(s) { case "+" : num2 = arrayDeque.pop(); num1 = arrayDeque.pop(); arrayDeque.push(num1 + num2); break; case "-": num2 = arrayDeque.pop(); num1 = arrayDeque.pop(); arrayDeque.push(num1 - num2); break; case "*": num2 = arrayDeque.pop(); num1 = arrayDeque.pop(); arrayDeque.push(num1 * num2); break; case "/": num2 = arrayDeque.pop(); num1 = arrayDeque.pop(); arrayDeque.push(num1 / num2); break; default: arrayDeque.push(Integer.valueOf(s)); } } return arrayDeque.pop(); } } 5.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/gvtxe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class MyQueue {     ArrayDeque stack1;     ArrayDeque stack2;
    /** Initialize your data structure here. */     public MyQueue() {         stack1 = new ArrayDeque<>();         stack2 = new ArrayDeque<>();     }          /** Push element x to the back of queue. */     public void push(int x) {         if(empty()) {             stack1.push(x);         } else{             while(!stack1.isEmpty()) {                 stack2.push(stack1.pop());             }             stack2.push(x);
            while(!stack2.isEmpty()) {                 stack1.push(stack2.pop());             }         }
    }          /** Removes the element from in front of queue and returns that element. */     public int pop() {         return stack1.pop();     }          /** Get the front element. */     public int peek() {         return stack1.peek();     }          /** Returns whether the queue is empty. */     public boolean empty() {         return stack1.isEmpty();     } }

6. 用队列实现栈

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/gw7fg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class MyStack { LinkedList queue1; LinkedList queue2;
/** Initialize your data structure here. */ public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } /** Push element x onto stack. */ public void push(int x) { if(empty()) { queue1.add(x); } else { while(!queue1.isEmpty()) { queue2.add(queue1.poll()); } queue1.add(x); while(!queue2.isEmpty()) { queue1.add(queue2.poll()); } } } /** Removes the element on top of the stack and returns that element. */ public int pop() { return queue1.poll(); } /** Get the top element. */ public int top() { return queue1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue1.isEmpty(); } }

7.字符串解码

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

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

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

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

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/gdwjv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路：通过压栈把字符，数字和[压入。当碰到 ] 时。弹出栈知道出现 [ 结束、

class Solution {     private int ptr = 0;     public String decodeString(String s) {         if(s == null || s.length() <= 0) {             return "";         }         StringBuilder sb = new StringBuilder();         ArrayDeque stack = new ArrayDeque<>();
        while(ptr < s.length()) {             char ch = s.charAt(ptr);             if (Character.isDigit(ch)) {                 stack.push(getDigits(s));             } else if(Character.isLetter(ch) || ch == '[') {                 stack.push(String.valueOf(ch));                 ptr++;             } else {                 ptr++;                 LinkedList subList = new LinkedList<>();                 int repeat = 0;                 while(!"[".equals(stack.peek())) {                     subList.addFirst(stack.pop());                 }                 String subStr = getString(subList);                 stack.pop();                 repeat = Integer.valueOf(stack.pop());                 StringBuilder subSb = new StringBuilder();                 while(repeat-- > 0) {                     subSb.append(subStr);                 }                 stack.push(subSb.toString());             }
        }         while(!stack.isEmpty()) {             sb.append(stack.pollLast());         }
        return sb.toString();     }
    private String getString(LinkedList subList) {         StringBuilder sb = new StringBuilder();         for(String str : subList) {             sb.append(str);         }
        return sb.toString();     }
    private String getDigits(String s) {         StringBuilder sb = new StringBuilder();         while(Character.isDigit(s.charAt(ptr))){             sb.append(s.charAt(ptr++));         }         return sb.toString();     } }

算法栈和队列

栈和队列

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

【基础】排序算法学习笔记

常用的排序算法介绍和在JAVA的实现（一）

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

标签