HuaPu在学：Python数据结构与算法【栈 & 队列】

以下是花圃在学习Python的数据结构与算法的一些要点内容笔记。

实际上，栈(stack)代表一种容器，又称堆栈，服从的是后进先出(LIFO)的原则，先进去的只能是最后取，后进去的首先取。那么栈实际上也是数据结构，之前我们又提“链表”，那么链表更关注的就是数据之间的关系，如何存储数据，试想一下，无论是顺序表还是单链表如果我将一些头插法和insert等方法进行强制规定，那么这个时候完全可以就将其称之为“栈”，这样看来。栈更关注的是数据的操作问题。

队列也是一种线性的容器，栈仅支持从一端操作，无论存取；队列是只允许从一端取，另一端存，真么一个类似排队的结构，称之为队列。特点就是先进先出（FIFO）。

双端队列可以理解为两个栈的底部相接。

以顺序表实现：

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

    def push(self,item):
        self.__list.append(item)
        pass

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

    def peek(self):
        if self.is_empty():
            return None
        else:
            return self.__list[-1]
        pass

    def is_empty(self):
        if self.__list:
            return False
        else:
            return True
        pass

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

    pass


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

    def enqueue(self,item):
        self.__list.append(item)
        pass

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

    def is_empty(self):
        if self.__list:
            return False
        else:
            return True
        pass

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

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

    def add_front(self,item):
        self.__list.insert(0,item)
        pass

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

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

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

    def is_empty(self):
        if self.__list:
            return False
        else:
            return True
        pass

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

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

    print("=================================")

    q=Queue()
    print(q.size())
    print(q.is_empty())
    q.enqueue(4)
    q.enqueue(5)
    q.enqueue(6)
    print(q.size())
    print(q.is_empty())
    print(q.dequeue())
    print(q.dequeue())

    print("=================================")

    d=Deque()
    print(d.size())
    print(d.is_empty())
    d.add_front(10)
    d.add_front(20)
    d.add_rear(30)
    d.add_rear(40)
    print(d.pop_front())
    print(d.pop_rear())

0
True
3
3
False
3
2
=================================
0
True
3
False
4
5
=================================
0
True
20
40