数据结构-队列与栈

队列与栈是最常使用的两种数据结构，其中，队列的核心特征是先入先出，栈的核心特征是后入先出，只要符合这两个特征，就属于队列（栈），不因实现形式的不同（数组或链表）而有差别，可以根据具体情况选择使用起来更方便的实现形式。

在本文中，我们对队列与栈的核心功能，循环队列这种特殊结构，以及队列和栈的主要应用，尤其是广度优先搜索和深度优先搜索进行介绍。

1. 队列

队列是一个先入先出的数据结构，插入时新元素只能添加到队列末尾，取出时只能获取第一个元素。也因此我们需要维护两个指针。

1.1 队列实现

队列的实现可以使用动态数组或链表，最基本的功能包括：插入，删除，取第一个元素以及判空。由于 Golang 切片的易操作性，队列的实现即为简单，front 和 rear 指针被隐藏了起来。

1
2
3
4
5
queue := make([]int,0) // 建立队列
queue = append(queue, value)  // 插入元素
queue = queue[1:] // 删除元素
value := queue[0] // 取第一个元素
if len(queue) == 0 {} // 判空

但当我们使用链表实现时，头尾指针是必需的，维持头和尾两个指针可以将插入和删除操作的复杂度保持在$O(1)$。

1.2 利用标准库实现

Go 没有提供内置的队列库，是因为可以很容易使用链表实现，只要保证新元素添加到链表尾，取元素从链表头取即可。

1
2
3
4
5
queue := list.New() // 建立队列
queue.PushBack(value) // 入队：添加新元素到末尾
queue.Front().Value.(valueType) // 获取队首元素
queue.Remove(queue.Front()).(valueType) // 出队：删除队首元素
queue.Len() // 队列长度

1.3 循环队列

队列对空间的浪费比较严重，这从上面的程序中可以看出，因为数组在在不停地延长，而头指针之前指向的空间都没有被释放。循环队列是解决该问题的一种办法，主要思路是重用之前被浪费的存储。

循环队列使用一段固定的空间，当尾指针指向队列尾时，如果有新元素添加进来而队列非空，可以将尾指针重新指向最开始的存储空间。循环队列的核心是队列空和满的判定，我们少用一个元素来区分队列空和队列满，约定 front 指向队列头元素，rear 指向队列尾元素的下一个位置，队列内容为 $[front,rear)$。

 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
// 循环队列结构定义
type MyCircularQueue struct {
    queue []int
    front,rear int // front指向第一个元素，rear指向最后一个元素的下一个位置
}


/** Initialize your data structure here. Set the size of the queue to be k. */
func Constructor(k int) MyCircularQueue {
    return MyCircularQueue{make([]int,k+1),0,0}
}


/** Insert an element into the circular queue. Return true if the operation is successful. */
func (this *MyCircularQueue) EnQueue(value int) bool {
    if this.IsFull() {
        return false
    }
    this.queue[this.rear] = value
    this.rear = (this.rear + 1) % len(this.queue) //尾指针防止溢出
    return true
}


/** Delete an element from the circular queue. Return true if the operation is successful. */
func (this *MyCircularQueue) DeQueue() bool {
    if this.IsEmpty() {
        return false
    }
    this.front = (this.front + 1) % len(this.queue) //头指针防止溢出
    return true
}


/** Get the front item from the queue. */
func (this *MyCircularQueue) Front() int {
    if this.IsEmpty() {
        return -1
    }
    return this.queue[this.front]
}


/** Get the last item from the queue. */
func (this *MyCircularQueue) Rear() int {
    if this.IsEmpty() {
        return -1
    }
    return this.queue[(this.rear - 1 + len(this.queue)) % len(this.queue)] //尾指针返回正确的位置
}


/** Checks whether the circular queue is empty or not. */
func (this *MyCircularQueue) IsEmpty() bool {
    if this.front == this.rear {
        return true
    }
    return false
}


