亲宝软件园·资讯

展开

Python 栈

盼小辉丶 人气:0

0. 学习目标

栈和队列是在程序设计中常见的数据类型,从数据结构的角度来讲,栈和队列也是线性表,是操作受限的线性表,它们的基本操作是线性表操作的子集,但从数据类型的角度来讲,它们与线性表又有着巨大的不同。本节将首先介绍栈的定义和其不同实现,并且给出栈的一些实际应用。

通过本节学习,应掌握以下内容:

1. 栈的基本概念

1.1 栈的基本概念

栈 (Stack) 是限定仅在序列一端执行插入和删除操作的线性表,对于栈而言,可进行操作的一端称为栈顶 (top),而另一端称为栈底 (bottom)。如果栈中不含任何元素则称其为空栈。

栈提供了一种基于在集合中的时间来排序的方式,最近添加的元素靠近顶端,旧元素则靠近底端。最新添加的元素被最先移除,这种排序原则也称为后进先出 (last in first out, LIFO) 或先进后出 (fast in last out, FILO)。

栈在现实中的例子随处可见,如下图所示,球桶中的球构成了一个栈,每次只能从顶部取出一个,放回时也只能置于顶部。假设栈为S = ( a0 , a1 , … , en)为栈顶元素,栈中元素按的顺序入栈 (push),而栈顶元素是第一个退栈 (pop) 的元素。

通过观察元素的添加和移除顺序,就可以快速理解栈所蕴含的思想。下图展示了栈的入栈和出栈过程,栈中元素的插入顺序和移除顺序恰好是相反的。

1.2 栈抽象数据类型

除了主要的操作(入栈和出栈)外,栈还具有初始化、判空和取栈顶元素等辅助操作。具体而言,栈的抽象数据类型定义如下:

基本操作:

1. __itit__(): 初始化栈

创建一个空栈

2. size(): 求取并返回栈中所含元素的个数 n

若栈为空,则返回整数0

3. isempty(): 判断是否为空栈

判断栈中是否存储元素

4. push(data): 入栈

将元素 data 插入栈顶

5. pop(): 出栈

删除并返回栈顶元素

4. peek(): 取栈顶元素

返回栈顶元素值,但并不删除元素

1.3 栈的应用场景

栈具有广泛的应用场景,例如:

除了以上应用外,我们在之后的学习中还将看到栈用作许多算法的辅助数据结构。

2. 栈的实现

和线性表一样,栈同样有两种存储表示方式。

2.1 顺序栈的实现

顺序栈是栈的顺序存储结构,其利用一组地址连续的存储单元从栈底到栈顶依次存放。同时使用指针top来指示栈顶元素在顺序栈中的索引,同样顺序栈可以是固定长度和动态长度,当栈满时,定长顺序栈会抛出栈满异常,动态顺序栈则会动态申请空闲空间。

2.1.1 栈的初始化

顺序栈的初始化需要三部分信息:stack 列表用于存储数据元素,max_size 用于存储 stack 列表的最大长度,以及 top 用于记录栈顶元素的索引:

class Stack:
    def __init__(self, max_size=10):
        self.max_size = max_size
        self.stack = self.max_size * [None]
        self.top = -1

2.1.2 求栈长

由于 top 表示栈顶元素的索引,我们可以据此方便的计算顺序栈中的数据元素数量,即栈长:

    def size(self):
        return self.top + 1

2.1.3 判栈空

根据栈的长度可以很容易的判断栈是否为空栈:

    def isempty(self):
        if self.size() == 0:
            return True
        else:
            return False

2.1.4 判栈满

由于需要提前申请栈空间,因此我们需要能够判断栈是否还有空闲空间:

    def isfully(self):
        if self.size() == self.max_size:
            return True
        else:
            return False

2.1.5 入栈

入栈时,需要首先判断栈中是否还有空闲空间,然后根据栈为定长顺序栈或动态顺序栈,入栈操作稍有不同:

[定长顺序栈的入栈操作] 如果栈满,则引发异常:

    def push(self, data):
        if self.isfully():
            raise IndexError('Stack Overflow!')
        else:
            self.top += 1
            self.stack[self.top_1] = data

[动态顺序栈的入栈操作] 如果栈满,则首先申请新空间:

    def resize(self):
        new_size = 2 * self.max_size
        new_stack = [None] * new_size
        for i in range(self.num_items):
            new_stack[i] = self.items[i]
        self.stack = new_stack
        self.max_size = new_size
    def push(self, data):
        if self.isfully():
            self.resize()
        else:
            self.top += 1
            self.stack[self.top_1] = data

入栈的时间复杂度为O(1)。这里需要注意的是,虽然当动态顺序栈满时,原栈中的元素需要首先复制到新栈中,然后添加新元素,但根据《顺序表及其操作实现》中顺序表追加操作的介绍,由于n次入栈操作的总时间T(n) 与O(n) 成正比,因此入栈的摊销时间复杂度仍可以认为是O(1)。

2.1.6 出栈

若栈不空,则删除并返回栈顶元素:

    def pop(self):
        if self.isempty():
            raise IndexError('Stack Underflow!')
        else:
            result = self.stack[self.top]
            self.top -= 1
            return result

2.1.7 求栈顶元素

若栈不空,则只需返回栈顶元素:

    def peek(self):
        if self.isempty():
            raise IndexError('Stack Underflow!')
        else:
            return self.stack[self.top]

2.2 链栈的实现

栈的另一种存储表示方式是使用链式存储结构,因此也常称为链栈,其中 push 操作是通过在链表头部插入元素来实现的,pop 操作是通过从头部删除节点来实现的。

