数据结构-栈

原创
03/11 18:37
阅读数 58

栈(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
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部