/** Checks whether the circular queue is full or not. */
func (this *MyCircularQueue) IsFull() bool {
    if (this.rear + 1) % len(this.queue) == this.front {
        return true
    }
    return false
}

使用链表实现循环队列时在细节上可能有所不同。

2. 队列与BFS

广度优先搜索（BFS）的实现与队列是密不可分的，最常用在树和图中，使用非常普遍。下面使用伪代码提供两个模板，一个是遍历，一个是找最短路径，这两个模板足够应付绝大多数题目。

2.1 遍历

遍历的伪代码模板如下，核心思想就是将初始节点入队，然后在循环中对队列头元素的所有邻居节点进行处理，如果没有被访问过就入队。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func BFS(root Node) {
    create queue  // 创建队列，存储所有待处理结点
    create visited // 标记已访问过的结点
    add root to queue // 根结点入队
    // BFS
    for queue is not empty {
        var cur Node = the first node in queue
        remove the first node from queue // 实际情况可将以上两步合并为一步
        add cur to visited // 标记当前结点为已访问
        for curNeighbor  := range the neighbors of cur {
            if curNeighbor not in visited {
                 add next to queue
            }     
        }
    }
}

以「岛屿数量」题目为例，给出一个改模板的使用示例。leetcode题目地址

 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
// 题目描述
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或
垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例输入:
11000
11000
00100
00011

输出: 3
// 程序
func numIslands(grid [][]byte) int {
    var res int
    for i := 0; i < len(grid); i++ {
        for j :=0 ; j < len(grid[i]); j++ {
            // 将连成一篇的陆地算作1个
            if grid[i][j] == '1' {
                BFS(grid,i,j)
                res++
            }
            
        }
    }
    return res
}

type point struct {
    x,y int
}

func BFS(grid [][]byte, x,y int) {
    queue := []point{}
    queue = append(queue,point{x,y})
    grid[x][y] = '0'
    
    //以“右->下->左->上”顺序循环，dx,dy是每一种转向的坐标变化方式
	dx := []int{0, 1, 0, -1}
	dy := []int{1, 0, -1, 0}

    for len(queue) != 0 {
        cur := queue[0]
        queue = queue[1:]
        
        for i := 0; i < 4; i++ {
            nx,ny := cur.x + dx[i],cur.y + dy[i]
            // 坐标超出界限或当前邻居结点为水域，进入下一个循环
            if nx < 0 || nx >= len(grid) || ny < 0 || ny >= len(grid[cur.x]) || grid[nx][ny] == '0' { 
                continue
            }
            queue = append(queue,point{nx,ny})
            grid[nx][ny] = '0' // 入队时标记已访问，防止重复入队，陷入循环
        }
    }
}

2.2 最短路径

寻找最短路径的伪代码模板如下

 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
// 如果找到返回最短路径
func BFS(root, target Node) int {
    create queue          // 创建队列，存储所有待处理结点
    create visited        // 标记已访问过的结点
    var shortestPath int  // 根结点到当前节点的最短路径
    // 初始化
    add root to queue
    add root to visited
    // BFS
    for queue is not empty {
        shortestPath++
        int size = queue.length();
        for  i = 0; i < size; i++ {
            var cur Node = the first node in queue;
            return shortestPath if cur is target;
            for curNeighbor := range the neighbors of cur {
                if curNeighbor is not in visited {
                    add next to queue
                    add next to visited
                }
            }
            remove the first node from queue
        }
    }
    return -1;          // 找不到最短路径
}

注：如果确定没有循环（比如树中）或者确实希望将结点多次加入队列，则不需要使用 visited 标记已访问结点。

这里有一些总结的技巧

已访问列表可充分利用原题的数组或链表值实现
已访问列表可使用 map 实现
使用 map 实现时，值类型为 bool 或 int 可用于不同的场景
对当前节点的所有邻居节点进行访问，如果是数组，可使用方向数组完成，其它场景则根据具体情况决定

