Go语言实现栈与队列基本操作学家_F11 - 专业站长和开发者的学习网站

分享到

Go语言实现栈与队列基本操作学家

Golang 来源：互联网作者：佚名发布时间：2022-11-12 21:30:56 人浏览

摘要

go语言中，并没有栈与队列相关的数据结构，但是我们可以借助切片来实现栈与队列的操作；接下来我们一起实现栈与队列基本操作，并且还会实现用栈实现队列，用队列实现栈的操作

go语言中，并没有栈与队列相关的数据结构，但是我们可以借助切片来实现栈与队列的操作；接下来我们一起实现栈与队列基本操作，并且还会实现用栈实现队列，用队列实现栈的操作。

二、实现栈与队列基本操作

2.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.2 队列基本操作

//创建队列

queue := make([]int, 0)

//enqueue入队

queue = append(queue, 10)

//dequeue出队

v := queue[0]

queue = queue[1:]

//检查队列为空

len(queue) == 0

三、用栈实现队列

3.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的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

3.2 算法题

接下来看一下LeetCode原题

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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.3 思路

解决这个问题，需要一个输出栈和输入栈

先将数据放到输入栈，再把数据从输入栈放到输出栈，此时输出栈输出数据的顺序就和队列一样了，先入先出

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

}

代码可以直接拿到力扣上运行。我已经将细节全部用注释解释了，如果不懂可以私信博主。

四、用队列实现栈

4.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.empty();

4.2 算法题

接下来看一下LeetCode原题

请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

4.3 思路

用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

4.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

}

4.5 优化

其实这道题目就是用一个队列就够了。

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外）重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

4.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

}

您可能感兴趣的文章 :

原文链接 : https://juejin.cn/post/7164602338752069668

Tag : 队列(4)go语言(31)

Go map发生内存泄漏解决方法

Go 程序运行时，有些场景下会导致进程进入某个高点，然后就再也下不来了。比如，多年前曹大写过的一篇文章讲过，在做活动时线上涌入
Go语言实现栈与队列基本操作学家

go语言中，并没有栈与队列相关的数据结构，但是我们可以借助切片来实现栈与队列的操作；接下来我们一起实现栈与队列基本操作，并且还
Golang内存模型The Go Memory Model

本文翻译了原文并加入了自己的理解。主要介绍多个 Go协程之间对同一个变量并发读写时需要注意的同步措施和执行顺序问题。并列出几个
Golang源码分析之golang/sync之singleflight

1.1. 项目介绍 golang/sync库拓展了官方自带的sync库，提供了errgroup、semaphore、singleflight及syncmap四个包，本次分析singlefliht的源代码。 singleflih
教你如何优雅处理Golang中的异常

我们在使用Golang时，不可避免会遇到异常情况的处理，与Java、Python等语言不同的是，Go中并没有try...catch...这样的语句块，我们知道在Java中
Go语言k8s kubernetes使用leader election实现选举

在kubernetes的世界中，很多组件仅仅需要一个实例在运行，比如controller-manager或第三方的controller，但是为了高可用性，需要组件有多个副本，
golang中的defer函数理解

golang的defer 什么是defer defer的的官方文档:https://golang.org/ref/spec#Defer_statements go语言中defer可以完成延迟功能,当前函数执行完成后再执行defer的
Windows系统中搭建Go语言开发环境图文介绍

本文详细讲述如何在 Windows 系统上搭建 Go语言的开发环境，以供借鉴或参考。文章将介绍Go语言的VSCode、GoLand、Vim三种开发环境，大家可以灵
深入理解Golang channel的应用

channel是用于 goroutine 之间的同步、通信的数据结构 channel 的底层是通过 mutex 来控制并发的，但它为程序员提供了更高一层次的抽象，封装了
基于GORM实现CreateOrUpdate的方法

CreateOrUpdate 是业务开发中很常见的场景，我们支持用户对某个业务实体进行创建/配置。希望实现的 repository 接口要达到以下两个要求：如果

Go语言实现栈与队列基本操作学家

二、实现栈与队列基本操作

2.1 栈基本操作

2.2 队列基本操作

三、用栈实现队列

3.1 理论

3.2 算法题

3.3 思路

3.4 代码部分

四、用队列实现栈

4.1 理论

4.2 算法题

4.3 思路

4.4 使用两个队列实现

4.5 优化

4.6 使用一个队列实现

您可能感兴趣的文章 :

Go map发生内存泄漏解决方法

Go语言实现栈与队列基本操作学家

Golang内存模型The Go Memory Model

Golang源码分析之golang/sync之singleflight

教你如何优雅处理Golang中的异常

Go语言k8s kubernetes使用leader election实现选举

golang中的defer函数理解

Windows系统中搭建Go语言开发环境图文介绍

深入理解Golang channel的应用

基于GORM实现CreateOrUpdate的方法

go语言编程二维码生成及识别的介绍

Go语言之文件操作的方法

go语言代码生成器code generator使用介绍

Go Excelize API源码阅读SetSheetViewOptions实

在Go中使用JSON(附demo)的介绍