数据结构与算法全套精讲(python版) (三)栈与队列

怼烎@ 2021-12-16 14:29 208阅读 0赞

**1. 栈stack **

开口那端叫栈顶；

既可用顺序表(连续存储)，也可用链表表示(离散存储)。

#栈
    class Stack(object):#object表示继承
        def __init__(self):
            self.__list = []
    
        def push(self,item):#压栈
            return self.__list.append(item)
    
        def pop(self):#弹栈
            return self.__list.pop()
    
        def peek(self):#返回栈顶值，但是不改动栈
            if self.__list:#非空
                return self.__list[-1]
    
        def is_empty(self):
            return not self.__list#True
    
        def size(self):
            return len(self.__list)
    
    if __name__ == '__main__':
        s = Stack()
        s.push(1)
        s.push(2)
        s.push(3)
        print(s.pop())
        print(s.pop())
        print(s.pop())

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70][]

**2. 队列 list**

(1).单端队列

class Queue(object):#队列
        def __init__(self):
            self.__list = []
    
        def enqueue(self,item):#入队
            return self.__list.append(item)
    
        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(1)
        q.enqueue(2)
        q.enqueue(3)
        print(q.dequeue())
        print(q.dequeue())
        print(q.dequeue())

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1][]

(2). 双端队列deque(double-ended queue):同时具有队列与栈的性质

![20190703222705504.png][]

class Deque(object):#双端队列
        def __init__(self):
            self.__list = []
    
        def add_front(self,item):#入队首
            return self.__list.insert(0,item)
    
        def add_rear(self,item):#入队尾
            return 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__':
        q = Deque()

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70]: /images/20211214/263a78e20233454fbf6b0fa41bfabe86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1]: /images/20211214/9ada0d8855584411a60755115236d328.png
[20190703222705504.png]: /images/20211214/b5462eb1d0944d6b820051709957b284.png