数据结构与算法系列之栈&队列(GO)

书旅 2020-11-09 10:50:11
算法 数据结构 数据 结构 法系



以下完整代码均可从这里获取

栈的基本概念

后进先出、先进后出就是典型的栈结构。栈可以理解成一种受了限制的线性表,插入和删除都只能从一端进行

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,就应该首选“栈”这种数据结构(浏览器的前进、后退功能)

栈的实现

栈主要有两种操作,入栈和出栈,这里通过数组(顺序栈)和链表(链式栈)两种方式实现栈

顺序栈
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
}

队列的应用场景

阻塞队列和并发队列
阻塞队列

在实际应用中,队列不会是无限长的,队列一旦有长度限制,就会有满的时候,当队列满了的时候,入队操作就会被阻塞,因为没有数据可取。而当队列为空时,出队是阻塞的,直到队列中有数据可取

没错,平时经常用到的生产者-消费者模型就是这样,通过队列可以轻松实现一个生产者-消费者模型

基于阻塞队列,还可以通过调整“生产者”和“消费者”的个数,来提高数据的处理效率

并发队列

对于上边的阻塞队列,在多线程的情况下,就会存在多个线程同时操作队列,这个时候就会存在线程安全问题(如果想了解底层原因,可以看我的这篇文章:进程管理之进程同步

保证线程安全的队列就称之为并发队列,最简单的方式就是在入队和出队的时候加锁。关于锁,也可以看我这里的系列文章:线程锁系列

参考资料:

  • 数据结构与算法之美
  • 从零学习数据结构
版权声明
本文为[书旅]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000037768401

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云