3. 栈

如下图，栈是一个后入先出的数据结构，插入（Push）和删除（Pop）都只能在栈顶操作。

3.1 栈实现

使用动态数组的简单实现如下

 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
var stack []int

// 初始化
func Constructor() {
    stack = make([]int,0)
}

// 入栈
func Push(value int) bool {
	stack = append(stack, value)
	return true
}

// 出栈
func Pop() bool {
	if len(stack) == 0 {
		return false
	}
	stack = stack[:len(stack)-1]
	return true
}

// 获取栈顶元素
func Top() int {
	if len(stack) == 0 {
		return -1
	}
	return stack[len(stack)-1]
}

// 判空
func IsEmpty() bool {
	if len(stack) != 0 {
		return false
	}
	return true
}

3.2 内置库

与对了相同，栈也可以很容易地使用 Go 提供的链表库实现

1
2
3
4
5
stack := list.New() // 建立队列
stack.PushBack(value) // 入队：添加新元素到末尾
stack.Back().Value.(valueType) // 获取队首元素
stack.Remove(queue.Back()).(valueType) // 出队：删除队首元素
stack.Len() // 队列长度

3.3 例子：有效括号

这是一个最经典也最简单的栈使用的例子，题目描述如下，leetcode题目地址

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func isValid(s string) bool {
	a := map[rune]rune{
		'(': ')',
		'[': ']',
		'{': '}',
	}
	stack := []rune{}
	for _, v := range s {
		if len(stack) != 0 && a[stack[len(stack)-1]] == v {
			stack = stack[:len(stack)-1]
			continue
		}
		stack = append(stack, v)
	}
	if len(stack) != 0 {
		return false
	}
	return true
}

4. 栈和DFS

类似的，深度优先搜索（DFS）是栈的一种核心使用场景。DFS有两种实现方式，一种是递归，尽管递归的实现看起来没有使用栈，但实际上使用的是系统提供的隐式栈，也称为调用栈（Call Stack）；另一种就是显式的使用栈。

DFS 无法像 BFS 一样计算最短路径。

4.1 递归（隐式栈）

递归的模板如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func DFS(cur, target Node, visited map[Node]bool) bool {
    create visited // 标记已访问结点
    return true if cur is target
    for next : each neighbor of cur {
        if next is not in visited {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

仍以队列中的「岛屿数量」一题为例，DFS 递归解法如下

 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
type point struct {
	x, y int //x,y分别为行号和列号
}

func numIslands(grid [][]byte) int {
	var res int
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
            // 连在一起的陆地算一个
			if grid[i][j] == '1' {
				res++
				DFS(grid, i, j)
			}
		}
	}
	return res
}

func DFS(grid [][]byte, row, col int) {
    //以“右->下->左->上”顺序循环，dx,dy是每一种转向的坐标变化方式
	dx := []int{-1, 0, 1, 0}
	dy := []int{0, -1, 0, 1}

	grid[row][col] = '0'

	for i := 0; i < 4; i++ {
		nx, ny := row+dx[i], col+dy[i]
		if nx < 0 || nx >= len(grid) || ny < 0 || ny >= len(grid[row]) || grid[nx][ny] == '0' {
			continue
		}
        // 当前邻居结点满足条件，标记为已访问，并递归对该结点执行DFS
		grid[nx][ny] = '0'
		DFS(grid, nx, ny)
	}
}

4.2 显式栈

显式栈的模板如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func DFS(root,target Node) {
    create stack
    create visited
    add root to stack;
    for stack is not empty {
        var cur Node = the top element in stack
        remove cur from stack
        return true if cur is target
        for Node next : the neighbors of cur {
            if next is not in visited {
                add next to stack
                add next to visited
            }
        }      
    }
    return false
}

「岛屿数量」一题的 DFS 显式栈解法如下

 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
type point struct {
    x,y int //x,y分别为行号和列号
}
func numIslands(grid [][]byte) int {
	var res int
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == '1' {
				res++
                DFS(grid,i,j)
			}
		}
	}
	return res
}