2.2.1 栈结点

栈的结点实现与链表并无差别:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    def __str__(self):
        return str(self.data)

2.2.2 栈的初始化

栈的初始化函数中,使栈顶指针指向 None,并初始化栈长:

class Stack:
    def __init__(self):
        self.top = None
        # 栈中元素数
        self.length = 0

2.2.3 求栈长

返回 length 的值用于求取栈的长度,如果没有 length 属性,则需要遍历整个链表才能得到栈长:

    def size(self):
        return self.length

2.2.4 判栈空

根据栈的长度可以很容易的判断栈是否为空栈:

    def isempty(self):
        if self.length == 0:
            return True
        else:
            return False

2.2.5 入栈

入栈时,在栈顶插入新元素即可:

    def push(self, data):
        p = Node(data)
        p.next = self.top
        self.top = p
        self.length += 1

由于插入元素是在链表头部进行的,因此入栈的时间复杂度为O(1),在这种情况下链尾作为栈底 。

2.2.6 出栈

若栈不空,则删除并返回栈顶元素:

    def pop(self):
        if self.isempty():
            raise IndexError("Stack Underflow!")
        ele = self.top.data
        self.top = self.top.next
        self.length -= 1
        return ele

由于删除元素仅需修改头指针指向其 next 域,因此出栈的时间复杂度同样为O(1)。

2.2.7 求栈顶元素

若栈不空,返回栈顶元素即可,但栈顶元素并不会被删除:

    def peek(self):
        if self.isempty():
            raise IndexError("Stack Underflow!")
        return self.top.data

2.3 栈的不同实现对比

本节我们将对比栈的不同实现之间的异同:

顺序栈

链栈

3. 栈应用

接下来,我们首先测试上述实现的链表,以验证操作的有效性,然后利用实现的基本操作来解决实际算法问题。

3.1 顺序栈的应用

首先初始化一个顺序栈 stack,然后测试相关操作:

# 初始化一个最大长度为4的栈
s = Stack(4)
print('栈空?', s.isempty())
for i in range(4):
    print('入栈元素:', i)
    s.push(i)
print('栈满?', s.isfully())
print('栈顶元素:', s.peek())
print('栈长度为:', s.size())
while not s.isempty():
    print('出栈元素:', s.pop())

测试程序输出结果如下:

栈空? True
入栈元素: 0
入栈元素: 1
入栈元素: 2
入栈元素: 3
栈满? True
栈顶元素: 3
栈长度为: 4
出栈元素: 3
出栈元素: 2
出栈元素: 1
出栈元素: 0

3.2 链栈的应用

首先初始化一个链栈 stack,然后测试相关操作:

# 初始化新栈
s = Stack()
print('栈空?', s.isempty())
for i in range(4):
    print('入栈元素:', i)
    s.push(i)
print('栈顶元素:', s.peek())
print('栈长度为:', s.size())
while not s.isempty():
    print('出栈元素:', s.pop())

测试程序输出结果如下:

栈空? True
入栈元素: 0
入栈元素: 1
入栈元素: 2
入栈元素: 3
栈顶元素: 3
栈长度为: 4
出栈元素: 3
出栈元素: 2
出栈元素: 1
出栈元素: 0

3.3 利用栈基本操作实现复杂算法

匹配符号是指正确地匹配左右对应的符号(符号允许进行嵌套),不仅每一个左符号都有一个右符号与之对应,而且两个符号的类型也是一致的,下标展示了一些符号串的匹配情况:

符号串是否匹配
[]()()匹配
[(())()不匹配
{([]())}匹配
(())[]}不匹配

为了检查符号串的匹配情况,需要遍历符号串,如果字符是 (、[ 或 { 之类的开始分隔符,则将其写入栈中;当遇到诸如 )、] 或 } 等结束分隔符时,则栈顶元素出栈,并将其与当前遍历元素进行比较,如果它们匹配,则继续解析符号串,否则表示不匹配。当遍历完成后,如果栈不为空,则同样表示不匹配:

def isvalid_expression(expression):
    stack = Stack()
    symbols = {')':'(', ']':'[', '}':'{'}
    for s in expression:
        if s in symbols:
            if stack:
                top_element = stack.pop()
            else:
                top_element = '#'
            if symbols[s] != top_element:
                return False
        else:
            stack.push(s)
    return not stack

由于我们只需要遍历符号串一边,因此算法的时间复杂度为O(n),算法的空间复杂度同样为O(n)。

给定一链表(带有头结点) L : L0→L1→…→Ln ,将其重排为:L0→Ln→L1→Ln−1 … 。

例如链表中包含 9 个元素,则下图现实了重排前后的链表元素情况:

由于栈的先进后出原则,可以利用栈与原链表的配合进行重排,首次按遍历链表,将每个结点入栈;栈中元素的出栈顺序为原链表结点的逆序,然后交替遍历链表和栈,构建新链表。

def reorder_list(L):
    p = L.head.next
    if p == None:
        return L
    stack = Stack()
    while p!= None:
        stack.push(p)
        p = p.next
    l = L.head.next
    from_head = L.head.next
    from_stack = True
    while (from_stack and l != stack.peek() or (not from_stack and l != from_head)):
        if from_stack:
            from_head = from_head.next
            l.next = stack.pop()
            from_stack = False
        else:
            l.next = from_head
            from_stack = True
        l = l.next
    l.next = None

该算法的时间复杂度和空间复杂度均为O(n)。

加载全部内容

相关教程
猜你喜欢
用户评论