Le langage Go a-t-il des structures de file d'attente et de pile ?

Il n'y a pas de structures de données liées aux files d'attente et aux piles dans le langage Go ; cependant, les opérations de pile et de file d'attente peuvent être implémentées à l'aide de tranches. Le langage Go implémente les piles et les files d'attente principalement en utilisant l'ajout et le découpage (fonctionnant avec des types de tableaux intégrés). La syntaxe de création de piles et de files d'attente est "make([]int, 0)", et la syntaxe de poussée dans les piles et les files d'attente est. "append(stack, 10)", la syntaxe pour ouvrir la pile est "v:=stack[len(stack)-1] stack = stack[:len(stack)-1]".

L'environnement d'exploitation de ce tutoriel : système Windows 7, GO version 1.18, ordinateur Dell G3.

Dans le langage Go, il n'y a pas de structures de données liées aux piles et aux files d'attente, mais nous pouvons utiliser le slicing pour implémenter des opérations sur les piles et les files d'attente. Ensuite, nous implémenterons des opérations de base sur les piles et les files d'attente, et également implémenter. use La pile implémente la file d'attente , et utilise la file d'attente pour implémenter les opérations de la pile .

Implémenter les opérations de base des piles et des files d'attente

1 Opérations de base des piles

Le langage Go utilise principalement l'ajout et le slice (fonctionnant avec des types de tableaux intégrés) pour implémenter les piles et les files d'attente

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

2. Opérations de base des files d'attente

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

Utilisez la pile pour implémenter la file d'attente

1. Théorie

Utilisez la pile pour modéliser le comportement de la file d'attente Si vous n'utilisez qu'une seule pile, cela ne fonctionnera certainement pas, vous en avez donc besoin de deux. piles, une pile d'entrée et une pile de sortie, nous devons ici prêter attention à la relation entre la pile d'entrée et la pile de sortie.

L'animation ci-dessous simule le processus d'exécution de la file d'attente suivante comme suit :

Instruction d'exécution :

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

Lors du transfert de données, tant que les données sont placées dans la pile d'entrée, mais lors du popping, l'opération est plus compliquée. Si la pile de sortie est vide, importez toutes les données push dans la pile (notez que toutes les données sont importées), puis extrayez les données de la pile pop. Si la pile de sortie n'est pas vide, extrayez simplement les données. directement depuis la pile pop.

Comment déterminer si la file d'attente est finalement vide ? Si push et pop sont vides, cela signifie que la file d'attente simulée est vide.

2. Question sur l'algorithme

Jetons un coup d'œil à la question originale de LeetCode

232 Utiliser des piles pour implémenter les files d'attente

Veuillez n'utiliser que deux piles pour implémenter les files d'attente premier entré, premier sorti. La file d'attente doit prendre en charge toutes les opérations (push, pop, peek, vide) prises en charge par les files d'attente générales :

Implémentez la classe MyQueue :

void push(int x) Poussez l'élément x à la fin de la file d'attente int pop() supprime et renvoie un élément du début de la file d'attente int peek() renvoie l'élément au début de la file d'attente boolean empty() renvoie true si la file d'attente est vide, sinon renvoie false ; Remarque :

Vous ne pouvez utiliser que des opérations de pile standard - c'est-à-dire que seules les opérations pousser vers le haut, jeter un coup d'œil/pop depuis le haut, tailler et vider sont légales. Le langage que vous utilisez peut ne pas prendre en charge les piles. Vous pouvez utiliser une liste ou un deque (file d'attente à double extrémité) pour simuler une pile, à condition qu'il s'agisse d'une opération de pile standard.

3. Idée

Pour résoudre ce problème, vous avez besoin d'une pile de sortie et d'une pile d'entrée

Placez d'abord les données dans la pile d'entrée, puis placez les données de la pile d'entrée dans la pile de sortie. le temps, l'ordre des données de sortie de la pile de sortie est C'est le même que la file d'attente, premier entré, premier sorti

4 La partie code

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
}

Le code peut être directement exécuté sur Likou. J'ai expliqué tous les détails dans les commentaires. Si vous ne comprenez pas, vous pouvez envoyer un message privé au blogueur.

Utilisez des files d'attente pour implémenter des piles

1. Théorie

La file d'attente simule des piles. En fait, une file d'attente suffit, parlons donc d'abord de l'idée de deux files d'attente pour implémenter des piles.

La file d'attente est une règle du premier entré, premier sorti. Lorsque les données d'une file d'attente sont importées dans une autre file d'attente, l'ordre des données ne change pas et il ne devient pas un ordre premier entré, dernier sorti.

Donc, l'idée d'utiliser une pile pour implémenter une file d'attente est différente de l'utilisation d'une file d'attente pour implémenter une pile, selon la nature de ces deux structures de données.

Mais nous devons quand même utiliser deux files d'attente pour simuler la pile, mais il n'y a pas de relation entre l'entrée et la sortie, mais une autre file d'attente est entièrement utilisée pour la sauvegarde !

Comme le montre l'animation ci-dessous, deux files d'attente que1 et que2 sont utilisées pour implémenter la fonction de file d'attente. que2 est en fait une fonction de sauvegarde. Elle sauvegarde tous les éléments sauf le dernier élément de que1 dans que2, puis extrait le dernier élément. . Importez ensuite les autres éléments de que2 vers que1.

L'instruction d'exécution de file d'attente simulée est la suivante :

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

2 Question sur l'algorithme

Ensuite, jetons un coup d'œil à la question originale de 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
}

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!