python复杂数据结构之栈

栈是一种后进先出的数据结构，python列表的本身就是实现栈结构的基本操作，例如列表的append()方法是在列表的尾部追加元素，pop()方法实在列表的尾部删除元素，这和栈的操作类似。但是直接使用python列表对象模拟栈操作是不推荐的，当列表的元素为空时如果再次执行pop()方法那么会抛出异常，另外列表也无法限制栈空间的大侠。

使用列表的方式表示栈：

>>> myStack = []
>>> myStack.append(3)
>>> myStack.append(5)
>>> myStack.append(7)
>>> myStack
[3, 5, 7]
>>> myStack.pop()
7
>>> myStack.pop()
5
>>> myStack.pop()
3
>>> myStack.pop()
Traceback (most recent call last):
File "<pyshell#7>", line 1, in <module>
myStack.pop()
IndexError: pop from empty list

封装列表实现栈结构：

class Stack:
    def __init__(self, size = 10):
        self._content = []                 #使用列表存放栈的元素
        self._size = size                  #初始栈大小
        self._current = 0                  #栈中元素个数初始化为0

    def empty(self):
        self._content = []
        self._current = 0

    def isEmpty(self):
        if not self._content:
            return True
        else:
            return False
       def setSize(self, size):
        #如果缩小栈空间，则删除指定大小之后的已有元素
        if size < self._current:
            for i in range(size, self._current)[::-1]:
                del self._content[i]
            self._current = size
        self._size = size

    def isFull(self):
        if self._current == self._size:
            return True
        else:
            return False
def push(self, v):
        if len(self._content) < self._size:
            self._content.append(v)
            self._current = self._current+1 #栈中元素个数加1
        else:
            print('Stack Full!')

    def pop(self):
        if self._content:
            self._current = self._current-1 #栈中元素个数减1
            return self._content.pop()
        else:
            print('Stack is empty!')
       def show(self):
        print(self._content)

def showRemainderSpace(self):
print('Stack can still PUSH ', self._size-self._current, ' elements.')

if __name__ == '__main__':
print('Please use me as a module.')

自定义栈的用法：

和队列一样，idle的官方安装包中并不提供栈的模块，以上定义的模块可以使用，把以上定义的结构当成一个模块来使用。

>>> import Stack
>>> x = Stack.Stack()
>>> x.push(1)
>>> x.push(2)
>>> x.show()
[1, 2]
>>> x.pop()
2
>>> x.show()
[1]
>>> x.showRemainderSpace()
Stack can still PUSH 9 elements.
>>> x.isEmpty()
False
>>> x.isFull()
False

下面一篇文章介绍了如何在idle中引入自定义的模块，上面的栈结构需要引用才能把它当成模块使用：

import的是 *.py文件名

https://www.cnblogs.com/memory4young/p/python-import-module.html

python复杂数据结构之栈

相关推荐