您现在的位置是：首页 > Python

当前栏目

数据结构、python实现

Python 存储队列数组数据结构队列

2023-03-02 11:48:26 时间

1.数据结构：线性表和链表、堆栈和队列、树和二叉树、图、字典和集合、B树、哈希表

线性表包括数组和链表

线性表是最常用且最简单的一种数据结构，它是n个数据元素的有限序列。

实现线性表的方式一般有两种，一种是使用数组存储线性表的元素，即用一组连续的存储单元依次存储线性表的数据元素。另一种是使用链表存储线性表的元素，即用一组任意的存储单元存储线性表的数据元素（存储单元可以是连续的，也可以是不连续的）。

数组是一种大小固定的数据结构，对线性表的所有操作都可以通过数组来实现。虽然数组一旦创建之后，它的大小就无法改变了，但是当数组不能再存储线性表中的新元素时，我们可以创建一个新的大的数组来替换当前数组。这样就可以使用数组实现动态的数据结构。

链表

1）含义：链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)

2）特点：使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大

3）操作：

is\_empty() 链表是否为空  
length() 链表长度  
travel() 遍历链表  
add(item) 链表头部添加  
append(item) 链表尾部添加  
insert(pos, item) 指定位置添加  
remove(item) 删除节点  
search(item) 查找节点是否存在  
\# -\*- coding: utf-8 -\*-

# -*- coding: utf-8 -*-
     
    class Node(object):
        """双向链表节点"""
        def __init__(self, item):
            self.item = item
            self.next = None
            self.prev = None
     
    class DLinkList(object):
        """双向链表"""
        def __init__(self):
            self._head = None
     
        def is_empty(self):
            """判断链表是否为空"""
            return self._head == None
     
        def length(self):
            """返回链表的长度"""
            cur = self._head
            count = 0
            while cur != None:
                count += 1
                cur = cur.next
            return count
     
        def travel(self):
            """遍历链表"""
            cur = self._head
            while cur != None:
                print cur.item
                cur = cur.next
     
        def add(self, item):
            """头部插入元素"""
            node = Node(item)
            if self.is_empty():
                # 如果是空链表，将_head指向node
                self._head = node
            else:
                # 将node的next指向_head的头节点
                node.next = self._head
                # 将_head的头节点的prev指向node
                self._head.prev = node
                # 将_head 指向node
                self._head = node
     
        def append(self, item):
            """尾部插入元素"""
            node = Node(item)
            if self.is_empty():
                # 如果是空链表，将_head指向node
                self._head = node
            else:
                # 移动到链表尾部
                cur = self._head
                while cur.next != None:
                    cur = cur.next
                # 将尾节点cur的next指向node
                cur.next = node
                # 将node的prev指向cur
                node.prev = cur
     
        def search(self, item):
            """查找元素是否存在"""
            cur = self._head
            while cur != None:
                if cur.item == item:
                    return True
                cur = cur.next
            return False
     
        def insert(self, pos, item):
            """在指定位置添加节点"""
            if pos <= 0:
                self.add(item)
            elif pos > (self.length()-1):
                self.append(item)
            else:
                node = Node(item)
                cur = self._head
                count = 0
                # 移动到指定位置的前一个位置
                while count < (pos-1):
                    count += 1
                    cur = cur.next
                # 将node的prev指向cur
                node.prev = cur
                # 将node的next指向cur的下一个节点
                node.next = cur.next
                # 将cur的下一个节点的prev指向node
                cur.next.prev = node
                # 将cur的next指向node
                cur.next = node
     
        def remove(self, item):
            """删除元素"""
            if self.is_empty():
                return
            else:
                cur = self._head
                if cur.item == item:
                    # 如果首节点的元素即是要删除的元素
                    if cur.next == None:
                        # 如果链表只有这一个节点
                        self._head = None
                    else:
                        # 将第二个节点的prev设置为None
                        cur.next.prev = None
                        # 将_head指向第二个节点
                        self._head = cur.next
                    return
                while cur != None:
                    if cur.item == item:
                        # 将cur的前一个节点的next指向cur的后一个节点
                        cur.prev.next = cur.next
                        # 将cur的后一个节点的prev指向cur的前一个节点
                        cur.next.prev = cur.prev
                        break
                    cur = cur.next
     
    ll = DLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print '----------------1-----------------'
    print "length:",ll.length()
    print '----------------2-----------------'
    ll.travel()
    print '----------------3-----------------'
    print ll.search(3)
    print ll.search(4)
    print '----------------4-----------------'
    ll.remove(1)
    print "length:",ll.length()
    print '----------------5-----------------'
    ll.travel()

