数据结构入门（一）栈的实现

从这一篇文章开始，笔者将会正式进入数据结构的领域，后面也将会持续更新。
本文将会讲述一种特殊的线性表结构：栈（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来实现栈，实现的方法分别为：栈的初始化，栈的长度，判断栈是否为空，元素入栈，栈顶元素，元素退栈。
我们先来测试下栈的使用情况，代码如下：

from Stack import Stack

s = Stack()

s.push(5)
s.push(3)
print(len(s))
print(s.pop())
print(s.is_empty())
print(s.pop())
print(s.is_empty())
s.push(7)
s.push(9)
print(s.top())
s.push(4)
print(len(s))
print(s.pop())

输出结果如下：

2
3
False
5
True
9
3
4

OK，我们已经实现了栈这个结构。接下来，我们将使用栈结构去解决一个实际问题：数的进制转换，作为栈的第一个应用实例，后续笔者会有专门的文章讲述栈的应用。

十进制数N和其他d进制数的转换是计算机实现计算得基本问题，其解决方法如下：
N = (N div d) * d + N mod d（其中，div为整除运算，mod为求余运算）。
例如， $(2018)_{10}=(3742)_{8}$ ，其运算结果如下：

N	N div 8	N mod 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='')

输出结果如下：

搞定，代码非常之简洁！如果我们用普通方法去实现这个程序，可能会稍显麻烦，而使用栈，就会简单很多。
本次分享到此结束，欢迎大家交流~~

注意：本人现已开通微信公众号： Python爬虫与算法（微信号为：easy_web_scrape），欢迎大家关注哦~~

数据结构入门（一）栈的实现

推荐阅读更多精彩内容