一前言

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原题

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

queue.empty();

4.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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

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

}

巴特西

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实现栈与队列基本操作

一 前言

二 实现栈与队列基本操作

2.1 栈基本操作

2.2 队列基本操作

三 用栈实现队列

3.1 理论

3.2 算法题

3.3 思路

3.4 代码部分

四 用队列实现栈

4.1 理论

4.2 算法题

4.3 思路

4.4 使用两个队列实现

4.5 优化

4.6 使用一个队列实现

最新文章

热门文章

一前言

二实现栈与队列基本操作

三用栈实现队列

四用队列实现栈