用栈实现队列

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

实现 MyQueue 类：

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

使用双栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
type MyQueue struct {
    stackIn     []int
    stackOut    []int
}


func Constructor() MyQueue {
    return MyQueue{
        stackIn:    make([]int,0),
        stackOut:   make([]int,0),
    }
}


func (this *MyQueue) Push(x int)  {
    this.stackIn = append(this.stackIn,x)
}


func (this *MyQueue) Pop() int {
    inlen , outlen := len(this.stackIn) , len(this.stackOut)
    if outlen == 0{
        if inlen == 0 {
            return -1 
        }
        for i:=inlen-1;i>=0 ;i--{
            this.stackOut = append(this.stackOut,this.stackIn[i])
        }
    }
    outlen = len(this.stackOut)
    val := this.stackOut[outlen-1]
    this.stackOut = this.stackOut[:outlen-1]
    return val 
}

func (this *MyQueue) Peek() int {
    val := this.Pop()
    if val == -1 {
        return -1 
    }
    this.stackOut = append(this.stackOut, val)
    return val 
}


func (this *MyQueue) Empty() bool {
    return len(this.stackIn)==0 && len(this.stackOut)==0
}

用队列实现栈

没啥好说的，简直了

不理解为什么一定要用队列实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
type MyStack struct {
    queue []int // 使用队列作为栈的底层数据结构
}

func Constructor() MyStack {
    return MyStack{
        queue: make([]int, 0),
    }
}

func (this *MyStack) Push(x int) {
    this.queue = append(this.queue, x) // 向队列末尾添加新元素，实现入栈操作
}

func (this *MyStack) Pop() int {
    if len(this.queue) == 0 {
        return -1 // 如果队列为空，表示栈为空，返回特殊值
    }
    lastIndex := len(this.queue) - 1 // 获取队尾索引
    val := this.queue[lastIndex]     // 取出栈顶元素
    this.queue = this.queue[:lastIndex] // 移除队尾元素，即栈顶元素
    return val
}

func (this *MyStack) Top() int {
    if len(this.queue) == 0 {
        return -1 // 如果队列为空，表示栈为空，返回特殊值
    }
    return this.queue[len(this.queue)-1] // 返回队尾元素，即栈顶元素
}

func (this *MyStack) Empty() bool {
    return len(this.queue) == 0 // 如果队列为空，表示栈为空
}

有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func isValid(s string) bool {
    hash := map[byte]byte{')':'(', ']':'[', '}':'{'}
    stack := make([]byte, 0)
    if len(stack)%2==1{
        return false 
    }
    if s == "" {
        return true
    }

    for i := 0; i < len(s); i++ {
        if s[i] == '(' || s[i] == '[' || s[i] == '{' {
            stack = append(stack, s[i])
        } else if len(stack) > 0 && stack[len(stack)-1] == hash[s[i]] {
            stack = stack[:len(stack)-1]
        } else {
            return false
        }
    }
    return len(stack) == 0
}

删除字符串中所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func removeDuplicates(s string) string {
    stack := make([]byte,0)
    if len(s)==0{
        return s 
    }
    stack = append(stack,s[0])
    for i:=1 ;i<len(s);i++{
        n := len(stack)
        if n>0 && s[i] == stack[n-1] {
            stack = stack [:n-1]
            continue 
        }
        stack = append(stack,s[i])
    }
    return string(stack)
}

逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。
1
2
3
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func evalRPN(tokens []string) int {
    stack := []int{}
    for _ , token := range tokens{
        val , err := strconv.Atoi(token)
        if err == nil{
            stack = append(stack,val)
        }else{// 有错误就表示输入的不是数字的字符形式
            num1 ,num2 := stack[len(stack)-2] ,stack[len(stack)-1]
            stack = stack[:len(stack)-2]
            switch token{
                case "+":
                    stack = append(stack, num1+num2)
                case "-":
                    stack = append(stack, num1-num2)
                case "*":
                    stack = append(stack,num1*num2)
                case "/":
                    stack = append(stack,num1/num2)
            }
        }
    }
    return stack[0]
}

strconv.Atoi string->int

strconv.Itoa int->string

移动窗口——单调队列

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package main

import "fmt"

type MyQueue struct {
	queue []int
}

func NewMyQueue() *MyQueue {
	return &MyQueue{}
}

func (q *MyQueue) Front() int {
	return q.queue[0]
}

func (q *MyQueue) Back() int {
	return q.queue[len(q.queue)-1]
}

func (q *MyQueue) Empty() bool {
	return len(q.queue) == 0
}

// 这个val表示的是新加入的元素
func (q *MyQueue) Push(val int) {
	for !q.Empty() && q.Back() < val {
		q.queue = q.queue[:len(q.queue)-1]
	}
	q.queue = append(q.queue, val)
}

// 这个val表示的是移动窗口前一位元素
func (q *MyQueue) Pop(val int) {
	if !q.Empty() && q.Front() == val {
		q.queue = q.queue[1:]
	}
}

func maxSlidingWindow(nums []int, k int) []int {
	var res []int
	q := NewMyQueue()
	for i := 0; i < k; i++ {
		q.Push(nums[i])
	}
	res = append(res, q.Front())
	for i := k; i < len(nums); i++ {
		q.Pop(nums[i-k]) //输入移动窗口前一位元素
		q.Push(nums[i])  //输入移动窗口新元素
		res = append(res, q.Front())
	}
	return res
}

func main() {
	nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
	k := 3
	res := maxSlidingWindow(nums, k)
	fmt.Println(res)
}