資料結構-棧

語言: CN / TW / HK

棧(stack)又名堆疊,它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂,相對地,把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧,它是把新元素放到棧頂元素的上面,使之成為新的棧頂元素;從一個棧刪除元素又稱作出棧或退棧,它是把棧頂元素刪除掉,使其相鄰的元素成為新的棧頂元素。

棧作為一種資料結構,是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進後出的原則儲存資料,先進入的資料被壓入棧底,最後的資料在棧頂,需要讀資料的時候從棧頂開始彈出資料(最後一個數據被第一個讀出來)。棧具有記憶作用,對棧的插入與刪除操作中,不需要改變棧底指標。

棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top),另一端為棧底(bottom);棧底固定,而棧頂浮動;棧中元素個數為零時稱為空棧。插入一般稱為進棧(PUSH),刪除則稱為退棧(POP)。棧也稱為先進後出表。

棧可以用來在函式呼叫的時候儲存斷點,做遞迴時要用到棧!

在演算法中,要記錄歷史狀態,並使用 最後一次 狀態的情況,就可以用棧。

棧的常用操作

定義一個簡單的stack程式碼:

type Stack Interface {
	Push(x interface{})
	Pop() interface{}
	Size() int
	Empty() bool
}

func StackDemo(sta Stack) {
	sta.size()//判斷棧的大小   0
	sta.empty()//判斷棧是否為空 true
	sta.push(1) //入棧
	sta.size()//判斷棧的大小  1
	sta.empty()//判斷棧是否為空 false
	sta.pop() //出棧
	sta.size()//判斷棧的大小  0
	sta.empty()//判斷棧是否為空  true
}

常見應用

進位制轉換

利用棧將轉化數字的進位制,假設將數字n轉換為以b為基數的數字,方法如下:

最高位為n % b,將此位壓入棧 使用Math.floor(n/b)代替n 重複步驟1和2,直到n等於0,且沒有餘數 持續將棧內元素彈出,直到棧為空

func MulBase(num int, base int) string {
	//go裡面用切片模擬棧即可(操作最後一個元素)
	var stack []uint8
	for {
		if num <= 0 {
			break
		}
		v := uint8(num % base)
		if v > 9 {
			v = v + 55
		}else{
			v = v + 48
		}
		//講結果入棧
		stack = append(stack, v)
		num = int(math.Floor(float64(num/base)))
	}
	l := len(stack)
	var sb []uint8
	for i:=l-1;i>-1;i-- {
		//從棧頂出棧(這裡用陣列模擬)
		sb = append(sb, stack[i])
	}
	return string(sb[:])
}

迴文判斷

利用棧,可以輕鬆判斷一個字串是否是迴文(迴文指一個字串從前往後寫和從後往前寫都一樣)

function IsPalindrome(word string) bool{
	var stack []byte
	for i:=0;i<len(word);i++{
		stack = apped(stack, word[i])
	}

	return string(stack[:]) == word
}

leetcode 20

leetCode 20:給定一個只包括 '(',')','{','}','[',']' 的字串,判斷字串是否有效。

有效字串需滿足:左括號必須用相同型別的右括號閉合。左括號必須以正確的順序閉合。

func isValid(s string) bool {
	var bt []byte
	for i := 0; i < len(s); i++ {
		if s[i] == '(' || s[i] == '{' || s[i] == '[' {
			bt = append(bt, s[i])
		} else {
			l := len(bt)
			if l < 1 {
				return false
			}
			check := false
			if s[i] == ')' {
				if bt[l-1] == '(' {
					bt = bt[:l-1]
					check = true
				}
			} else {
				if bt[l-1]+2 == s[i] {
					bt = bt[:l-1]
					check = true

				}
			}
			if !check {
				return false
			}
		}

	}
    if len(bt) > 0 {
        return false
    }
	return true
}

優化下

func isValid(s string) bool {
    n := len(s)
    if n % 2 == 1 {
        return false
    }
    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []byte{}
    for i := 0; i < n; i++ {
        if pairs[s[i]] > 0 {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}

基本計算器,leetcode 224

給你一個字串表示式 s ,請你實現一個基本計算器來計算並返回它的值。

示例 1:

輸入:s = "1 + 1"
輸出:2

示例 2:

輸入:s = " 2-1 + 2 "
輸出:3

示例 3:

輸入:s = "(1+(4+5+2)-3)+(6+8)"
輸出:23
func calculate(s string) int {
    var ans int
    ops := []int{1}  
    sign := 1     // +,-     1 => + -1 => -
    n := len(s)
    for i := 0; i < n; {
        switch s[i] {
        case ' ':  //空格跳過
            i++
        case '+': 
            sign = ops[len(ops)-1]  //操作符為最後一個數字的符號
            i++
        case '-':
            sign = -ops[len(ops)-1] //操作符為最後一個數字的符號取反
            i++
        case '(':
            ops = append(ops, sign) //遇到括號,將最後一個符號入棧   LIFO
            i++
        case ')':
            ops = ops[:len(ops)-1]  //遇到括號結束, 移除最後一個標誌符號
            i++
        default:
            num := 0
            // int(s[i]-'0')  ascii 計算 -0 就為數字本身的值 技巧 get
            // 和 int(s[i] -  48) 一樣
             //如果當前迭代器是0~9範圍內的數字 則進行計算
            //為什麼再寫一次迴圈在switch內呢? 
            //因為自增的i是不變的,所以時間複雜度還是o(n)
            //但是 如果i++寫在外部, 會增加多次的switch操作
            for ; i < n && '0' <= s[i] && s[i] <= '9'; i++ { 
                // num = num*10 是最進位用 從示例來說, 是不需要的,但是題目並沒有說數字僅僅是個位數,因此需要用到
                num = num*10 + int(s[i]-'0')
            }
            ans += sign * num
        }
    }
    return ans
}

計算器||, leetcode227

你一個字串表示式 s ,請你實現一個基本計算器來計算並返回它的值。

整數除法僅保留整數部分。

示例 1:

輸入:s = "3+2*2"
輸出:7

示例 2:

輸入:s = " 3/2 "
輸出:1

示例 3:

輸入:s = " 3+5 / 2 "
輸出:5
func calculate(s string) int {
	var stack []int
	var res int
	var preOp = '+' //第一個操作符肯定是作為+  比如 "3" => 3
	num := 0        //上一次的數字,也就是符號之前的
	for i, ch := range s {
		isNum := ch > 47 && ch < 58
		if isNum { //如果是數字則計算出當前數額
			num = num*10 + int(ch-'0')
		}

		if i != len(s)-1 { //如果不是最後一個字元
			if isNum || ch == ' ' { //如果是數字 或者是空格  不處理
				continue
			}
		}
		//根據上一個操作符計算資料,可以把整個計算器看成  (表示式) + (表示式) + (表示式)
		// 將表示式結果入棧  最後將棧元素相加就行
		switch preOp {
		case '+':
			stack = append(stack, num) // +n
		case '-':
			stack = append(stack, -num) //計算當前表示式 -n
		case '*':
			stack[len(stack)-1] *= num //計算當前表示式  m*n
		case '/':
			stack[len(stack)-1] /= num //計算當前表示式  m/n
		}
		preOp = ch // 上一次的符號決定當前數字的計算邏輯
		num = 0

	}
	for _, v := range stack {
		res += v
	}

	return res
}
分享到: