02.数据结构——栈与队列

数据结构—栈与队列

相关数据结构实现用go语言实现

相关代码做题合集：https://github.com/longpi1/algorithm-pattern

go 通过切片模拟栈和队列

栈

栈是一种后进先出（LIFO, Last-In-First-Out）的数据结构。Go 没有内置的栈类型，但可以使用切片或链表实现栈。

定义和特点

  • 栈支持两种主要操作：
    • Push（入栈）：将元素添加到栈顶。
    • Pop（出栈）：从栈顶移除并返回元素。
  • 其他辅助操作包括检查栈是否为空、获取栈长度等。
1
2
3
4
5
6
7
8
9
10
切片模拟栈
// 创建栈
stack:=make([]int,0)
// push压入
stack=append(stack,10)
// pop弹出
v:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
// 检查栈空
len(stack)==0

队列

队列是一种先进先出（FIFO, First-In-First-Out）的数据结构。Go 没有内置的队列类型，但可以使用切片或链表实现队列。

定义和特点

  • 队列支持两种主要操作：
    • Enqueue（入队）：将元素添加到队列尾部。
    • Dequeue（出队）：从队列头部移除并返回元素。
  • 其他辅助操作包括检查队列是否为空、获取队列长度等。
1
2
3
4
5
6
7
8
9
// 创建队列
queue:=make([]int,0)
// enqueue入队
queue=append(queue,10)
// dequeue出队
v:=queue[0]
queue=queue[1:]
// 长度0为空
len(queue)==0

相关练习题

20. 有效的括号

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。


示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false


提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成


🧠 解题思路
判断括号的有效性可以使用「栈」这一数据结构来解决。

我们遍历给定的字符串 s。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。

当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。

在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，返回 True，否则返回 False。

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程。

*/

func isValid(s string) bool {
    n := len(s)
    // 注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程。
    if n % 2 == 1 {
        return false
    }
    // 使用 rune 类型存储括号对，提高效率
    m := map[rune]rune{
        '(': ')',
        '{': '}',
        '[': ']',
    }
    
    // 使用动态切片实现栈
    var stack []rune
    
    // 直接迭代字符串的字符，避免使用 strings.Split
    for _, char := range s {
        // 如果是开括号，压入栈
        if _, ok := m[char]; ok {
            stack = append(stack, char)
        } else {
            // 如果是闭括号
            // 检查栈是否为空
            if len(stack) == 0 {
                return false
            }
            
            // 获取栈顶的开括号
            lastOpening := stack[len(stack)-1]
            
            // 检查是否匹配
            if m[lastOpening] != char {
                return false
            }
            
            // 弹出栈顶元素
            stack = stack[:len(stack)-1]
        }
    }
    
    // 检查栈是否为空
    return len(stack) == 0
}




232. 用栈实现队列

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。


示例 1：

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

🧠 解题思路
队列的特性是 FIFO（先入先出），而栈的特性是 FILO（先入后出）。

知道两者特性之后，我们需要用两个栈来模拟队列的特性，一个栈为入队栈，一个栈为出对栈。

当出队栈存在内容时，出队栈的栈顶，即为第一个出队的元素。

若出队栈无元素，我们的需求又是出队的话，我们就需要将入队栈的内容反序导入出队栈，然后弹出栈顶即可。

注意：根据栈的的特性，我们仅能使用 push 和 pop 操作。

*/


type MyQueue struct {
	in, out []int
}

func Constructor() MyQueue {
	return MyQueue{in: make([]int, 0), out: make([]int, 0)}
}

func (this *MyQueue) Push(x int) {
	for len(this.out) != 0 {
		num := this.out[len(this.out)-1]
		this.in = append(this.in, num)
		this.out = this.out[0 : len(this.out)-1]
	}
	this.in = append(this.in, x)
}

func (this *MyQueue) Pop() int {
	for len(this.in) != 0 {
		num := this.in[len(this.in)-1]
		this.out = append(this.out, num)
		this.in = this.in[0 : len(this.in)-1]
	}
	result := this.out[len(this.out)-1]
	this.out = this.out[0 : len(this.out)-1]
	return result
}

func (this *MyQueue) Peek() int {
	for len(this.in) != 0 {
		num := this.in[len(this.in)-1]
		this.out = append(this.out, num)
		this.in = this.in[0 : len(this.in)-1]
	}
	if len(this.out) == 0 {
		return -1
	}
	return this.out[len(this.out)-1]
}

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

225. 用队列实现栈

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
61
62
63
64
65
66
67
68
69
/*
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。


注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。


示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

🧠 解题思路
根据题意，要用两个队列来实现栈，首先我们知道，队列是先进先出，栈是后进先出。

知道了以上要点，我们两个队列的用处也就一目了然了。

一个队列为主队列，一个为辅助队列，当入栈操作时，我们先将主队列内容导入辅助队列，然后将入栈元素放入主队列队头位置，再将辅助队列内容，依次添加进主队列即可。
*/


type MyStack struct {
	queue1, queue2 []int
}

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

func (this *MyStack) Push(x int) {
	this.queue2 = append(this.queue2, x)
	for len(this.queue1) != 0 {
		tmp := this.queue1[0]
		this.queue1 = this.queue1[1:]
		this.queue2 = append(this.queue2, tmp)
	}
	this.queue1, this.queue2 = this.queue2, this.queue1
}

func (this *MyStack) Pop() int {
	tmp := this.queue1[0]
	this.queue1 = this.queue1[1:]
	return tmp
}

func (this *MyStack) Top() int {
	return this.queue1[0]
}

func (this *MyStack) Empty() bool {
	return len(this.queue1) == 0
}




#原创 #数据结构 #算法
02.数据结构——栈与队列
https://blog.longpi1.com/2025/05/30/02-数据结构栈与队列/