栈和队列.md

栈满足先进后出，队列满足先进先出。
## [用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks/)
```typescript
class MyQueue {
private queue: number[] = [];
push(value: number): void {
this.queue.push(value);
}
pop(): number | undefined {
return this.queue.shift();
}
peek(): number | undefined {
return this.queue[0];
}
empty(): boolean {
return !this.queue.length;
}
}
```
## [用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/)
```typescript
class MyStack {
private stack: number[] = [];
push(value: number): void {
this.stack.push(value);
}
pop(): number | undefined {
return this.stack.shift();
}
top(): number {
const n = this.stack.length;
return this.stack[n - 1];
}
empty(): boolean {
return !this.stack.length;
}
}
```
## [滑动窗口的最小值](https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/)
> 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里面的最大值。
```typescript
function maxSlidingWindow(nums: number[], k: number): number[] {
const { length } = nums;
if (!k || !length) return [];
const deque: number[] = [];
for (let i = 0; i < k; i++) {
cleanDeque(deque, nums, i, k);
deque.push(i);
}
const res: number[] = [];
res.push(nums[deque[0]]);
for (let i = k; i < length; ++i) {
cleanDeque(deque, nums, i, k);
deque.push(i);
res.push(nums[deque[0]]);
}
return res;
}
/**
* 刷新双端队列
* @param queue
* @param nums
* @param index
* @param k
*/
function cleanDeque(
queue: number[],
nums: number[],
index: number,
k: number
): void {
// 如果双向队列中包含不是滑动窗口的数，直接出队
if (queue.length && index >= k + queue[0]) {
queue.shift();
}
while (queue.length && nums[index] > nums[queue[queue.length - 1]]) {
queue.pop();
}
}
```
## [有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
> 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
>
> 有效字符串需满足：
>
> 左括号必须用相同类型的右括号闭合。
> 左括号必须以正确的顺序闭合。
> 注意空字符串可被认为是有效字符串。
```typescript
function isValid(s: string): boolean {
const n = s.length
if (n % 2) return false
const stack: string[] = []
let index = 0
while (index < n) {
const letter = s[index]
if (letter === '(' || letter === '{' || letter === '[') stack.push(letter)
else {
switch (letter) {
case ')': {
if (stack.pop() !== '(') return false
break
}
case '}': {
if (stack.pop() !== '{') return false
break
}
case ']': {
if (stack.pop() !== '[') return false
break
}
}
}
index++
}
return !stack.length
}
```
## [字符串解码](https://leetcode-cn.com/problems/decode-string/)
> 给定一个经过编码的字符串，返回它解码后的字符串。
>
> 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
>
> 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
>
> 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
>
```typescript
function decodeString(s: string): string {
const stack: string[] = []
for (const char of s) {
if (char !== ']') {
stack.push(char)
continue
}
// 每当遇到 ']' 的时候，就可以把栈里面的数据取出来，然后计算出之前的字母的数量
let cur = stack.pop()
let str = '' // 括号内的字母
while (cur !== '[') {
str = cur + str
cur = stack.pop()
}
cur = stack.pop()
let num = '' // 括号前的数字
while (!isNaN(+cur!)) {
num = cur + num
cur = stack.pop()
}
cur && stack.push(cur) // 把上一次的字母加回去
stack.push(str.repeat(+num))
}
return stack.join('')
}
```
## [根据身高建队列](https://leetcode-cn.com/problems/queue-reconstruction-by-height/)
> 假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
>
> 注意：
> 总人数少于1100人。
```typescript
function reconstructQueue(people: number[][]): number[][] {
const n = people.length
if (!n) return []
// 按身高进行降序排列，然后按照前面的人数进行升序排列
people.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]))
const res: number[][] = []
for (let i = 0; i < n; i++) {
res.splice(people[i][1], 0, people[i])
}
return res
}
```
## [数组中的第 k 个最大元素](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/)
> 在未排序的数组中找到第 **k** 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
```typescript
function findKthLargest(nums: number[], k: number): number {
nums.sort((a, b) => b - a)
return nums[k - 1]
}
```