加入收藏 | 设为首页 | 会员中心 | 我要投稿 聊城站长网 (https://www.0635zz.com/)- 智能语音交互、行业智能、AI应用、云计算、5G!
当前位置: 首页 > 综合聚焦 > 编程要点 > 语言 > 正文

Go语言有无队列和栈结构

发布时间:2023-07-05 14:31:51 所属栏目:语言 来源:
导读:这篇文章主要介绍“Go语言有没有队列和栈结构”,在日常操作中,相信很多人在Go语言有没有队列和栈结构问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Go语言有没有
这篇文章主要介绍“Go语言有没有队列和栈结构”,在日常操作中,相信很多人在Go语言有没有队列和栈结构问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Go语言有没有队列和栈结构”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
 
Go语言中没有队列和栈相关的数据结构;但可以借助切片来实现栈与队列的操作。go语言实现栈和队列主要用到append和切片(用内置数组类型进行操作),创建栈和队列的语法“make([]int, 0)”,入栈和入队的语法“append(stack, 10)”,出栈的语法“v:=stack[len(stack)-1] stack = stack[:len(stack)-1]”。
 
go语言中,并没有栈与队列相关的数据结构,但是我们可以借助切片来实现栈与队列的操作;接下来我们一起实现栈与队列基本操作,并且还会实现用栈实现队列,用队列实现栈的操作。
 
实现栈与队列基本操作
 
1、栈基本操作
 
go语言实现栈和队列主要用到append 和切片(用内置数组类型进行操作)
 
 
//创建栈
 
stack := make([]int, 0)
 
//push压入栈
 
stack = append(stack, 10)
 
//pop弹出
 
v := stack[len(stack)-1]
 
stack = stack[:len(stack)-1]
 
//检查栈空
 
len(stack) == 0
 
2、队列基本操作
 
//创建队列
 
queue := make([]int, 0)
 
//enqueue入队
 
queue = append(queue, 10)
 
//dequeue出队
 
v := queue[0]
 
queue = queue[1:]
 
//检查队列为空
 
len(queue) == 0
 
用栈实现队列
 
1、理论
 
使用栈来模式队列的行为,如果仅仅用一个栈,是一定不行的,所以需要两个栈一个输入栈,一个输出栈,这里要注意输入栈和输出栈的关系。
 
下面动画模拟以下队列的执行过程如下:
 
执行语句:
 
 
queue.push(1);
 
queue.push(2);
 
queue.pop(); 注意此时的输出栈的操作
 
queue.push(3);
 
queue.push(4);
 
queue.pop();
 
queue.pop();注意此时的输出栈的操作
 
queue.pop();
 
queue.empty();
 
在push数据的时候,只要数据放进输入栈就好,但在pop的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部导入进来(注意是全部导入),再从出栈弹出数据,如果输出栈不为空,则直接从出栈弹出数据就可以了。
 
最后如何判断队列为空呢?如果进栈和出栈都为空的话,说明模拟的队列为空了。
 
2、算法题
 
接下来看一下LeetCode原题
 
232. 用栈实现队列
 
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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(双端队列)来模拟一个栈,只要是标准的栈操作即可。
 
3、思路
 
解决这个问题,需要一个输出栈和输入栈
 
先将数据放到输入栈,再把数据从输入栈放到输出栈,此时输出栈输出数据的顺序就和队列一样了,先入先出
 
4、代码部分
 
type MyQueue struct {
 
stackIn  []int // 用来保存Push数据
 
stackOut []int // 用来保存Pop数据
 
}
 
// 栈构造器
 
func Constructor() MyQueue {
 
return MyQueue{
 
stackIn:  make([]int, 0),
 
stackOut: make([]int, 0),
 
}
 
}
 
func (this *MyQueue) Push(x int) {
 
// 判断stackOut中是否有元素,有的话全部放到stackIn
 
for len(this.stackOut) != 0 {
 
val := this.stackOut[len(this.stackOut)-1]
 
this.stackOut = this.stackOut[:len(this.stackOut)-1]
 
this.stackIn = append(this.stackIn, val)
 
}
 
// 将数据加进stackIn
 
this.stackIn = append(this.stackIn, x)
 
}
 
func (this *MyQueue) Pop() int {
 
// 判断stackIn中是否有元素,有的话全部放到stackOut
 
for len(this.stackIn) != 0 {
 
val := this.stackIn[len(this.stackIn)-1]
 
this.stackIn = this.stackIn[:len(this.stackIn)-1]
 
this.stackOut = append(this.stackOut, val)
 
}
 
// stackOut为零,说明没有元素,return 0
 
if len(this.stackOut) == 0 {
 
return 0
 
}
 
// stackOut Pop 元素
 
res := this.stackOut[len(this.stackOut)-1]
 
this.stackOut = this.stackOut[:len(this.stackOut)-1]
 
return res
 
}
 
func (this *MyQueue) Peek() int {
 
// 调用Pop()方法
 
val := this.Pop()
 
// val为零,说明没有元素,return 0
 
if val == 0 {
 
return 0
 
}
 
// Pop()方法删除了val,这里加上
 
this.stackOut = append(this.stackOut, val)
 
return val
 
}
 
func (this *MyQueue) Empty() bool {
 
// 两个栈都为空,说明为空,否则不为空
 
return len(this.stackOut) == 0 && len(this.stackIn) == 0
 
}
 
代码可以直接拿到力扣上运行。我已经将细节全部用注释解释了,如果不懂可以私信博主。
 
用队列实现栈
 
1、理论
 
队列模拟栈,其实一个队列就够了,那么我们先说一说两个队列来实现栈的思路。
 
队列是先进先出的规则,把一个队列中的数据导入另一个队列中,数据的顺序并没有变,并没有变成先进后出的顺序。
 
所以用栈实现队列, 和用队列实现栈的思路还是不一样的,这取决于这两个数据结构的性质。
 
但是依然还是要用两个队列来模拟栈,只不过没有输入和输出的关系,而是另一个队列完全用又来备份的!
 
如下面动画所示,用两个队列que1和que2实现队列的功能,que2其实完全就是一个备份的作用,把que1最后面的元素以外的元素都备份到que2,然后弹出最后面的元素,再把其他元素从que2导回que1。
 
模拟的队列执行语句如下:
 
 
queue.push(1);        
 
queue.push(2);        
 
queue.pop();   // 注意弹出的操作       
 
queue.push(3);        
 
queue.push(4);       
 
queue.pop();  // 注意弹出的操作    
 
queue.pop();    
 
queue.pop();    
 
queue.empty();
 
Go语言有没有队列和栈结构
 
2、算法题
 
接下来看一下LeetCode原题225. 用队列实现栈
 
请你仅使用两个队列实现一个后入先出(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(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
 
3、思路
 
用两个队列que1和que2实现队列的功能,que2其实完全就是一个备份的作用,把que1最后面的元素以外的元素都备份到que2,然后弹出最后面的元素,再把其他元素从que2导回que1。
 
4、使用两个队列实现
 
type MyStack struct {
 
    //创建两个队列
 
    queue1 []int
 
    queue2 []int
 
}
 
 
func Constructor() MyStack {
 
    return MyStack{ //初始化
 
        queue1:make([]int,0),
 
        queue2:make([]int,0),
 
    }
 
}
 
 
func (this *MyStack) Push(x int)  {
 
     //先将数据存在queue2中
 
    this.queue2 = append(this.queue2,x)
 
   //将queue1中所有元素移到queue2中,再将两个队列进行交换
 
    this.Move()
 
}
 
 
func (this *MyStack) Move(){    
 
    if len(this.queue1) == 0{
 
        //交换,queue1置为queue2,queue2置为空
 
        this.queue1,this.queue2 = this.queue2,this.queue1
 
    }else{
 
        //queue1元素从头开始一个一个追加到queue2中
 
            this.queue2 = append(this.queue2,this.queue1[0])  
 
            this.queue1 = this.queue1[1:] //去除第一个元素
 
            this.Move()     //重复
 
    }
 
}
 
func (this *MyStack) Pop() int {
 
    val := this.queue1[0]
 
    this.queue1 = this.queue1[1:] //去除第一个元素
 
    return val
 
}
 
 
func (this *MyStack) Top() int {
 
    return this.queue1[0] //直接返回
 
}
 
 
func (this *MyStack) Empty() bool {
 
return len(this.queue1) == 0
 
}
 
5、优化
 
其实这道题目就是用一个队列就够了。
 
一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时在去弹出元素就是栈的顺序了。
 
6、使用一个队列实现
 
type MyStack struct {
 
    queue []int//创建一个队列
 
}
 
 
/** Initialize your data structure here. */
 
func Constructor() MyStack {
 
    return MyStack{   //初始化
 
        queue:make([]int,0),
 
    }
 
}
 
 
/** Push element x onto stack. */
 
func (this *MyStack) Push(x int)  {
 
    //添加元素
 
    this.queue=append(this.queue,x)
 
}
 
 
/** Removes the element on top of the stack and returns that element. */
 
func (this *MyStack) Pop() int {
 
    n:=len(this.queue)-1//判断长度
 
    for n!=0{ //除了最后一个,其余的都重新添加到队列里
 
        val:=this.queue[0]
 
        this.queue=this.queue[1:]
 
        this.queue=append(this.queue,val)
 
        n--
 
    }
 
    //弹出元素
 
    val:=this.queue[0]
 
    this.queue=this.queue[1:]
 
    return val
 
    
 
}
 
 
/** Get the top element. */
 
func (this *MyStack) Top() int {
 
    //利用Pop函数,弹出来的元素重新添加
 
    val:=this.Pop()
 
    this.queue=append(this.queue,val)
 
    return val
 
}
 
 
/** Returns whether the stack is empty. */
 
func (this *MyStack) Empty() bool {
 
    return len(this.queue)==0
 
}
 
 

(编辑:聊城站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!