2020/10/01

栈

是一种装元素的容器，也是操作方法，就好像一个水杯一样只用一端开口用来加入数据和输出数据。没有位置的概念，最靠近杯口的数据可以随时访问，删除。这个原理就是LIFO（last in first out）

栈的实现

需要具有以下功能
stack() 创建一个新的空栈
push(item) 添加一个新的元素
pop（）弹出栈顶元素
peek（） 返回栈顶元素
is_empty() 判断栈是否为空
size（）返回栈的元素个数

class Stack(object):
    def __init__(self):
        self.__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 None

    def is_empty(self):
        return not self.__list

    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())

队列

也是就好像水管一样，在意的是FIFO（First in first out），一端获取数据，另一端输出数据

队列的实现

必须有以下操作
Queue（）创建一个空的队列
enqueue（）往队列力添加一个元素
dequeue（）从队列头部删除一个元素
is_empty（）判断一个队列是否为空
size（）返回队列的大小

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

    def enqueue(self, item):
        self.__list.append(item)
        # self.__list.insert(0,item)   注意看这个队列最后哪个的操作多。输入的多就用第一个，输出的多就用第二个

    def dequeue(self):
        return self.__list.pop(0)
        #return self.__list.pop()
    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)
    q.enqueue(4)
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

双端队列

就是两个头都可以储存和输出元素。其实就是两个栈叠加在一起

双端队列的实现方法

Deque（）创建一个空的双端队列
add_front(item)从队头加入
add_rear(item)从队尾加入
remove_front()从队头删除
remove_rear()从队尾删除
is_empty()看是否空
size()看大小

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

    def add_font(self, item):
        self.__list.insert(0, item)

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

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

    def remove_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 = Deque()
    d.add_font(1)
    d.add_font(3)
    d.add_font(5)
    d.add_font(7)
    print(d.remove_font())
    print(d.remove_font())
    print(d.remove_font())
    print(d.remove_font())

排序算法

排序算法（Sorting algorithm）其实是将无序的列表数据依照特定顺序进行排列的一种算法

排序算法的稳定性
排序之后的序列和排序前的序列，条件后还是在相同的位置。叫稳定，反之就不稳定

冒泡排序（Bubble Sort）

无序序列排成按从小到大有序序列，两个，两个的对比。两个数中较大的那个排在后面，比较一遍后最大的在最右边。这时候就需要两个两个比较前面的n-1个元素。再继续比较。

def bubble(alist):
    for j in range(len(alist)-1, 0, -1):
    	count = 0
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count += 1
            if count == 0:
            	return


if __name__ == "__main__":
    a = [54, 98, 100, 20, 76, 2, 55, 30]
    print(a)
    bubble(a)
    print(a)

最优时间复杂O（n）
最坏时间复杂度是O（n**2）
稳定性：稳定

最后

以上就是兴奋背包为你收集整理的Day 18 ：栈，队列，冒泡排序2020/10/01的全部内容，希望文章能够帮你解决Day 18 ：栈，队列，冒泡排序2020/10/01所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。