共计 4986 个字符，预计需要花费 13 分钟才能阅读完成。
以下残缺代码均可从这里获取
栈
栈的基本概念
后进先出、先进后出就是典型的栈构造。栈能够了解成一种受了限度的线性表，插入和删除都只能从一端进行
当某个数据汇合只波及在一端插入和删除数据，并且满足后进先出、先进后出的个性，就应该首选“栈”这种数据结构（浏览器的后退、后退性能）
栈的实现
栈次要有两种操作，入栈和出栈，这里通过数组（程序栈）和链表（链式栈）两种形式实现栈
程序栈
package arrayStack
import "fmt"
type Item interface {}
type ItemStack struct {Items []Item
N int
}
//init stack
func (stack *ItemStack) Init() *ItemStack {stack.Items = []Item{}
return stack
}
//push stack Item
func (stack *ItemStack) Push(item Item) {if len(stack.Items) > stack.N {fmt.Println("栈已满")
return
}
stack.Items = append(stack.Items, item)
}
//pop Item from stack
func (stack *ItemStack) Pop() Item {if len(stack.Items) == 0 {fmt.Println("栈已空")
return nil
}
item := stack.Items[len(stack.Items) - 1]
stack.Items = stack.Items[0:len(stack.Items) - 1]
return item
}链式栈
package linkListStack
import "fmt"
type Item interface {}
type Node struct {
Data Item
Next *Node
}
type Stack struct {headNode *Node}
//push Stack item
func (stack *Stack) Push(item Item) {newNode := &Node{Data: item}
newNode.Next = stack.headNode
stack.headNode = newNode
}
//pop Item from stack
func (stack *Stack) Pop() Item {
if stack.headNode == nil {fmt.Println("栈已空")
return nil
}
item := stack.headNode.Data
stack.headNode = stack.headNode.Next
return item
}
func (stack *Stack) Traverse() {
if stack.headNode == nil {fmt.Println("栈已空")
return
}
currentNode := stack.headNode
for currentNode != nil {fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
}栈的利用场景
函数调用栈
操作系统给每个线程调配了一块独立的内存空间，这块内存被组织成“栈”这种构造, 用来存储函数调用时的长期变量。每进入一个函数，就会将长期变量作为一个栈帧入栈，当被调用函数执行实现，返回之后，将这个函数对应的栈帧出栈
起源：数据结构与算法之美
从这段代码的执行过程中理解函数调用栈
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}main()函数调用了 add() 函数，获取计算结果，并且与长期变量 a 相加，最初打印 res 的值。程序在执行过程中，main 函数中的变量会先后入栈，当执行到 add()函数时，add()函数中的长期变量也会先后入栈，后果如下：
阐明：内存中的堆栈和数据结构堆栈不是一个概念，内存中的堆栈是实在存在的物理区，数据结构中的堆栈是形象的数据存储构造
栈在表达式求值中的利用
一个表达式蕴含两个局部，数字和运算符。咱们用两个栈来实现表达式求值，一个栈用来存储数字，一个栈用来存储运算符
假如有这么一个表达式
1000+5*6-6从左向右遍历表达式，当遇到数字时，将数字放入到存储数字的栈；如果遇到运算符，将存储运算符栈的栈顶元素取出，进行优先级比拟
如果比运算符栈顶元素优先级高，则将以后运算符压入到存储运算符的栈中；如果比运算符栈顶元素低或优先级一样，则从存储数字的栈中取出两个元素，而后进行计算，将计算的后果放入到存储数字的栈中。反复上边的操作。过程如图：
栈在括号匹配中的利用
这也是一个比拟经典的题，就是给定一个括号串，验证它是否齐全匹配，如：
{{} 不匹配
[[{()}]] 匹配
([{}] 不匹配这个也能够用栈来解决。从左到右遍历括号串，遇到未匹配的左括号则将其压入栈中，遇到右括号时，从栈顶取出一个左括号，如果能匹配，则持续遍历后边的括号，当遍历完之后，栈为空了，阐明这个括号串是匹配的，否则是不匹配的。具体实现如下：
package bracketMatch
func BracketsMatch(str string) bool {brackets := map[rune]rune{')':'(', ']':'[', '}':'['}
var stack []rune
for _, char := range str {
if char == '(' || char == '[' || char == '{' {stack = append(stack, char)
} else if len(stack) > 0 && brackets[char] == stack[len(stack) - 1] {stack = stack[:len(stack) - 1]
} else {return false}
}
return len(stack) == 0
}
队列
队列的基本概念
先进先出就是典型的队列构造，队列也能够了解成一种受了限度的线性表，插入只能从队列尾部进行，删除只能从队列尾部进行。类比排队取票
队列的基本操作也只有两个，入队和出队。队列的利用的确是非常的宽泛，如音讯队列、阻塞队列、循环队列等
队列的实现
还是通过两种形式实现队列，通过数组实现程序队列，通过链表实现链式队列
实现队列须要两个指针，一个指向队列头部，一个指向队列尾部
程序队列
package arrayQueue
import "fmt"
type Item interface {}
type Queue struct {Queue []Item
Length int
}
func (queue *Queue) Init() {queue.Queue = []Item{}}
func (queue *Queue) Enqueue(data Item) {if len(queue.Queue) > queue.Length {fmt.Println("队列满了")
return
}
queue.Queue = append(queue.Queue, data)
}
func (queue *Queue) Dequeue() Item {if len(queue.Queue) == 0 {fmt.Println("队列空了")
return nil
}
item := queue.Queue[0]
queue.Queue = queue.Queue[1:]
return item
}链式队列
package linkListQueue
import "fmt"
type Item interface {}
type Node struct {
Data Item
Next *Node
}
type Queue struct {headNode *Node}
func (queue *Queue) Enqueue(data Item) {node := &Node{Data: data}
if queue.headNode == nil {queue.headNode = node} else {
currentNode := queue.headNode
for currentNode.Next != nil {currentNode = currentNode.Next}
currentNode.Next = node
}
}
func (queue *Queue) Dequeue() Item {
if queue.headNode == nil {fmt.Println("队列空了")
return nil
}
item := queue.headNode.Data
queue.headNode = queue.headNode.Next
return item
}
func (queue *Queue) Traverse() {
if queue.headNode == nil {fmt.Println("队列空的")
return
}
currentNode := queue.headNode
for currentNode.Next != nil {fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
fmt.Printf("%v\t", currentNode.Data)
}循环队列
为什么会呈现循环队列？
看下边这种状况，我有有一个长度是 5 的队列，目前队列是满的。假如当初我从队头取出 3 个元素之后，想再往队列中放入数据，其实是放不进去的，此时就呈现一个问题，队列有闲暇空间，然而却无奈向队列中放入数据了
其中一个解决办法就是，数据搬移 。然而这样的话，每次在出队的时候就等于说删除数组下标为 0 的元素，而且要将后边所有的数据向前搬移，这样就导致出队的工夫复杂度由原来的 O(1) 变成 O(n)，这种办法显然是不可取的
第二个方法就是应用一个 循环队列，很显著就是一个环，这几乎和单向循环链表截然不同。具体什么样，大家应该都非常的分明，它的难点就在于判空和判满
队列为空时：tail == head
队列为满时：(tail+1)%n == head哎，找法则问题，不行硬记住就能够了，间接看下边如何实现
循环队列的实现
package loopQueue
import "fmt"
type Item interface {}
const QueueSize = 5
type LoopQueue struct {Items [QueueSize]Item
Head int
Tail int
}
//init
func (queue *LoopQueue) Init() {
queue.Head = 0
queue.Tail = 0
}
//enqueue
func (queue *LoopQueue) Enqueue(data Item) {if ((queue.Tail + 1) % QueueSize) == queue.Head {fmt.Println("队列满了")
}
queue.Items[queue.Tail] = data
queue.Tail = (queue.Tail+1) % QueueSize
}
//dequeue
func (queue *LoopQueue) Dequeue() Item {
if queue.Head == queue.Tail {fmt.Println("队列空了")
return nil
}
item := queue.Items[queue.Head]
queue.Head = (queue.Head + 1) % QueueSize
return item
}
队列的利用场景
阻塞队列和并发队列
阻塞队列
在理论利用中，队列不会是有限长的，队列一旦有长度限度，就会有满的时候，当队列满了的时候，入队操作就会被阻塞，因为没有数据可取。而当队列为空时，出队是阻塞的，直到队列中有数据可取
没错，平时常常用到的 生产者 - 消费者模型 就是这样，通过队列能够轻松实现一个生产者 - 消费者模型
基于阻塞队列，还能够通过调整“生产者”和“消费者”的个数，来进步数据的解决效率
并发队列
对于上边的阻塞队列，在多线程的状况下，就会存在多个线程同时操作队列，这个时候就会存在线程平安问题（如果想理解底层起因，能够看我的这篇文章：过程治理之进程同步）
保障线程平安的队列就称之为并发队列，最简略的形式就是在入队和出队的时候加锁。对于锁，也能够看我这里的系列文章：线程锁系列
参考资料：
- 数据结构与算法之美
- 从零学习数据结构
