Python数据结构与算法(五)—– 栈、队列和排序

756-周同学

发表文章数:47

热门标签

, , ,
首页 » 数据结构 » 正文

一. 栈

栈(stack),有些地方称为堆栈,是一种容器,可存入数据元素、访问元素、删除元素,它的特点在于只能允许在容器的一端(称为栈顶端指标,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算。没有了位置概念,保证任何时候可以访问、删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序。

由于栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。
Python数据结构与算法(五)----- 栈、队列和排序

1. 栈结构实现

栈可以用顺序表实现,也可以用链表实现。

2. 栈的操作

Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数

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

    def push(self,item):
        '''添加一个新的元素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 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())

二. 队列

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

队列是一种先进先出的(First In First Out)的线性表,简称FIFO。允许插入的一端为队尾,允许删除的一端为队头。队列不允许在中间部位进行操作!假设队列是q=(a1,a2,……,an),那么a1就是队头元素,而an是队尾元素。这样我们就可以删除时,总是从a1开始,而插入时,总是在队列最后。这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后来的当然排在队伍最后。
Python数据结构与算法(五)----- 栈、队列和排序

1. 队列的实现

同栈一样,队列也可以用顺序表或者链表实现。

2. 操作

Queue() 创建一个空的队列
enqueue(item) 往队列中添加一个item元素
dequeue() 从队列头部删除一个元素
is_empty() 判断一个队列是否为空
size() 返回队列的大小

class Queue(object):
    '''创建一个空的队列'''
    def __init__(self):
        self.__list = []

    def enqueue(self,item):
        '''往队列中添加一个item元素'''
        self.__list.append(item)

    def dequeue(self):
        '''从队列头部删除一个元素'''
        return self.__list.pop(0)

    def is_empty(self):
        '''判断一个队列是否为空'''
        return self.__list ==[]

    def size(self):
        '''返回队列的大小'''
        return len(self.__list)

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

3. 双端队列

双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

Python数据结构与算法(五)----- 栈、队列和排序

class Deque(object):
    '''双端队列'''

    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):
        '''判断一个队列是否为空'''
        return self.__list == []

    def size(self):
        '''返回队列的大小'''
        return len(self.__list)

三. 排序与搜索

排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。

排序算法的稳定性

稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。
不稳定排序算法可能会在相等的键值中改变纪录的相对次序,但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较,如此在其他方面相同键值的两个对象间之比较,(比如上面的比较中加入第二个标准:第二个键值的大小)就会被决定使用在原先数据次序中的条目,当作一个同分决赛。然而,要记住这种次序通常牵涉到额外的空间负担。

1. 冒泡排序

冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下:

比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

def bubble_sort(alist):
    '''冒泡排序'''
    n = len(alist)
    for j in range(n-1):
    count = 0
        for i in range(0, n-1-j):
            # 班长从头走到尾
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                count +=1
            ##优化时间复杂度
            if 0 == count:
            return 

if __name__ == '__main__':
    li = [54,26,93,17,77,31,44,55,20]
    print(li)
    bubble_sort(li)
    print(li)

时间复杂度
最优时间复杂度:O(n) (表示遍历一次发现没有任何可以交换的元素,排序结束。)
最坏时间复杂度:O(n2)
稳定性:稳定

3. 选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

def select_sort(alist):
    '''选择排序'''
    n = len(alist)
    for j in range(0,n-1): #j:0~n-2
        min_index = j
        for i in range(j + 1, n):
            if alist[min_index] > alist[i]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]

if __name__ == '__main__':
    li = [54,26,93,17,77,31,44,55,20]
    print(li)
    select_sort(li)
    print(li)

时间复杂度
最优时间复杂度:O(n2)
最坏时间复杂度:O(n2)
稳定性:不稳定(考虑升序每次选择最大的情况)

4. 插入排序

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

ef insert_sort(alist):
    '''插入排序'''
    n = len(alist)
    # 从右边的无序序列中取出多少个元素执行
    for j in range(1,n):
        # i 代表内层循环起始值
        i = j
        # 执行从右边的无序序列中取出第一个元素,即i位置的元素,然后将其插入到前面的正确位置中
        while i > 0:
            if alist[i] < alist[i - 1]:
                alist[i], alist[i - 1] = alist[i - 1], alist[i]
                i -= 1
            else:
                break

if __name__ == '__main__':
    li = [54,26,93,17,77,31,44,55,20]
    print(li)
    insert_sort(li)
    print(li)

时间复杂度
最优时间复杂度:O(n) (升序排列,序列已经处于升序状态)
最坏时间复杂度:O(n2)
稳定性:稳定

未经允许不得转载:作者:756-周同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法(五)—– 栈、队列和排序》 发布于2020-06-20

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录