4）输出：

![70][]

堆栈

1.含义：堆栈（英语：stack），也可直接称栈，在计算机科学中，是一种特殊的串列形式的数据结构，它的特殊之处在于只能允许在链接串列或阵列的一端（称为堆叠顶端指标，英语：top）进行加入资料（英语：push）和输出资料（英语：pop）的运算。另外堆叠也可以用一维阵列或连结串列的形式来完成。堆叠的另外一个相对的操作方式称为伫列；由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作

2.特点：先入后出，后入先出；除头尾节点之外，每个元素有一个前驱，一个后继

3.操作：

is\_empty：判断栈是否为空  
peek：返回栈顶元素  
size：返回栈的大小  
push：把新的元素堆进栈里面  
pop：把栈顶元素丢出去  
\# -\*- coding: utf-8 -\*-

class Stack(object):
        __slots__ = ('__items')   #限定Stack类的成员只有__items(类成员)
     
        # 初始化栈为空列表
        def __init__(self):
            self.__items = []
     
        # 判断栈是否为空，返回布尔值
        def is_empty(self):
            return self.__items == []
     
        # 返回栈顶元素
        def peek(self):
            return self.__items[len(self.__items) - 1]
     
        # 返回栈的大小
        def size(self):
            return len(self.__items)
     
        # 把新的元素堆进栈里面（程序员喜欢把这个过程叫做压栈，入栈，进栈……）
        def push(self, item):
            self.__items.append(item)
     
        # 把栈顶元素丢出去（程序员喜欢把这个过程叫做出栈……）
        def pop(self):
            return self.__items.pop()
     
    # 初始化一个栈对象
    my_stack = Stack()
    # 把'h'丢进栈里
    my_stack.push('h')
    # 把'a'丢进栈里
    my_stack.push('a')
    # 看一下栈的大小（有几个元素）
    print my_stack.size()
    # 打印栈顶元素
    print my_stack.peek()
    # 把栈顶元素丢出去，并打印出来
    print my_stack.pop()
    # 再看一下栈顶元素是谁
    print my_stack.peek()
    # 这个时候栈的大小是多少？
    print my_stack.size()
    # 再丢一个栈顶元素
    print my_stack.pop()
    # 看一下栈的大小
    print my_stack.size
    # 栈是不是空了？
    print my_stack.is_empty()

4）输出：

![70 1][]

队列

1）含义：和堆栈类似，唯一的区别是队列只能在队头进行出队操作，所以队列是是先进先出（FIFO, First-In-First-Out）的线性表

2）特点：先入先出,后入后出；除尾节点外,每个节点有一个后继；（可选）除头节点外,每个节点有一个前驱

3）操作：

inqueue()：一次入队一个  
many\_in\_queue()：一次入队多个  
outqueue()：出队  
show()：显示队列  
head()：队列的头部  
tail()：队列的尾部  
isempty()：判断队列是否为空  
length()：队列长度  
\# -\*- coding: utf-8 -\*-

class queue(object):
        def __init__(self):
            self.queue = []
     
        # 一次入队一个
        def inqueue(self,item):
            self.queue.append(item)
     
        # 一次入队多个
        def many_in_queue(self,*args):
            self.queue.extend(args)
     
        # 出队
        def outqueue(self):
            if not self.queue == []:
                self.queue.pop(0)
            else:
                return None
     
        # 显示队列
        def show(self):
            for i in self.queue:
                print i
     
        # 队列的头部
        def head(self):
            if not self.queue == [] :
                print self.queue[0]
            else :
                return None
     
        # 队列的尾部
        def tail(self):
            if not self.queue == []:
                print self.queue[-1]
            else :
                return None
     
        # 是否为空
        def isempty(self):
            return self.queue == []
     
        # 长度
        def length(self):
            print len(self.queue)
     
    q1 = queue()
    q1.inqueue(1)
    q1.show()
    print '----------1-----------'
    q1.many_in_queue(3,4,5)
    q1.show()
    print '----------1-----------'
    q1.outqueue()
    q1.show()
    print '----------1-----------'
    q1.head()
    print '----------1-----------'
    q1.tail()
    print '----------1-----------'
    q1.length()
    q1.isempty()

4）输出：

![70 2][]

二叉树

1）定义：二叉树是每个结点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空

![70 3][]

