一、概述

堆栈（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() == 0    def 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 % 2        remstack.push(rem)        decNumber = decNumber // 2    binString = ""    while not remstack.empty():        binString = binString + str(remstack.pop())    return binStringif __name__ == '__main__':    print(divideBy2(42))

运行结果：

$ python dec2bin.py101010