Python数据结构与算法-队列和双端队列

末蓝、 2022-05-14 10:00 181阅读 0赞

### 1.普通队列： ###

队列的实现:队列是先进先出的；相对于栈，栈是先进后出的

#coding=gbk
    #队列的实现:队列是先进先出的
    #Queue() 创建一个空的队列
    # enqueue(item) 往队列中添加一个item元素
    # dequeue() 从队列头部删除一个元素
    # is_empty() 判断一个队列是否为空
    # size() 返回队列的大小
    class Queue():
        '''队列的实现'''
        def __init__(self):
            self.items = []
            
        def is_empty(self):
            return len(self.items) == 0
        
        def size(self):
            return len(self.items)
        
        def enqueue(self, item):
            self.items.insert(0, item)
            
        def dequeue(self):
            self.items.pop()
        def show(self):
            print(self.items)
            
    q = Queue()
    q.enqueue(11)
    q.enqueue(12)
    q.enqueue(13)
    print(q.size()) # 3
    q.show()    # [13, 12, 11]
    q.dequeue()
    q.dequeue()
    q.show()    #[13]

### 2.双端队列 ###

#双端队列
    # Deque() 创建一个空的双端队列
    # add_front(item) 从队头加入一个item元素
    # add_rear(item) 从队尾加入一个item元素
    # remove_front() 从队头删除一个item元素
    # remove_rear() 从队尾删除一个item元素
    # is_empty() 判断双端队列是否为空
    # size() 返回队列的大小
    class Deque():
        def __init__(self):
            self.items = []
        def is_empty(self):
            return len(self.items) == 0
        
        def size(self):
            return len(self.items)
        
        def add_front(self,item):
            self.items.insert(0, item)
            
        def add_rear(self, item):
            self.items.append(item)
            
        def remove_front(self):
            self.items.pop(0)
        
        def remove_rear(self):
            self.items.pop()
        
        def show(self):
            print(self.items)
    
    print('test dque-----')
    d = Deque()
    d.add_front(10)
    d.add_front(11)
    d.show()  #[11, 10] 
    d.add_rear(12)
    d.add_rear(13)
    d.show()  # [11, 10, 12, 13]
    d.remove_front()
    d.show()  #[10, 12, 13] 
    d.remove_rear()
    d.show()    # [10, 12]
    print(d.size()) # 2
    print(d.is_empty()) #False