线性结构－堆栈
<big>编译环境：python v3.5.0, mac osx 10.11.4</big>
什么是堆栈
- 具有一定约束的线性表，只在一段（栈顶）进行操作
-
后入先出（LIFO），如同叠碗：先叠上的，最后才会被取出来
- 插入数据（Push，入栈），删除数据（Pop，出栈）
堆栈的抽象数据类型描述
-
图解堆栈
堆栈的顺序存储（数组）实现
-
基本结构实现(下载地址：stack.py）
# -- coding: utf-8 --
class Stack():
def init(self, maxSize): # 初始化堆栈,设定最大值
self._stack = []
self._maxSize = maxSize
self._p = -1 # 指针指向栈顶
def push(self, value): # 插入数据
if self._p >= self._maxSize-1: # 通过判断指针位置是否超过初始容量,确定堆栈是否满了
print('stack is full')
else:
self._stack.append(value)
self._p += 1 # 指针向栈顶移动
print('push %d in stack ' % value)
def pop(self): # 删除数据
if self._p == -1: # 通过判断指针位置来确定堆栈是否为空
print("it's an empty stack")
else:
iterms = self._stack[self._p] # 将最后一位元素的值取出
del self._stack[self._p] # s删除元素
self._p -= 1 # 指针指向栈顶
print('pop %d out' % items)
return iterms # 返回最后一位元素的值 -
堆栈的改良应用（下载地址：stack_apply.py）
怎样利用数组存储两个堆栈，要求最大化的利用数组空间，即只要任何一个堆栈不空，就能储存元素
解决方案：<big>两个堆栈从数组两端往中间生长</big>，即一个初始指针指向-1，另一个堆栈初始指针指向maxSize,当两指针相邻时，则两堆栈都满了。
# -- coding: utf-8 --class newStack(): def __init__(self, maxSize): self._maxSize = maxSize self._p1 = -1 # 堆栈1 的指针 self._p2 = maxSize # 堆栈2 的指针 self._stack = [None] * maxSize # 储存元素的数组 def push(self, value, tag): # 插入数据, tag表示插入哪一个堆栈堆栈 if self._p2 - self._p1 == 1: # 通过判断两个指针位置是否相邻,确定堆栈是否满了 print('all stack are full') else: if tag == 1: self._p1 += 1 # 指针向中间移动 self._stack[self._p1] = value print('push %d in stack1 ' % value) elif tag == 2: self._p2 -= 1 # 指针向中间移动 self._stack[self._p2] = value print('push %d in stack2 ' % value) else: print("stack %d doesn't exist" % tag) def pop(self, tag): # 删除数据 if tag == 1: if self._p1 == -1: # 通过判断指针位置来确定堆栈是否为空 print("it's an empty stack1") else: iterm1 = self._stack[self._p1] # 将最后一位元素的值取出 self._stack[self._p1] = None # 删除元素 self._p1 -= 1 # 指针指向栈顶 print('pop %d out from stack 1' % iterm1) return iterm1 # 返回最后一位元素的值 elif tag == 2: if self._p2 == self._maxSize: # 通过判断指针位置来确定堆栈是否为空 print("it's an empty stack2") else: iterm2 = self._stack[self._p2] # 将最后一位元素的值取出 self._stack[self._p2] = None # 删除元素 self._p2 += 1 # 指针指向栈顶 print('pop %d out from stack 2' % iterm2) return iterm2 # 返回最后一位元素的值 else: print("stack %d doesn't exist" % tag)
堆栈的链式存储（链表）实现
由于堆栈的链式存储结构实际上是一个单向链表，所以栈顶指针应该指向链表的表头，若是指向表尾的话，当pop出一个元素后，我们无法得知这个元素的前一个元素是什么。
-
基本结构实现(下载地址：stack_chain.py）
class stackChain():
def init(self, value=None, next=None): # 创建一个空链表
self.value = value
self.next = nextdef isEmpty(stack_chain): # 判断堆栈是否为空 return stack_chain.next is None def push(stack_chain, element): # 向堆栈stack_chain中插入元素element,并返回头指针 newChain = stackChain(element) # 生成新的链表元素 newChain.next = stack_chain.next # 将原表头栈顶元素接到新元素的下面 stack_chain.next = newChain # 将头指针指向新元素 print('push '+str(element)+' in stack') return stack_chain def pop(stack_chain): # 堆栈stack_chain的头元素,并返回头指针 if isEmpty(stack_chain): print('it is an empty stack') else: p = stack_chain.next # 指针指向头一个元素 print('pop '+str(p.value)+' out from stack') stack_chain.next = p.next # 将指针指向栈顶元素 element = p.value del p # 释放空间 return element -
链式堆栈的应用（下载地址：stack_expression.py）
表达式求值，应用堆栈实现后缀表达式的求值过程，即将中缀表达式转化为后缀表达式
解决方案：用列表存储输出状态，用堆栈储存表达符号。
# -- coding: utf-8 --import stack_chain def expression(expressionStrings): # 输入表达式字符串,如:'1 + 1 * 2'以空格空开 allexpress = ['+', '-', '*', '/', '(', ')'] orderEX = { # 构建运算符优先级 '(': [1,0], # 第一位为优先级,第二位为标签 ')': [1], '+': [3], '-': [3], '*': [2], '/': [2], } output = [] # 建立存放输出的列表 p_expression = stack_chain.stackChain() # 建立存放表达式的堆栈 normalExpression = expressionStrings.split() for element in normalExpression if not(element in allexpress): output.append(element) else: while not stack_chain.isEmpty(p_expression): # 如果堆栈不为空,则开始判断 topElement = stack_chain.pop(p_expression) # 弹出栈顶元素并赋值给topElement if orderEX[topElement][0] <= orderEX[element][0]: # 栈顶优先级低,则输出栈顶元素 if topElement == '(' and orderEX['('][1] == 0: # 未弹出'(',将'('不断输入 stack_chain.push(p_expression, topElement) stack_chain.push(p_expression, element) break elif topElement == ')': # 遇到 ')'则改变'('的标签 orderEX['('][1] = 1 elif topElement == '(': orderEX['('][1] = 0 # 当'('被pop出来后,初始化'('的标签 else: output.append(topElement) else: # 如果新扫到的运算符优先级低,则插入堆栈,并跳出循环 stack_chain.push(p_expression, topElement) # 将栈顶元素重新插入 stack_chain.push(p_expression, element) # 将新运算符也插入 break if stack_chain.isEmpty(p_expression): # 如果堆栈为空,则说明元素没有push进去 stack_chain.push(p_expression, element) while not(stack_chain.isEmpty(p_expression)): topElement = stack_chain.pop(p_expression) if not topElement in ['(', ')']: output.append(topElement) return output
堆栈的其他应用：
- 函数的调用及递归实现
- 深度优先搜索
- 回溯算法
