1. 首页
  2. 数据结构

一本正经的聊数据结构(3):栈和队列

一本正经的聊数据结构(3):栈和队列

前文传送门:

「一本正经的聊数据结构(1):时间复杂度」

「一本正经的聊数据结构(2):数组与向量」

引言

前一篇内容我们介绍了数组和向量,虽然说向量是数组的一个升级版,但是在另一个维度上,他们都属于线性结构。

那么什么是线性结构呢?

线性结构是一个有序数据元素的集合。常用的线性结构有:线性表,栈,队列,双队列,数组,串。

线性结构是最常用的数据结构,它最大的特点是数据元素之间存在一对一的线性关系。

线性结构拥有两种不同的存储结构,即顺序存储结构和链式存储结构。

顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的。

链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。

线性结构中存在两种操作受限的使用场景,就是我们本文要介绍的栈和队列。

至于为什么说栈和队列是受限的线型结构,我们下面细聊。

栈是一种比较奇葩的数据结构,栈的结构是支持对象的插入和删除操作,但是,栈操作的范围仅限于栈的某一特定端,就是下面这样的。

一本正经的聊数据结构(3):栈和队列

栈遵循先进后出( last-in-first-out, LIFO )的规律,这是重点。

栈一般使用两种方式来实现:

  1. 顺序表:采用顺序存储结构可以模拟栈存储数据的特点,从而实现栈存储结构。
  2. 链表:采用链式存储结构实现栈结构。

注意,这两种实现方式的区别,仅限于数据元素在实际物理空间上存放的相对位置,顺序栈底层采用的是数组,链栈底层采用的是链表。

栈结构我们还是会经常用到,一个非常经典的场景就是在浏览器的后退功能中。

例如我们每次打开一个页面,浏览器都会把这个页面放入栈中,当我们点击后退按钮的时候,在从栈中将这个页面取出来。

顺序栈

顺序栈,是用顺序表实现栈存储结构。

栈存储结构操作数据元素必须遵守 「先进后出 LIFO 」 的原则。

顺序表的底层是使用数组来实现的,简单理解可以直接理解成数组。

只是栈结构对数据的存取过程有特殊的限制,而数组是没有的。

链栈

链栈,是用链表实现栈存储结构。

链表这个结构在前面没聊过,简单画个图大家理解下:

一本正经的聊数据结构(3):栈和队列

链表的结构相比较数组而言就稍微有些复杂了,链表的每个节点由两部分组成,一个是存放数据的,叫数据域,另一个是存放指针的,叫指针域。

一本正经的聊数据结构(3):栈和队列

数组在内存中是连续的,所以我们可以轻松的知道数组的每一个元素的位置,而链表在内存中是分散的,我们需要一个指针来指明下一个元素在哪里。

一本正经的聊数据结构(3):栈和队列

这里介绍的其实是最简单的一种链表,叫单链表,顾名思义,除了单链表之外还有双链表,这个我们有机会后面再聊。

那么链栈是将链表的头部作为栈顶,尾部作为栈底。

将链表头部作为栈顶的一端,可以避免在实现数据 「入栈」 和 「出栈」 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶,意味着:

  • 在实现数据"入栈"操作时,需要将数据从链表的头部插入。
  • 在实现数据"出栈"操作时,需要删除链表头部的首元节点。

因此,链栈实际上就是一个只能采用头插法插入或删除数据的链表。

Python 实现栈

在 Python 中,栈并不是一个基础数据结构,不过我们可以通过代码来简单的实现它。

因为栈是可以通过两种方式来实现,一种是顺序表,另一种是链表:

首先是最简单的通过顺序表来实现栈,这里使用的是 Python 中的 list 列表:

class Stack(object):

    def __init__(self):
        '''
        创建空列表实现栈
        '''
        self.__list = []

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

    def push(self,item):
        '''
        压栈,添加元素
        :param item:
        :return:
        '''
        self.__list.append(item)

    def pop(self):
        '''
        弹出栈,将元素取出
        :return:
        '''
        if self.is_empty():
            return
        else:
            return self.__list.pop()

如果不想使用顺序表来实现,还可以使用链表,这里使用的是单链表,链表的结构需要先提前定义:

class Node(object):
    '''
    节点实现
    '''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class Stack(object):
    def __init__(self):
        '''
        初始化链表头
        '''
        self.__head = None

    def is_empty(self):
        return self.__head is None

    def push(self, item):
        '''
        压栈
        :param item:
        :return:
        '''
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def pop(self):
        '''
        弹出栈
        :return:
        '''
        if self.is_empty():
            return
        else:
            p = self.__head
            self.__head = p.next
            return p.elem

在链表的实现中,我这里先定义了链表的数据结构,然后才定义了栈。

上面两段代码都非常简单,只实现了最简单的两个功能,入栈和出栈,感兴趣的同学可以自己动手实现下。

队列

与栈一样,队列( queue) 也是存放数据对象的一种容器,其中的数据对象也按线性的逻辑次序排列。

队列和栈不一样的地方在于栈是先进后出,而队列是先进先出( first-in-first-out, FIFO )。

一本正经的聊数据结构(3):栈和队列

同栈一样的是队列也有两种实现方式:

  • 顺序队列:在顺序表的基础上实现的队列结构。
  • 链队列:在链表的基础上实现的队列结构。

Python 中的 Queue

在 Python 的标准库中,Python 为我们提供了线程安全的队列 Queue (总算不用我再自己写个队列了),使用方法异常简单:

先进先出队列 (FIFO) :

import queue

q1 = queue.Queue(maxsize=5)

for i in range(5):
    q1.put(i)

while not q1.empty():
    print('q1:',q1.get())

# 结果输出
q1: 0
q1: 1
q1: 2
q1: 3
q1: 4

Queue 这个标准库中,还为我们提供了 LIFO 队列,即先进后出队列,和我们前面介绍的栈非常类似,翻了下源码,看到是使用 list 实现的,和我们上面的实现基本一致,使用方式如下:

import queue

q2 = queue.LifoQueue(maxsize=5)

for i in range(5):
    q2.put(i)

while not q2.empty():
    print('q2:',q2.get())

# 结果输出
q2: 4
q2: 3
q2: 2
q2: 1
q2: 0

本篇内容就这样了,涉及到的代码肯定会上传代码仓库,有兴趣的同学可以去翻翻看。

示例代码

示例代码-Github

示例代码-Gitee

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code