Does Go language have queue and stack structures?

There are no data structures related to queues and stacks in the Go language; however, stack and queue operations can be implemented with the help of slices. Go language implements stacks and queues mainly using append and slicing (operating with built-in array types). The syntax for creating stacks and queues is "make([]int, 0)", and the syntax for pushing into stacks and queues is "append(stack, 10)", the syntax of popping the stack is "v:=stack[len(stack)-1] stack = stack[:len(stack)-1]".

The operating environment of this tutorial: Windows 7 system, GO version 1.18, Dell G3 computer.

In the go language, there are no data structures related to stacks and queues, but we can use slices to implement stack and queue operations; next we will implement stacks and queues together Basic operations , and will also implement using stacks to implement queues , using queues to implement stack operations.

Implementing basic operations of stacks and queues

1. Basic operations of stacks

Go language is mainly used to implement stacks and queues append and slicing (operating with built-in array types)

//创建栈
stack := make([]int, 0)
//push压入栈
stack = append(stack, 10)
//pop弹出
v := stack[len(stack)-1]
stack = stack[:len(stack)-1]
//检查栈空
len(stack) == 0

2. Basic queue operations

//创建队列
queue := make([]int, 0)
//enqueue入队
queue = append(queue, 10)
//dequeue出队
v := queue[0]
queue = queue[1:]
//检查队列为空
len(queue) == 0

Use stack to implement queue

1. Theory

Use a stack to model the behavior of a queue. If you only use one stack, it will definitely not work, so you need two stacks, one input stack and one output stack. Here Pay attention to the relationship between the input stack and the output stack.

The animation below simulates the execution process of the following queue as follows:

Execution statement:

queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();

When pushing data, as long as the data is put into the input stack, but when pop When the output stack is empty, import all the push data in (note that all data is imported), and then pop the data from the pop stack. If the output stack is not empty, pop the data directly from the pop stack. That's it.

How to determine if the queue is empty in the end? If both push and pop are empty, it means that the simulated queue is empty.

2. Algorithm question

Let’s take a look at the original LeetCode question

232. Implementing queues using stack

Please use only two stacks to implement the first-in-first-out queue. The queue should support all operations (push, pop, peek, empty) supported by general queues:

Implement the MyQueue class:

void push(int x) Push element x to the end of the queue int pop() removes and returns an element from the beginning of the queue int peek() returns the element at the beginning of the queue boolean empty() returns true if the queue is empty; otherwise, returns false Note:

You can only use standard stack operations - that is, only push to top, peek/pop from top, size, and is empty operations are legal. The language you are using may not support stacks. You can use a list or deque (double-ended queue) to simulate a stack, as long as it is a standard stack operation.

3. Idea

To solve this problem, you need an output stack and an input stack

First put the data into the input stack, and then put the data from The input stack is placed on the output stack. At this time, the order of output data from the output stack is the same as that of the queue. First in, first out

4. Code part

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
}

The code can be directly Get it on the buckle and run it. I have explained all the details in comments. If you don’t understand, you can send a private message to the blogger.

Use queue to implement stack

1. Theory

Queue simulates stack. In fact, one queue is enough, then we Let’s first talk about the idea of ​​using two queues to implement a stack.

The queue is a first-in, first-out rule. When data in one queue is imported into another queue, the order of the data does not change, and it does not become a first-in, last-out order.

So the idea of ​​using a stack to implement a queue is different from using a queue to implement a stack, depending on the nature of the two data structures.

But we still need to use two queues to simulate the stack, but there is no relationship between input and output, but another queue is used completely for backup!

As shown in the animation below, two queues que1 and que2 are used to implement the queue function. que2 is actually a backup function. It backs up all elements except the last element of que1 to que2, and then pops up the last element. elements of the surface, and then guide other elements from que2 back to que1.

The simulated queue execution statement is as follows:

queue.push(1);        
queue.push(2);        
queue.pop();   // 注意弹出的操作       
queue.push(3);        
queue.push(4);       
queue.pop();  // 注意弹出的操作    
queue.pop();    
queue.pop();    
queue.empty();

2. Algorithm question

Let’s take a look at LeetCode Original question225. Implement stack using queue

请你仅使用两个队列实现一个后入先出（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
}

【相关推荐：Go视频教程、编程教学】

The above is the detailed content of Does Go language have queue and stack structures?. For more information, please follow other related articles on the PHP Chinese website!