Adakah bahasa Go mempunyai struktur baris gilir dan tindanan?

Tiada struktur data yang berkaitan dengan baris gilir dan tindanan dalam bahasa Go walau bagaimanapun, operasi tindanan dan baris gilir boleh dilaksanakan dengan bantuan kepingan. Bahasa Go melaksanakan tindanan dan baris gilir terutamanya menggunakan penambahan dan penghirisan (beroperasi dengan jenis tatasusunan terbina dalam Sintaks untuk mencipta tindanan dan baris gilir ialah "make([]int, 0)", dan sintaks untuk menolak ke dalam tindanan dan baris gilir ialah "append(tindanan, 10)", sintaks untuk memunculkan tindanan ialah "v:=tindanan[len(tindanan)-1] tindanan = tindanan[:len(tindanan)-1]".

Persekitaran pengendalian tutorial ini: sistem Windows 7, GO versi 1.18, komputer Dell G3.

Dalam bahasa Go, tiada struktur data yang berkaitan dengan tindanan dan baris gilir, tetapi kami boleh menggunakan slices untuk melaksanakan operasi tindanan dan baris gilir; seterusnya kami akan melaksanakan tindanan dan baris gilir bersama-sama operasi asas , dan juga melaksanakan operasi menggunakan tindanan untuk melaksanakan baris gilir dan menggunakan baris gilir untuk melaksanakan tindanan .

Melaksanakan operasi asas tindanan dan baris gilir

1. tindanan dan baris gilir menambah dan menghiris (beroperasi dengan jenis tatasusunan terbina dalam)

2. laksanakan baris gilir

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

1. Teori

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

Gunakan tindanan untuk memodelkan tingkah laku baris gilir Jika anda hanya menggunakan satu tindanan, ia pasti tidak akan berfungsi jadi anda memerlukan dua tindanan, satu tindanan input dan satu tindanan Output, di sini kita harus memberi perhatian kepada hubungan antara tindanan input dan tindanan output. Animasi di bawah mensimulasikan proses pelaksanaan baris gilir berikut:

Pernyataan pelaksanaan:

Apabila menolak data, selagi data dimasukkan ke dalam input tindanan, tetapi Apabila muncul, operasi lebih rumit Jika tindanan output kosong, import semua data pada tindanan (perhatikan bahawa semua data diimport), dan kemudian pop data daripada tindanan tidak kosong, terus pop data dari timbunan Hanya pop data.

Bagaimana untuk menentukan sama ada baris gilir kosong pada akhirnya? Jika kedua-dua push dan pop kosong, ini bermakna baris gilir simulasi kosong.

2. Soalan Algoritma

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

Mari kita lihat soalan LeetCode yang asal

232 🎜>

Sila gunakan hanya dua tindanan untuk melaksanakan baris gilir pertama masuk dahulu. Barisan gilir harus menyokong semua operasi (tolak, pop, intip, kosong) disokong oleh baris gilir umum: Laksanakan kelas MyQueue:

void push(int x) Tolak elemen x ke penghujung barisan int pop() mengalih keluar dan mengembalikan elemen dari permulaan baris gilir int peek() mengembalikan elemen pada permulaan baris gilir boolean empty() mengembalikan benar jika baris gilir kosong, sebaliknya, mengembalikan palsu Nota:

Anda hanya boleh menggunakan operasi tindanan standard - iaitu, hanya tolak ke atas, intip/pop dari atas, saiz dan operasi kosong adalah sah. Bahasa yang anda gunakan mungkin tidak menyokong tindanan. Anda boleh menggunakan senarai atau deque (baris bersambung dua) untuk mensimulasikan tindanan, asalkan ia adalah operasi tindanan standard.

3. Idea

Untuk menyelesaikan masalah ini, anda memerlukan tindanan output dan tindanan input

Mula-mula masukkan data ke dalam tindanan input, dan kemudian letakkan data daripada Timbunan input diletakkan pada timbunan keluaran Pada masa ini, susunan data keluaran daripada timbunan keluaran adalah sama seperti baris gilir, masuk dahulu, keluar dahulu

<.> 4. Bahagian kod

kod Anda boleh terus membawanya ke Libuckle dan menjalankannya. Saya telah menerangkan semua butiran dalam komen Jika anda tidak faham, anda boleh menghantar mesej peribadi kepada blogger.

Gunakan baris gilir untuk melaksanakan tindanan

Teori

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
}

Baris gilir mensimulasikan tindanan. maka kita Mari kita bercakap tentang idea menggunakan dua baris gilir untuk melaksanakan timbunan.

Baris gilir ialah peraturan masuk dahulu, keluar dahulu Apabila data dalam satu baris gilir diimport ke baris gilir lain, susunan data tidak berubah dan ia tidak menjadi masuk pertama, terakhir. -perintah keluar.

Jadi idea menggunakan tindanan untuk melaksanakan baris gilir adalah berbeza daripada menggunakan baris gilir untuk melaksanakan tindanan, bergantung pada sifat kedua-dua struktur data ini.

Tetapi anda masih perlu menggunakan dua baris gilir untuk mensimulasikan tindanan, tetapi tiada hubungan antara input dan output, tetapi baris gilir lain digunakan sepenuhnya untuk sandaran!

Seperti yang ditunjukkan dalam animasi di bawah, dua baris gilir que1 dan que2 digunakan untuk melaksanakan fungsi que2 sebenarnya adalah fungsi sandaran kecuali elemen terakhir que1 kepada que2, dan kemudian muncul ke atas elemen terakhir permukaan, dan kemudian membimbing elemen lain dari que2 kembali ke que1.

Pernyataan pelaksanaan baris gilir simulasi adalah seperti berikut:

Soalan algoritma

Lihat seterusnya Mari kita lihat soalan asal LeetCode

225 Menggunakan baris gilir untuk melaksanakan tindanan

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

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

Atas ialah kandungan terperinci Adakah bahasa Go mempunyai struktur baris gilir dan tindanan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!