1 雙棧共享空間 思路
如果有兩個類型相同的棧摘符，我們?yōu)樗鼈兎謩e開辟了數(shù)組空間贤斜。極有可能是一個棧已經(jīng)滿了，再入棧就溢出了逛裤，而另一個棧卻還有很多存儲空間瘩绒。這又何必呢？我們完全可以用一個數(shù)組來存儲兩個棧带族，只不過需要一些小的技巧锁荔。
我們的做法如下，數(shù)組有兩個端點蝙砌，兩個棧有兩個棧底阳堕。讓一個棧的棧底為數(shù)組的始端，即數(shù)組下標為0的位置择克。讓另一個棧的棧底為數(shù)組的末端恬总，即數(shù)組下標為n-1的位置。這樣如果兩個棧增加元素肚邢，就是兩端點向中間延伸壹堰。
關(guān)鍵思路:
它們是在數(shù)組的兩端，向中間靠攏。top1和top2是兩個棧的棧頂指針缀旁。只要它們兩個不見面记劈，兩個棧就可以一直使用。
適用情況：
當兩個棧的空間需求有相反關(guān)系時, 也就是說一個棧增長另一個棽⑽。縮短的情況下, 就像買股票一樣有人買必有人賣目木。
2 代碼
代碼倉庫
https://gitee.com/babyb/data_srtuct/tree/master/005doublestack
代碼倉庫中有測試代碼
2.1 數(shù)據(jù)結(jié)構(gòu)
type DoubleStack struct {
top1 int64
top2 int64
size int64
data []interface{}
}
2.2 棧初始化代碼
數(shù)據(jù) data的下標為從 0 到 size -1;
所以初始化的時候, top1 = -1 top2 = size
添加元素的時候, 如果是往棧1 中添加, 則先讓 top1 ++ , 然后賦值, 棧1 中元素就從 數(shù)組的 底部下標 0開始, 向數(shù)組的頂部走
如果是往棧2中添加, 先 top2--, 然后再賦值, 棧2中的元素, 從數(shù)組的 頂部下標(size -1)處, 從上往下走
當棧1 中的元素與 棧2中的元素 見面 的時候, 也就是 top1 + 1 = top2, 說明數(shù)組中的所有空間被占滿, 棧滿了。
func InitStack(size int64) DoubleStack {
d := DoubleStack{}
d.top1 = -1
d.top2 = size
d.size = size
d.data = make([]interface{}, size)
return d
}
2.3 向指定 棧中插入元素
func (d *DoubleStack) Push(data interface{}, stackNum int64) {
if d.IsFull() {
fmt.Println("棸枚桑空間已滿, 無法繼續(xù)插入")
return
}
if stackNum == 1 {
// 向棧1 中插入元素
d.top1++
d.data[d.top1] = data
} else {
d.top2--
d.data[d.top2] = data
}
}
//IsFull 判斷棧是否已滿
func (d *DoubleStack) IsFull() bool {
return d.top1+1 == d.top2
}
2.4 從指定棧中彈出元素
func (d *DoubleStack) Pop(stackNum int64) (data interface{}) {
if stackNum == 1 {
if d.top1 == -1 {
fmt.Printf("棧%d 已空, 無法繼續(xù)彈出", stackNum)
return
}
data = d.data[d.top1]
d.top1--
} else {
if d.top2 >= d.size {
fmt.Printf("棧%d已空,無法繼續(xù)彈出", stackNum)
}
data = d.data[d.top2]
d.top2++
}
return data
}
2.5 展示和清空棧
func (d *DoubleStack) Show(stackNum int64) {
var i int64
if stackNum == 1 {
for i = 0; i <= d.top1; i++ {
fmt.Println(d.data[i])
}
} else {
for i = d.size - 1; i >= d.top2; i-- {
fmt.Println(d.data[i])
}
}
}
/*
Clear 清空棧
*/
func (d *DoubleStack) Clear() {
d.top1 = -1
d.top2 = d.size
}
