平面设计免费网站,东莞整合网站建设推广,windows 2008 iis添加网站,城市房产网以下完整代码均可从这里获取栈栈的基本概念「后进先出、先进后出就是典型的栈结构」。栈可以理解成一种受了限制的线性表#xff0c;插入和删除都只能从一端进行当某个数据集合只涉及在一端插入和删除数据#xff0c;并且满足后进先出、先进后出的特性#xff0c;就应该首选… 以下完整代码均可从这里获取栈栈的基本概念「后进先出、先进后出就是典型的栈结构」。栈可以理解成一种受了限制的线性表插入和删除都只能从一端进行当某个数据集合只涉及在一端插入和删除数据并且满足后进先出、先进后出的特性就应该首选“栈”这种数据结构浏览器的前进、后退功能栈的实现栈主要有两种操作入栈和出栈这里通过数组顺序栈和链表链式栈两种方式实现栈顺序栈package arrayStackimport fmttype Item interface {}type ItemStack struct {Items []ItemN 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 linkListStackimport fmttype Item interface {}type Node struct {Data ItemNext *Node
}type Stack struct {headNode *Node
}//push Stack item
func (stack *Stack) Push(item Item) {newNode : Node{Data: item}newNode.Next stack.headNodestack.headNode newNode
}//pop Item from stack
func (stack *Stack) Pop() Item {if stack.headNode nil {fmt.Println(栈已空)return nil}item : stack.headNode.Datastack.headNode stack.headNode.Nextreturn item
}func (stack *Stack) Traverse() {if stack.headNode nil {fmt.Println(栈已空)return}currentNode : stack.headNodefor currentNode ! nil {fmt.Printf(%vt, 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()函数中的临时变量也会先后入栈结果如下 「说明内存中的堆栈和数据结构堆栈不是一个概念内存中的堆栈是真实存在的物理区数据结构中的堆栈是抽象的数据存储结构」栈在表达式求值中的应用一个表达式包含两个部分数字和运算符。我们用两个栈来实现表达式求值一个栈用来存储数字一个栈用来存储运算符假设有这么一个表达式10005*6-6从左向右遍历表达式当遇到数字时将数字放入到存储数字的栈如果遇到运算符将存储运算符栈的栈顶元素取出进行优先级比较如果比运算符栈顶元素优先级高则将当前运算符压入到存储运算符的栈中如果比运算符栈顶元素低或优先级一样则从存储数字的栈中取出两个元素然后进行计算将计算的结果放入到存储数字的栈中。重复上边的操作。过程如图 栈在括号匹配中的应用这也是一个比较经典的题就是给定一个括号串验证它是否完全匹配如{{} 不匹配
[[{()}]] 匹配
([{}] 不匹配这个也可以用栈来解决。从左到右遍历括号串遇到未匹配的左括号则将其压入栈中遇到右括号时从栈顶取出一个左括号如果能匹配则继续遍历后边的括号当遍历完之后栈为空了说明这个括号串是匹配的否则是不匹配的。具体实现如下package bracketMatchfunc BracketsMatch(str string) bool {brackets : map[rune]rune{):(, ]:[, }:[}var stack []runefor _, 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 arrayQueueimport fmttype Item interface {}type Queue struct {Queue []ItemLength 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 linkListQueueimport fmttype Item interface {}type Node struct {Data ItemNext *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.headNodefor 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.Dataqueue.headNode queue.headNode.Nextreturn item
}func (queue *Queue) Traverse() {if queue.headNode nil {fmt.Println(队列空的)return}currentNode : queue.headNodefor currentNode.Next ! nil {fmt.Printf(%vt, currentNode.Data)currentNode currentNode.Next}fmt.Printf(%vt, currentNode.Data)
}
循环队列为什么会出现循环队列看下边这种情况我有有一个长度是5的队列目前队列是满的。假设现在我从队头取出3个元素之后想再往队列中放入数据其实是放不进去的此时就出现一个问题队列有空闲空间但是却无法向队列中放入数据了 其中一个解决办法就是「数据搬移」。但是这样的话每次在出队的时候就等于说删除数组下标为0的元素而且要将后边所有的数据向前搬移这样就导致出队的时间复杂度由原来的O(1)变成O(n)这种方法显然是不可取的 第二个办法就是使用一个「循环队列」很明显就是一个环这简直和单向循环链表一模一样。具体什么样大家应该都十分的清楚它的难点就在于判空和判满队列为空时tail head
队列为满时(tail1)%n head
哎找规律问题不行硬记住就可以了直接看下边如何实现循环队列的实现package loopQueueimport fmttype Item interface {}const QueueSize 5
type LoopQueue struct {Items [QueueSize]ItemHead intTail int
}//init
func (queue *LoopQueue) Init() {queue.Head 0queue.Tail 0
}//enqueue
func (queue *LoopQueue) Enqueue(data Item) {if ((queue.Tail 1) % QueueSize) queue.Head {fmt.Println(队列满了)}queue.Items[queue.Tail] dataqueue.Tail (queue.Tail1) % 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) % QueueSizereturn item
}队列的应用场景阻塞队列和并发队列阻塞队列在实际应用中队列不会是无限长的队列一旦有长度限制就会有满的时候当队列满了的时候入队操作就会被阻塞因为没有数据可取。而当队列为空时出队是阻塞的直到队列中有数据可取没错平时经常用到的「生产者-消费者模型」就是这样通过队列可以轻松实现一个生产者-消费者模型基于阻塞队列还可以通过调整“生产者”和“消费者”的个数来提高数据的处理效率并发队列对于上边的阻塞队列在多线程的情况下就会存在多个线程同时操作队列这个时候就会存在线程安全问题如果想了解底层原因可以看我的这篇文章进程管理之进程同步保证线程安全的队列就称之为并发队列最简单的方式就是在入队和出队的时候加锁。关于锁也可以看我这里的系列文章线程锁系列参考资料数据结构与算法之美从零学习数据结构