func DFS(grid [][]byte, row,col int) {   
    stack := []point{}
    stack = append(stack,point{row,col})
    grid[row][col] = '0'
    
    //以“右->下->左->上”顺序循环，dx,dy是每一种转向的坐标变化方式
    dx := []int{-1,0,1,0}
    dy := []int{0,-1,0,1}
    
    for len(stack) != 0 {
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]      
        
        for i := 0; i < 4; i++ {
            nx,ny := cur.x+dx[i],cur.y+dy[i]
            if nx < 0 || nx >= len(grid) || ny < 0 || ny >= len(grid[row]) || grid[nx][ny] == '0' {
                continue
            }
            // 满足条件的结点标记为已访问并入栈
            grid[nx][ny] = '0'
            stack = append(stack,point{nx,ny})
        }
    }  
}

5. 其它

最后一部分介绍两种非常常见的问法：用栈实现队列，用队列实现栈

5.1 用栈实现队列

使用两个栈实现，最普通的思路是，每次出队时，将栈中的元素弹入一个临时栈，然后取出栈底元素，最后将临时栈的元素再放回去。但这样时间复杂度比较高，另一种合适的做法是，设立一个入栈，一个出栈，入队时将元素放入入栈，出队时从出栈的栈顶取元素，如果出栈为空，将此时入栈的所有元素弹入出栈，然后取栈顶元素。这样做可以将时间复杂度缩减到 $O(1)$

 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
type MyQueue struct {
    in []int
    out []int
}


/** Initialize your data structure here. */
func Constructor() MyQueue {
    return MyQueue{}
}


/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
    this.in = append(this.in,x)
}


/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
    if len(this.out) == 0 {
        for i := len(this.in)-1; i >= 0; i-- {
            this.out = append(this.out,this.in[i])
        }
        this.in = nil
    }
    pop := this.out[len(this.out)-1]
    this.out = this.out[0:len(this.out)-1]
    return pop
}


/** Get the front element. */
func (this *MyQueue) Peek() int {
    if len(this.out)==0{
        for i:=len(this.in)-1; i>=0; i--{
            this.out = append(this.out, this.in[i])
        }
        this.in = nil
    }
    return this.out[len(this.out)-1]
}


/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
    if len(this.in) == 0 && len(this.out) == 0{
        return true
    }else{
        return false
    }
}

5.2 用队列实现栈

使用两个队列实现，只能使用笨办法，每次出栈将所有元素放到临时队列，取队尾元素，然后再将临时队列的元素放回去。如果使用链表实现，可以将最后一步简化为交换两个队列的头指针。

 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
type MyStack struct {
    q []int
    t []int
}


/** Initialize your data structure here. */
func Constructor() MyStack {
    return MyStack{}
}


/** Push element x onto stack. */
func (this *MyStack) Push(x int)  {
    this.q = append(this.q,x)
}


/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
    if this.Empty() {
        return -1
    }
    for len(this.q) > 1 {
        this.t = append(this.t,this.q[0])
        this.q = this.q[1:]
    }
    pop := this.q[0]
    this.q = nil
    if this.t != nil {
        for i := 0; i < len(this.t); i++ {
            this.q = append(this.q,this.t[i])
        }
    }
    this.t = nil
    return pop
}


/** Get the top element. */
func (this *MyStack) Top() int {
    if this.Empty() {
        return -1
    }
    for len(this.q) > 1 {
        this.t = append(this.t,this.q[0])
        this.q = this.q[1:]
    }
    pop := this.q[0]
    this.q = nil
    this.t = append(this.t,pop)
    if this.t != nil {
        for i := 0; i < len(this.t); i++ {
            this.q = append(this.q,this.t[i])
        }
    }
    this.t = nil
    return pop
}


/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
    if len(this.q) == 0 {
        return true
    }else{
        return false
    }
}