栈可以分为
- 顺序栈: 数组实现
- 链式栈: 链表实现
空间复杂度
栈的空间复杂度:
有一个n个元素的栈, 在入栈和出栈过程中, 只需要存储一个临时变量存储空间, 所以空间复杂度是O(1)
并不是说栈有n个元素, 空间复杂度就是O(n), 而是指除了原本的空间外, 算法需要的额外空间
栈要满足后进先出(LIFO)的特性, 栈有以下几种方法
- 判断为空
isEmpty - 入栈
push - 出栈
pop - 返回栈顶元素
peek - 返回栈大小
size - 是否是空
isEmpty
以下是使用列表来模拟栈的操作
# coding:utf-8class Stack(object):"""模拟栈"""def __init__(self):self.items = []def isEmpty(self):return self.items == []def push(self, item):self.items.append(item)def pop(self):if self.isEmpty():raise Exception('the stack is empty')return self.items.pop()def peek(self):if self.isEmpty():raise Exception('the stack is empty')return self.items[-1]def size(self):return len(self.items)if __name__ == '__main__':s = Stack()s.push('t')s.push('e')s.push('s')assert s.pop() == 's'assert s.peek() == 'e'assert s.pop() == 'e'assert s.pop() == 't'应用
1. 符号匹配
实现括号匹配来区分符号是否平衡. 如果是开始符号如(, {, [那么就压入栈, 如果碰到结束符号, 则从栈顶弹出元素
class Stack(object):def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):return self.stack.pop()def isEmpty(self):return self.stack == []basic = {')': '(',']': '[','}': '{',
}def test(string):s = Stack()first = basic.values()last = basic.keys()for i in string:if i in first:s.push(i)elif i in last:if s.pop() == basic[i]:continueelse:return Falseelse:continueif s.isEmpty():return Truereturn Falseif __name__ == '__main__':assert test('[hello ( world { === })]') == Trueassert test('kk(dsfd)ll[') == False
2. 求二进制
如数字6(110), 分别用2除6, 求余数, 最后余数反转就是110
class Stack(object):def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):return self.stack.pop()def isEmpty(self):return self.stack == []def binary(num):s = Stack()while num > 0:n = num % 2s.push(n)num = num // 2res = ""while not s.isEmpty():res += str(s.pop())return resif __name__ == "__main__":assert binary(5) == '101'assert binary(8) == '1000'assert binary(9) == '1001'
