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

浅浅的花香味﹌ 2022-04-11 11:13 177阅读 0赞

从这一篇文章开始，笔者将会正式进入数据结构的领域，后面也将会持续更新。  
  本文将会讲述一种特殊的线性表结构：栈（stack）。  
  **栈**，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为**栈顶**（top），相应地，表头端称为**栈底**（bottom）。不含任何元素的空表称为空栈。  
  假设栈 S = ( a 1 , a 2 , . . . , a n ) , S=(a\_\{1\},a\_\{2\},...,a\_\{n\}), S=(a1,a2,...,an),则称 a 1 a\_\{1\} a1为栈底元素， a n a\_\{n\} an为栈顶元素。栈中元素按 a 1 , a 2 , . . . , a n a\_\{1\},a\_\{2\},...,a\_\{n\} a1,a2,...,an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按**后进先出**的原则进行的，如下图所示：

![栈的示意图][1240]

因此，栈又被称为后进先出（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 (2018)\_\{10\}=(3742)\_\{8\} (2018)10=(3742)8，其运算结果如下：

因此，如果我们需要将十进制数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）， 欢迎大家关注哦~~

[1240]: /images/20220411/8c39051cc6874848ae694b7041071505.png
[Stack.py]: http://Stack.py