2）特点：性质1：二叉树第i层上的结点数目最多为2i-1(i>=1)；性质2：深度为k的二叉树至多有2k-1个结点（k>=1）；性质3：包含n个结点的二叉树的高度至少为(log2n)+1；性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

3）操作

\# -\*- coding: utf-8 -\*-

class Node(object):
        def __init__(self,item):
            self.item = item
            self.child1 = None
            self.child2 = None
     
    class Tree(object):
        def __init__(self):
            self.root = None
     
        def add(self, item):
            node = Node(item)
            if self.root is None:
                self.root = node
            else:
                q = [self.root]
     
                while True:
                    pop_node = q.pop(0)
                    if pop_node.child1 is None:
                        pop_node.child1 = node
                        return
                    elif pop_node.child2 is None:
                        pop_node.child2 = node
                        return
                    else:
                        q.append(pop_node.child1)
                        q.append(pop_node.child2)
     
        def traverse(self):  # 层次遍历
            if self.root is None:
                return None
            q = [self.root]
            res = [self.root.item]
            while q != []:
                pop_node = q.pop(0)
                if pop_node.child1 is not None:
                    q.append(pop_node.child1)
                    res.append(pop_node.child1.item)
     
                if pop_node.child2 is not None:
                    q.append(pop_node.child2)
                    res.append(pop_node.child2.item)
            return res
     
        def preorder(self,root):  # 先序遍历
            if root is None:
                return []
            result = [root.item]
            left_item = self.preorder(root.child1)
            right_item = self.preorder(root.child2)
            return result + left_item + right_item
     
        def inorder(self,root):  # 中序序遍历
            if root is None:
                return []
            result = [root.item]
            left_item = self.inorder(root.child1)
            right_item = self.inorder(root.child2)
            return left_item + result + right_item
     
        def postorder(self,root):  # 后序遍历
            if root is None:
                return []
            result = [root.item]
            left_item = self.postorder(root.child1)
            right_item = self.postorder(root.child2)
            return left_item + right_item + result
     
    t = Tree()
    for i in range(10):
        t.add(i)
    print u'层序遍历:',t.traverse()
    print u'先序遍历:',t.preorder(t.root)
    print u'中序遍历:',t.inorder(t.root)
    print u'后序遍历:',t.postorder(t.root)

4）输出：

![70 4][]

更多数据结构问题，也可以参考[https://www.cnblogs.com/wanghuaijun/p/7302303.html][https_www.cnblogs.com_wanghuaijun_p_7302303.html]的文章。

[70]: /images/20220417/2284009ce4f84420909a5caa446aab1e.png
[70 1]: /images/20220417/f3eba7df6d6a46e3897fa5514366c03d.png
[70 2]: /images/20220417/b6ab79281da94be0ae1566308cb4cc88.png
[70 3]: /images/20220417/a0c62557d294450e9ce56a6471b12bcf.png
[70 4]: /images/20220417/1cbaa40d40034daf83eab6c28f0b4e0d.png
[https_www.cnblogs.com_wanghuaijun_p_7302303.html]: https://www.cnblogs.com/wanghuaijun/p/7302303.html

猜你喜欢

新一代Java程序员必学的Docker容器化技术基础篇
Java定时器演进过程和生产级分布式任务调度ElasticJob代码实战
手写Mybatis和Spring整合简单版示例窥探Spring的强大扩展能力
云原生时代之Kubernetes容器编排初步探索及部署、使用实战-v1.22
走进Spring Boot源码学习之路和浅谈入门v2.5.3
从Redis分布式缓存实战入手到底层原理分析、面面俱到覆盖大厂面试考点
浅谈MySQL数据库面试必要掌握知识点
Apache Kafka分布式流处理平台及大厂面试宝典v3.0.0
Apache RocketMQ分布式消息传递和流数据平台及大厂面试宝典v4.9.2
Netty高性能网络应用框架对标P7面试题分享v4.1.70.Final
企业数据治理落地和同行面试基础
Apache ZooKeeper原理剖析及分布式理论名企高频面试v3.7.0
从ApacheTomcat架构谈面试到源码编译环境v10.0.12
MySQL数据库之大厂面试必备技能v8.0.27
数据安全技术落地经验浅谈和分类分级实施
Redis分布式缓存剖析及大厂面试精髓v6.2.6
Nginx后端开发人员必学神器-并发编程经典之作剖析和名企热点面试v1.21.3
并发编程热身十个性能小面试题
数字化大时代崛起的数据安全能力框架
Kubernetes容器编排探索与实践v1.22.1-上半部分

zl程序教程

当前栏目

数据结构、python实现

相关文章