python学习笔记_第29天(栈+列队)

1544-陈同学

发表文章数:60

热门标签

,
首页 » 数据结构 » 正文


顺序表(list)与链表解析存储模式,栈、队列、树是具体应用场景。

队列一端添加,另一端取数,先进先出

栈(stack)是一种容器,也称为堆栈。特点在于只允许在容器的一端(称为栈顶top)进行压栈(加入数据push)和出栈(输出数据pop)。没有位置概念,确定了默认访问顺序,按照后进先出(LIFO, Last In First Out)的原理运作。
栈可以用顺序表(list)实现,也可以用链表实现。
python学习笔记_第29天(栈+列队)

栈的操作

操作 说明
Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数

栈操作具体实现

class Stack:
'''栈只支持数据从一头进出,先进后出'''
    def __init__(self):
        self.__list = []

    def push(self, item):
        '''添加一个新的元素item到栈顶'''
        self.__list.append(item)
        # 用顺序表存储法构造栈时,头部操作的时间复杂度为O(n),尾部操作的时间复杂度为O(1)
        # self.__list.insert(0,item)  # 头部操作更优

    def pop(self):
        '''弹出栈顶元素'''
        return self.__list.pop()
        # 若用链表存储法构造栈时,则头部操作的时间复杂度更低
        # return self.__list.pop(0)  # 头部操作更优

    def peek(self):
        '''返回栈顶元素'''
        if self.__list:  # 当列表存在且不为空
            return self.__list[-1]  # 尾部操作,切片操作返回尾部最后一个元素值
        else:
            return None

    def is_empty(self):
        '''判断栈是否为空'''
        return self.__list == []  # 0、空字符串、空列表、空字典、空元祖等逻辑值为False

    def size(self):
        '''返回栈的元素个数'''
        return len(self.__list)

测试

if __name__ == "__main__":
    '''栈先进后出'''
    stack = Stack()
    stack.push("hello")
    stack.push("world")
    stack.push("python")
    print(stack.size())
    print(stack.peek())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

执行结果:
3
python
python
world
hello

队列

队列(queue)允许插入的一端为队尾,允许删除的一端为队头。特点在于只允许在一端进行插入操作(enqueue),另一端进行删除操作(dequeue)。按照先进先出(First In First Out)的原理运作,简称FIFO。
队列不允许在中间部位进行操作! 假设队列是q=(a1,a2,……,an),那么a1就是队头元素,而an是队尾元素。删除时从a1开始,而插入时总是在队列最后。
队列也可以用顺序表(list)或者链表实现。
python学习笔记_第29天(栈+列队)

列队的操作

操作 说明
Queue() 创建一个空的队列
enqueue(item) 往队列尾添加一个item元素
dequeue() 从队列头部删除一个元素
is_empty() 判断一个队列是否为空
size() 返回队列的大小

列队操作具体实现

class Queue:
    '''队列一端添加,另一端取数,先进先出'''

    def __init__(self):
        self.__list = []

    # 入队操作和出队操作那个使用更频繁,决定了从列表头部操作还是从列表尾部操作
    def enqueue(self, item):
        '''往队列中添加一个item元素'''
        self.__list.append(item)  # 时间复杂度O(1)
        # self.__list.insert(0,item)  # 时间复杂度O(n)

    def dequeue(self):
        '''从队列头部删除一个元素'''
        return self.__list.pop(0)  # 时间复杂度O(n)
        # return self.__list.pop()  # 时间复杂度O(1)

    def is_empty(self):
        '''判断一个队列是否为空'''
        return self.__list == []

    def size(self):
        '''返回队列的大小'''
        return len(self.__list)

测试

if __name__ == "__main__":
    '''队列先进先出'''
    queue = Queue()
    queue.enqueue("hello")
    queue.enqueue("world")
    queue.enqueue("python")
    print(queue.size())
    print(queue.is_empty())
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.dequeue())

执行结果:
3
False
hello
world
python

双端队列

双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构,可以看做两个栈底部相连的情况。
双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
python学习笔记_第29天(栈+列队)

双端列队的操作

操作 说明
Deque() 创建一个空的双端队列
add_front(item) 从队头加入一个item元素
add_rear(item) 从队尾加入一个item元素
remove_front() 从队头删除一个item元素
remove_rear() 从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小

双端列队操作具体实现

class Deque:
    '''双端队列'''

    def __init__(self):
        self.__list = []

    # 入队操作和出队操作那个使用更频繁,决定了从列表头部操作还是从列表尾部操作
    def add_front(self, item):
        '''从队头加入一个item元素'''
        self.__list.insert(0, item)  # 时间复杂度O(n)

    def add_rear(self, item):
        '''从队尾加入一个item元素'''
        self.__list.append(item)  # 时间复杂度O(1)

    def remove_front(self):
        '''从队头删除一个item元素'''
        return self.__list.pop(0)  # 时间复杂度O(n)

    def remove_rear(self):
        '''从队尾删除一个item元素'''
        return self.__list.pop()  # 时间复杂度O(1)

    def is_empty(self):
        '''判断一个队列是否为空'''
        return self.__list == []

    def size(self):
        '''返回队列的大小'''
        return len(self.__list)

未经允许不得转载:作者:1544-陈同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《python学习笔记_第29天(栈+列队)》 发布于2021-02-19

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录