go語言循環(huán)隊列的實現

隊列的概念在 順序隊列 中，而使用循環(huán)隊列的目的主要是規(guī)避假溢出造成的空間浪費，在使用循環(huán)隊列處理假溢出時，主要有三種解決方案

成都創(chuàng)新互聯(lián)自2013年起，先為莊浪等服務建站，莊浪等地企業(yè)，進行企業(yè)商務咨詢服務。為莊浪企業(yè)網站制作PC+手機+微官網三網同步一站式服務解決您的所有建站問題。

本文提供后兩種解決方案。

順序隊和循環(huán)隊列是一種特殊的線性表，與順序棧類似，都是使用一組地址連續(xù)的存儲單元依次存放自隊頭到隊尾的數據元素，同時附設隊頭(front)和隊尾(rear)兩個指針，但我們要明白一點，這個指針并不是指針變量，而是用來表示數組當中元素下標的位置。

本文使用切片來完成的循環(huán)隊列，由于一開始使用三個參數的make關鍵字創(chuàng)建切片，在輸出的結果中不包含nil值(看起來很舒服)，而且在驗證的過程中發(fā)現使用append()函數時切片內置的cap會發(fā)生變化，在消除了種種障礙后得到了一個四不像的循環(huán)隊列，即設置的指針是順序隊列的指針，但實際上進行的操作是順序隊列的操作。最后是對make()函數和append()函數的一些使用體驗和小結，隊列的應用放在鏈隊好了。

官方描述(片段)

即切片是一個抽象層，底層是對數組的引用。

當我們使用

構建出來的切片的每個位置的值都被賦為interface類型的初始值nil，但是nil值也是有大小的。

而使用

來進行初始化時，雖然生成的切片中不包含nil值，但是無法通過設置的指針變量來完成入隊和出隊的操作，只能使用append()函數來進行操作

在go語言中，切片是一片連續(xù)的內存空間加上長度與容量的標識，比數組更為常用。使用 append 關鍵字向切片中追加元素也是常見的切片操作

正是基于此，在使用go語言完成循環(huán)隊列時，首先想到的就是使用make(type, len, cap)關鍵字方式完成切片初始化，然后使用append()函數來操作該切片，但這一方式出現了很多問題。在使用append()函數時，切片的cap可能會發(fā)生變化，用不好就會發(fā)生擴容或收縮。最終造成的結果是一個四不像的結果，入隊和出隊操作變得與指針變量無關，失去了作為循環(huán)隊列的意義，用在順序隊列還算合適。

參考博客：

Go語言中的Nil

Golang之nil

Go 語言設計與實現

Go切片數組深度解析

Go 中的分片數組，實際上有點類似于Java中的ArrayList,是一個可以擴展的數組，但是Go中的切片由比較靈活，它和數組很像，也是基于數組，所以在了解Go切片前我們先了解下數組。

數組簡單描述就由相同類型元素組成的數據結構, 在創(chuàng)建初期就確定了長度，是不可變的。

但是Go的數組類型又和C與Java的數組類型不一樣， NewArray 用于創(chuàng)建一個數組，從源碼中可以看出最后返回的是 Array{}的指針，并不是第一個元素的指針，在Go中數組屬于值類型，在進行傳遞時，采取的是值傳遞，通過拷貝整個數組。Go語言的數組是一種有序的struct。

Go 語言的數組有兩種不同的創(chuàng)建方式，一種是顯示的初始化，一種是隱式的初始化。

注意一定是使用 [...]T 進行創(chuàng)建，使用三個點的隱式創(chuàng)建，編譯器會對數組的大小進行推導，只是Go提供的一種語法糖。

其次，Go中數組的類型，是由數值類型和長度兩個一起確定的。[2]int 和 [3]int 不是同一個類型，不能進行傳參和比較，把數組理解為類型和長度兩個屬性的結構體，其實就一目了然了。

Go中的數組屬于值類型，通常應該存儲于棧中，局部變量依然會根據逃逸分析確定存儲棧還是堆中。

編譯器對數組函數中做兩種不同的優(yōu)化：

在靜態(tài)區(qū)完成賦值后復制到棧中。

總結起來，在不考慮逃逸分析的情況下，如果數組中元素的個數小于或者等于 4 個，那么所有的變量會直接在棧上初始化，如果數組元素大于 4 個，變量就會在靜態(tài)存儲區(qū)初始化然后拷貝到棧上。

由于數組是值類型，那么賦值和函數傳參操作都會復制整個數組數據。

不管是賦值或函數傳參，地址都不一致，發(fā)生了拷貝。如果數組的數據較大，則會消耗掉大量內存。那么為了減少拷貝我們可以主動的傳遞指針呀。

地址是一樣的，不過傳指針會有一個弊端，從打印結果可以看到，指針地址都是同一個，萬一原數組的指針指向更改了，那么函數里面的指針指向都會跟著更改。

同樣的我們將數組轉換為切片，通過傳遞切片，地址是不一樣的，數組值相同。

切片是引用傳遞，所以它們不需要使用額外的內存并且比使用數組更有效率。

所以，切片屬于引用類型。

通過這種方式可以將數組轉換為切片。

中間不加三個點就是切片,使用這種方式創(chuàng)建切片，實際上是先創(chuàng)建數組，然后再通過第一種方式創(chuàng)建。

