从这一篇文章开始，笔者将会正式进入数据结构的领域，后面也将会持续更新。
本文将会讲述一种特殊的线性表结构：栈（stack）。
栈，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（bottom）。不含任何元素的空表称为空栈。
假设栈\(S=(a_{1},a_{2},...,a_{n}),\)则称\(a_{1}\)为栈底元素，\(a_{n}\)为栈顶元素。栈中元素按\(a_{1},a_{2},...,a_{n}\)的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如下图所示：
因此，栈又被称为后进先出（last in first out）的线性表（简称LIFO结构）。
栈的基本操作有：栈的初始化，判断是否为空，取栈顶元素，在栈顶进行插入和删除等。我们将借助Python中的列表来实现栈这个结构，完整的Python代码（Stack.py）如下：
# -*- coding: utf-8 -*- class Empty(Exception): # Error attempting to access an element from an empty container pass class Stack: # initialize def __init__(self): self.__data = [] # length of Stack def __len__(self): return len(self.__data) # whether the Stack is empty def is_empty(self): return len(self.__data) == 0 # push an element is Stack def push(self, e): self.__data.append(e) # top element of Stack def top(self): if self.is_empty(): raise Empty('Stack is empty') return self.__data[-1] # remove the top element of Stack def pop(self): if self.is_empty(): raise Empty('Stack is empty') return self.__data.pop()在上述代码中，我们先定义了一个错误类型Empty，当你试图从一个空的容器中获取元素时，则会提示这个错误。接下来，定义了类Stack来实现栈，实现的方法分别为：栈的初始化，栈的长度，判断栈是否为空，元素入栈，栈顶元素，元素退栈。
我们先来测试下栈的使用情况，代码如下：
输出结果如下：
2 3 False 5 True 9 3 4OK，我们已经实现了栈这个结构。接下来，我们将使用栈结构去解决一个实际问题：数的进制转换，作为栈的第一个应用实例，后续笔者会有专门的文章讲述栈的应用。
十进制数N和其他d进制数的转换是计算机实现计算得基本问题，其解决方法如下：
N = (N div d) * d + N mod d（其中，div为整除运算，mod为求余运算）。
例如，\((2018)_{10}=(3742)_{8}\)，其运算结果如下：
2018 252 2
252 31 4
31 3 7
3 0 3
因此，如果我们需要将十进制数N转化为其他d进制数，比如8，我们只需要将第三列的N mod 8逆序输出即可，这可以借助栈很好地实现，实现的Python代码如下：
from Stack import Stack # 十进制数 N = 2018 s = Stack() while N: s.push(N % 8) N //= 8 # 八进制数 while not s.is_empty(): print(s.pop(), end='')输出结果如下：
3742搞定，代码非常之简洁！如果我们用普通方法去实现这个程序，可能会稍显麻烦，而使用栈，就会简单很多。
本次分享到此结束，欢迎大家交流~~
注意：本人现已开通微信公众号： Python爬虫与算法（微信号为：easy_web_scrape）， 欢迎大家关注哦~~