一、概述
堆栈（Stack）是一种后进先出（LIFO）的线性数据结构，对堆栈的插入和删除操作都只能在栈顶（top）进行。
二、ADT
堆栈ADT（抽象数据类型）一般提供以下接口：
Stack()创建堆栈push(item)向栈顶插入项pop()返回栈顶的项，并从堆栈中删除该项clear()清空堆栈empty()判断堆栈是否为空size()返回堆栈中项的个数top()返回栈顶的项
堆栈操作的示意图如下：
三、Python实现
使用Python的内建类型list列表，可以很方便地实现堆栈ADT：
#!/usr/bin/env python
# -*- coding: utf-8 -*-class Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def clear(self):del self.items[:]def empty(self):return self.size() == 0def size(self):return len(self.items)def top(self):return self.items[self.size()-1]
四、应用
十进制转二进制 是一个应用堆栈的典型案例。十进制转二进制 采用“除2取余，逆序排列”的方法，如图所示：
借助Stack类，可以很方便地实现上述转换算法：
#!/usr/bin/env python
# -*- coding: utf-8 -*-def divideBy2(decNumber):remstack = Stack()while decNumber > 0:rem = decNumber % 2remstack.push(rem)decNumber = decNumber // 2binString = ""while not remstack.empty():binString = binString + str(remstack.pop())return binStringif __name__ == '__main__':print(divideBy2(42))
运行结果：
$ python dec2bin.py
101010