了解顺序表及其顺序表中的栈和队列

一、什么是顺序表

将元素顺序的存放在一块儿连续的存储区里，元素间的顺序关系由他们的存储顺序自然表示

二、顺序表的分类 1.同类型数据顺序表

顺序表都是存储一样的类型，例如：

li=[200,390,78,121]

2.python中不同数据类型的顺序表

li=[12,'ab',1.111,1000]

面试题：python中不同类型的数据如何存储在同一个列表？

每一个数据类型所占得存储空间大小不一样，但是他们的地址名称类型是一样的，所以我们可以把地址名称建一个顺序表，而存储这个地址表的地址是连续的，因此例如我们在读li[2]的过程，实际上进行的顺序是： 先找到li的存储地址，是0x324，其次再偏移两个字节，找到0x332，然后找到0x332这个地址所对应的地址，然后可以找到这个地址对应的数据，再读取出来。

三、栈

特点：先进后出，后进先出（在同一端操作）

# 栈：先进后出，后进先出

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

    # 进栈
    def push(self, item):
        self.__list.append(item)

    # 出栈
    def pop(self):
        if not self.empty():
            return self.__list.pop()

    # 求栈的个数
    def length(self):
        return len(self.__list)

    # 返回栈顶元素
    def peek(self):
        if not self.empty():
            return self.__list[-1]

    #  求栈是否为空
    def empty(self):
        return self.__list == []

if __name__ == '__main__':
    s=Stack()
    print(s.empty())
    print(s.pop())
    s.push(1)
    s.push(2)
    s.push(3)
    print(s.empty())
    print(s.pop())
    print(s.length())

四、队列

• 特点：先进先出，后进后出

单端队列：一端插入一端删除，即可满足先进先出

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

    def enqueue(self, item):
        # 往队列中添加一个item元素,从尾部添加复杂度为O(1),若从头部，则弹出从尾部
        self.__list.append(item)

    def dequeue(self):
        # 弹出一个元素，要与入队的方向相反,此时复杂度为O(n)
        return self.__list.pop(0)

    def is_empty(self, item):
        # 判断队列是否为空
        return self.__list == []

    def size(self, item):
        # 返回队列中元素个数
        return len(self.__list)


if __name__ == '__main__':
    s = Queue()
    s.enqueue(1)
    s.enqueue(2)
    print(s.dequeue())  # 1
    print(s.dequeue())  # 2

双端队列：头部和尾部都可以插入和删除

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

    def add_front(self, item):
        # 往队列头部添加一个item元素
        self.__list.insert(0, item)

    def add_rear(self, item):
        # 往队列尾部添加一个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, item):
        # 判断队列是否为空
        return self.__list == []

    def size(self, item):
        # 返回队列中元素个数
        return len(self.__list)


if __name__ == '__main__':
    s = Queue()
    s.enqueue(1)
    s.enqueue(2)
    print(s.dequeue())  # 1
    print(s.dequeue())  # 2