2020-11-15 数据结构与算法(4) 栈与队列

1411-李同学

发表文章数:148

热门标签

, ,
首页 » 数据结构 » 正文

栈与队列

概念:栈,也称为堆栈,是一种容器,可存入数据元素,访问元素、删除元素。它的特点在于只能允许在容器的一段进行加入数据和输出数据的运算。没有了位置概念,保证任何时候可以访问、删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序。

原理运作:后进先出

队列

队列是只允许在一段进行插入操作,而在另一端进行删除操作的列表。

队列是一种先进先出的线性表。允许插入的一端为队尾,允许删除的一端为队头。队列不允许在中间部位进行操作!

栈的实现

栈可以用顺序表或链表实现

  • 压栈(入栈)

  • 出栈

class Stack(object):
    def __init__(self):
        self.__List=[] #将list设为私有属性
    def push(self,item):
        self.__List.append(item) #选择在尾部压栈时间复杂度低

    def pop(self):
        return self.__List.pop()


    def peek(self):
        if self.__List:
            return self.__List[-1]
        else:
            return  self.__List==[]
            #return not self.__List

    def is_empty(self):
        if self.__List is not True:
            return None

    def size(self):
        return len(self.__List)

if __name__=="__main__":
    s=Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())

队列的实现

class Queue(object):
    def __init__(self):
        self.__list=[]
    def enqueue(self,item):
        self.__list.append(item) 
        #使用list时,append时间复杂度低
        #使用链表时,add时间复杂度低,append需要遍历。

    def dequeue(self):
        return self.__list.pop(0)

    def is_empty(self):
        return not self.__list

    def size(self):
        return len(self.__list)


if __name__=="__main__":
    q=Queue()
    q.enqueue(20)
    q.enqueue(30)
    q.enqueue(40)
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

双端队列

概念:是一种具有队列和栈的性质的数据结构

双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两顿进行。双端队列可以在队列任意一端入队和出队。

class Dequeue(object):
    def __init__(self):
        self.__list=[]

    def add_front(self,item):
        self.__list.insert(0,item)
        #使用list时,append时间复杂度低
        #使用链表时,add时间复杂度低,append需要遍历。

    def add_rear(self,item):
        self.__list.append(item)

    def pop_front(self):
        return self.__list.pop(0)

    def pop_rear(self):
        return self.__list.pop()

    def is_empty(self):
        return not self.__list

    def size(self):
        return len(self.__list)


if __name__=="__main__":
    d=Dequeue()
    d.add_front(30)
    d.add_front(20)
    d.add_rear(40)
    d.add_rear(50)
    print(d.pop_front())
    print(d.pop_front())
    print(d.pop_rear())
    print(d.pop_rear())

未经允许不得转载:作者:1411-李同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《2020-11-15 数据结构与算法(4) 栈与队列》 发布于2020-11-15

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录