使用make創(chuàng)建切片，就不光編譯期了，make創(chuàng)建切片會涉及到運行期。1. 切片的大小和容量是否足夠小；

切片是否發(fā)生了逃逸，最終在堆上初始化。如果切片小的話會先在棧或靜態(tài)區(qū)進行創(chuàng)建。

切片有一個數組的指針，len是指切片的長度, cap指的是切片的容量。

cap是在初始化切片是生成的容量。

發(fā)現切片的結構體是數組的地址指針array unsafe.Pointer，而Go中數組的地址代表數組結構體的地址。

slice 中得到一塊內存地址，array[0]或者unsafe.Pointer(array[0])。

也可以通過地址構造切片

nil切片：指的unsafe.Pointer 為nil

空切片：

創(chuàng)建的指針不為空，len和cap為空

當一個切片的容量滿了，就需要擴容了。怎么擴，策略是什么？

如果原來數組切片的容量已經達到了最大值，再想擴容， Go 默認會先開一片內存區(qū)域，把原來的值拷貝過來，然后再執(zhí)行 append() 操作。這種情況對現數組的地址和原數組地址不相同。

從上面結果我們可以看到，如果用 range 的方式去遍歷一個切片，拿到的 Value 其實是切片里面的值拷貝,即淺拷貝。所以每次打印 Value 的地址都不變。

由于 Value 是值拷貝的，并非引用傳遞，所以直接改 Value 是達不到更改原切片值的目的的，需要通過 slice[index] 獲取真實的地址。

如何看待go語言泛型的最新設計？

Go 由于不支持泛型而臭名昭著，但最近，泛型已接近成為現實。Go 團隊實施了一個看起來比較穩(wěn)定的設計草案，并且正以源到源翻譯器原型的形式獲得關注。本文講述的是泛型的最新設計，以及如何自己嘗試泛型。

例子

FIFO Stack

假設你要創(chuàng)建一個先進先出堆棧。沒有泛型，你可能會這樣實現：

type?Stack?[]interface{}func?(s?Stack)?Peek()?interface{}?{

return?s[len(s)-1]

}

func?(s?*Stack)?Pop()?{

*s?=?(*s)[:

len(*s)-1]

}

func?(s?*Stack)?Push(value?interface{})?{

*s?=?

append(*s,?value)

}

但是，這里存在一個問題：每當你 Peek 項時，都必須使用類型斷言將其從 interface{} 轉換為你需要的類型。如果你的堆棧是 *MyObject 的堆棧，則意味著很多 s.Peek().(*MyObject)這樣的代碼。這不僅讓人眼花繚亂，而且還可能引發(fā)錯誤。比如忘記 * 怎么辦？或者如果您輸入錯誤的類型怎么辦？s.Push(MyObject{})` 可以順利編譯，而且你可能不會發(fā)現到自己的錯誤，直到它影響到你的整個服務為止。

通常，使用 interface{} 是相對危險的。使用更多受限制的類型總是更安全，因為可以在編譯時而不是運行時發(fā)現問題。

泛型通過允許類型具有類型參數來解決此問題：

type?Stack(type?T)?[]Tfunc?(s?Stack(T))?Peek()?T?{

return?s[len(s)-1]

}

func?(s?*Stack(T))?Pop()?{

*s?=?(*s)[:

len(*s)-1]

}

func?(s?*Stack(T))?Push(value?T)?{

*s?=?

append(*s,?value)

}

這會向 Stack 添加一個類型參數，從而完全不需要 interface{}。現在，當你使用 Peek() 時，返回的值已經是原始類型，并且沒有機會返回錯誤的值類型。這種方式更安全，更容易使用。（譯注：就是看起來更丑陋，^-^）

此外，泛型代碼通常更易于編譯器優(yōu)化，從而獲得更好的性能（以二進制大小為代價）。如果我們對上面的非泛型代碼和泛型代碼進行基準測試，我們可以看到區(qū)別：

type?MyObject?struct?{

X?

int

}

var?sink?MyObjectfunc?BenchmarkGo1(b?*testing.B)?{

for?i?:=?0;?i??b.N;?i++?{

var?s?Stack

s.Push(MyObject{})

s.Push(MyObject{})

s.Pop()

sink?=?s.Peek().(MyObject)

}

}

func?BenchmarkGo2(b?*testing.B)?{

for?i?:=?0;?i??b.N;?i++?{

var?s?Stack(MyObject)

s.Push(MyObject{})

s.Push(MyObject{})

s.Pop()

sink?=?s.Peek()

}

}

結果：

BenchmarkGo1BenchmarkGo1-16?????12837528?????????87.0?ns/op???????48?B/op????????2?allocs/opBenchmarkGo2BenchmarkGo2-16?????28406479?????????41.9?ns/op???????24?B/op????????2?allocs/op

在這種情況下，我們分配更少的內存，同時泛型的速度是非泛型的兩倍。

合約（Contracts）

上面的堆棧示例適用于任何類型。但是，在許多情況下，你需要編寫僅適用于具有某些特征的類型的代碼。例如，你可能希望堆棧要求類型實現 String() 函數

網站欄目：go語言append go語言append函數追加元素允許重復
標題來源：http://www.chinadenli.net/article16/doddedg.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供網站建設、軟件開發(fā)、品牌網站設計、外貿建站、網站收錄、全網營銷推廣

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)