Verfügt die Go-Sprache über Warteschlangen- und Stapelstrukturen?

In der Go-Sprache gibt es keine Datenstrukturen im Zusammenhang mit Warteschlangen und Stapeln. Stapel- und Warteschlangenoperationen können jedoch mithilfe von Slices implementiert werden. Die Go-Sprache implementiert Stapel und Warteschlangen hauptsächlich durch Anhängen und Schneiden (Arbeiten mit integrierten Array-Typen). Die Syntax zum Erstellen von Stapeln und Warteschlangen lautet „make([]int, 0)“ und die Syntax zum Pushen in Stapel und Warteschlangen „append(stack, 10)“, die Syntax zum Öffnen des Stapels lautet „v:=stack[len(stack)-1] stack = stack[:len(stack)-1]“.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, GO Version 1.18, Dell G3-Computer.

In der Go-Sprache gibt es keine Datenstrukturen, die sich auf Stapel und Warteschlangen beziehen, aber wir können Slicing verwenden, um Stapel- und Warteschlangenoperationen zu implementieren. Als Nächstes werden wir grundlegende Operationen von Stapeln und Warteschlangen implementieren und auch implementieren verwenden Der Stapel implementiert die Warteschlange und verwendet die Warteschlange, um die Operationen des Stapels zu implementieren .

Implementieren Sie grundlegende Operationen von Stapeln und Warteschlangen

1. Grundlegende Operationen von Stapeln

Die Go-Sprache verwendet hauptsächlich Anhängen und Slice (Betrieb mit integrierten Array-Typen), um Stapel und Warteschlangen zu implementieren

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

2. Grundlegende Operationen von Warteschlangen

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

Verwenden Sie den Stapel, um die Warteschlange zu implementieren.

1. Verwenden Sie den Stapel, um das Verhalten der Warteschlange zu modellieren. Wenn Sie nur einen Stapel verwenden, funktioniert dies definitiv nicht. Sie benötigen also zwei Stapel, ein Eingabestapel und ein Ausgabestapel. Hier sollten wir auf die Beziehung zwischen dem Eingabestapel und dem Ausgabestapel achten.

Die folgende Animation simuliert den Ausführungsprozess der folgenden Warteschlange wie folgt:

Ausführungsanweisung:

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

Beim Pushen von Daten, solange die Daten in den Eingabestapel gelegt werden, beim Popen ist der Vorgang jedoch komplizierter. Wenn der Ausgabestapel leer ist, importieren Sie alle Push-Daten in den Stapel (beachten Sie, dass alle Daten importiert werden) und entfernen Sie dann die Daten aus dem Pop-Stapel. Wenn der Ausgabestapel nicht leer ist, kopieren Sie einfach die Daten direkt vom Pop-Stapel.

Wie kann man feststellen, ob die Warteschlange am Ende leer ist? Wenn sowohl Push als auch Pop leer sind, bedeutet dies, dass die simulierte Warteschlange leer ist.

2. Algorithmus-Frage

Werfen wir einen Blick auf die ursprüngliche LeetCode-Frage

232. Verwenden Sie Stapel, um Warteschlangen zu implementieren

Bitte verwenden Sie nur zwei Stapel, um First-In-First-Out-Warteschlangen zu implementieren. Die Warteschlange sollte alle von allgemeinen Warteschlangen unterstützten Operationen (Push, Pop, Peek, Empty) unterstützen:

Implementieren Sie die MyQueue-Klasse:

void push(int x) Schieben Sie Element x an das Ende der Warteschlange int pop() entfernt ein Element vom Anfang der Warteschlange und gibt es zurück int peek() gibt das Element am Anfang der Warteschlange zurück boolean empty() gibt „true“ zurück, wenn die Warteschlange leer ist; andernfalls wird „false“ zurückgegeben Hinweis:

Sie können nur Standard-Stack-Operationen verwenden – das heißt, nur Push-to-Top-, Peek/Pop-von-Top-, Size- und Is-Leer-Operationen sind zulässig. Die von Ihnen verwendete Sprache unterstützt möglicherweise keine Stacks. Sie können eine Liste oder eine Deque (doppelte Warteschlange) verwenden, um einen Stapel zu simulieren, sofern es sich um eine Standard-Stack-Operation handelt.

3. Idee

Um dieses Problem zu lösen, benötigen Sie einen Ausgabestapel und einen Eingabestapel. Legen Sie zuerst die Daten in den Eingabestapel und dann die Daten vom Eingabestapel in den Ausgabestapel Die Reihenfolge der Ausgabedaten aus dem Ausgabestapel ist dieselbe wie in der Warteschlange: First in, first out

4 Der Codeteil

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
}

Der Code kann direkt auf Likou ausgeführt werden. Ich habe alle Details in den Kommentaren erklärt. Wenn Sie es nicht verstehen, können Sie dem Blogger eine private Nachricht senden. „Verwenden Sie Warteschlangen, um Stapel zu implementieren.“

Die Warteschlange ist eine First-In-First-Out-Regel. Wenn Daten in einer Warteschlange in eine andere Warteschlange importiert werden, ändert sich die Reihenfolge der Daten nicht und es entsteht keine First-In-Last-Out-Reihenfolge.

Die Idee, einen Stapel zum Implementieren einer Warteschlange zu verwenden, unterscheidet sich also von der Idee, eine Warteschlange zum Implementieren eines Stapels zu verwenden, abhängig von der Art dieser beiden Datenstrukturen.

Aber wir müssen immer noch zwei Warteschlangen verwenden, um den Stapel zu simulieren, aber es gibt keine Beziehung zwischen Eingabe und Ausgabe, sondern eine andere Warteschlange wird vollständig für die Sicherung verwendet!

Wie in der Animation unten gezeigt, werden zwei Warteschlangen que1 und que2 verwendet, um die Warteschlangenfunktion zu implementieren. que2 ist eigentlich eine Sicherungsfunktion. Sie sichert alle Elemente außer dem letzten Element von que1 bis que2 und entfernt dann das letzte Element . Importieren Sie dann andere Elemente von que2 zurück nach que1.

Die simulierte Warteschlangenausführungsanweisung lautet wie folgt:

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

2. Als nächstes werfen wir einen Blick auf die ursprüngliche LeetCode-Frage

225. Verwenden Sie Warteschlangen, um Stapel zu implementieren

请你仅使用两个队列实现一个后入先出（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视频教程、编程教学】

Das obige ist der detaillierte Inhalt vonVerfügt die Go-Sprache über Warteschlangen- und Stapelstrukturen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!