欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构的栈,队列,双端队列,顺序表,链表,二叉树

程序员文章站 2022-03-26 20:10:04
基础数据结构 栈(stack) 队列 (queue) 双端队列 ( deque ) 顺序表 与 内存 简单了解一下内存 顺序表 顺序表的弊端:顺序表的结构需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁。 链表 (Linked list) 二叉树 二叉树 根节点 叶子节点 ......

基础数据结构

栈(stack)

  栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。
这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,
它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,
它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,
先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。

- 特性:先进后出的数据结构

# 应用:每个 web 浏览器都有一个返回按钮。当你浏览网页时,这些网页被放置在一个栈中(实际是网页的网址)。
你现在查看的网页在顶部,你第一个查看的网页在底部。如果按‘返回’按钮,将按相反的顺序浏览刚才的页面。
# 使用python代码实现一个栈
- stack() 创建一个空的新栈。 它不需要参数,并返回一个空栈。
- push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
- pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
- peek() 从栈返回顶部项,但不会删除它。不需要参数。 不修改栈。
- isempty() 测试栈是否为空。不需要参数,并返回布尔值。
- size() 返回栈中的 item 数量。不需要参数,并返回一个整数。

class stack():
    def __init__(self):
        self.items = []
    def push(self,item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return len(self.items) - 1
    def isempty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    
stack = stack()
stack.push(1)
stack.push(2)
stack.push(3)

print('栈顶元素下标:',stack.peek())
print(stack.isempty())
print('元素个数:',stack.size())
print(stack.pop())
print(stack.pop())
print(stack.pop())

数据结构的栈,队列,双端队列,顺序表,链表,二叉树

队列 (queue)

- 队列:先进先出
- 应用场景:
    - 我们的计算机实验室有 30 台计算机与一台打印机联网。当学生想要打印时,
他们的打印任务与正在等待的所有其他打印任务“一致”。第一个进入的任务是先完成。
如果你是最后一个,你必须等待你前面的所有其他任务打印。
# 使用python代码实现一个队列
- queue() 创建一个空的新队列。 它不需要参数,并返回一个空队列。
- enqueue(item) 将新项添加到队尾。 它需要 item 作为参数,并不返回任何内容。
- dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。
- isempty() 查看队列是否为空。它不需要参数,并返回布尔值。
- size() 返回队列中的项数。它不需要参数,并返回一个整数。

class queue():
    def __init__(self):
        self.items = []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def isempty(self):
        return self.items == []
    def size(self):
        return len(self.items)

q = queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())    
# 面试题
- 烫手的山芋
    - 烫手山芋游戏介绍:6个孩子围城一个圈,排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋,
需要在计时器计时1秒后将山芋传递给下一个孩子,依次类推。规则是,在计时器每计时7秒时,手里有山芋的孩子退出游戏。
该游戏直到剩下一个孩子时结束,最后剩下的孩子获胜。请使用队列实现该游戏策略,排在第几个位置最终会获胜。
# 解题思路
    - 让手里有山芋的孩子永远排在队列的头部
class queue():
    def __init__(self):
        self.items = []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def isempty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    
kids = ['a','b','c','d','e','f']
queue = queue()
for kid in kids:
    queue.enqueue(kid) #a对头f队尾
while queue.size() > 1:
    for i in range(6): #每循环一次,山芋传递一次,手里有山芋的孩子永远在对头位置
        kid = queue.dequeue()
        queue.enqueue(kid)
    queue.dequeue()
print('获胜的选手是:',queue.dequeue())
for a in range(len(kids)):
    if kids[a] == kid:   
        print('排在第:%d会获胜'%a)  
# 执行结果
获胜的选手是: e
排在第:4会获胜

数据结构的栈,队列,双端队列,顺序表,链表,二叉树

# 面试题 使用两个队列实现一个栈
class queue():
    def __init__(self):
        self.items = []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def size(self):
        return len(self.items)
    
alist = [1,2,3,4,5]
q1 = queue()
for i in alist:
    q1.enqueue(i)
q2 = queue()
while q1.size() > 0:
    #将q1中的n-1个值取出放入到q2中
    while q1.size() > 1:
        item = q1.dequeue()
        q2.enqueue(item)
    print(q1.dequeue())

    q1,q2 = q2,q1    

双端队列 ( deque )

同队列相比,有两个头部和尾部。可以在双端进行数据的插入和删除,提供了单数据结构中栈和队列的特性.

# 用python代码实现一个双端队列
- deque() 创建一个空的新 deque。它不需要参数,并返回空的 deque。
- addfront(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。
- addrear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。
- removefront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。
- removerear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。
- isempty() 测试 deque 是否为空。它不需要参数,并返回布尔值。
- size() 返回 deque 中的项数。它不需要参数,并返回一个整数。

class deque():
    def __init__(self):
        self.items = []
    def addfront(self,item):
        self.items.insert(0,item)
    def addrear(self,item):
        self.items.append(item)
    def removefront(self):
        return self.items.pop()
    def removerear(self):
        return self.items.pop(0)
    def isempty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    
q = deque()
q.addfront(1)
q.addfront(2)
q.addfront(3)

print(q.removerear())
print(q.removerear())
print(q.removerear())
- 双端队列应用案例:回文检查
    - 回文是一个字符串,读取首尾相同的字符,例如,radar toot madam。
class deque():
    def __init__(self):
        self.items = []
    def addfront(self,item):
        self.items.insert(0,item)
    def addrear(self,item):
        self.items.append(item)
    def removefront(self):
        return self.items.pop()
    def removerear(self):
        return self.items.pop(0)
    def isempty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    
def ishuiwen(s):
    ex = true
    q = deque()
    for ch in s:
        q.addfront(ch)
    while q.size() > 1:
        if q.removefront() != q.removerear():
            ex = false
            break
    return ex
print(ishuiwen('上海自来水来自海上'))
# 执行结果
true

顺序表 与 内存

  • 简单了解一下内存

- 内存在计算机的作用
    - 用来存储和运算二进制的数据
- 问题:计算机如何计算1+2?
    - 将1和2的二进制类型的数据加载到计算机的内存中,然后使用寄存器进行数值的预算。
- 变量的概念
    - 变量可以理解为某一块内存(实际是引用的某一块内存的地址)
    - 内存空间是有两个默认的属性:
        - 内存空间的大小
            - bit(位):一个bit大小的内存空间只能存放一位二进制的数
            - byte(字节):8bit
            - kb:1024byte
        - 内存空间的地址
            - 使用一个十六进制的数值表示
            - 作用:让cup寻址
                       
- 理解a=10的内存图(引用,指向)
    - 引用:变量==》内存空间的地址
    - a = 10:a变量/引用/内存空间的地址
    - 指向:如果变量或者引用表示的是某一块内存空间地址的话,则该变量或者该引用指向了该块内存
  • 顺序表

- 集合中存储的元素是有顺序的,顺序表的结构可以分为两种形式:单数据类型(np.array数组)和多数据类型(列表,元组)。

- python中的列表和元组就属于多数据类型的顺序表

- 单数据类型顺序表的内存图 (内存连续开辟,每个内存空间大小一致)

数据结构的栈,队列,双端队列,顺序表,链表,二叉树

数据结构的栈,队列,双端队列,顺序表,链表,二叉树

- 多数据类型顺序表的内存图(内存非连续开辟)

数据结构的栈,队列,双端队列,顺序表,链表,二叉树

  • 顺序表的弊端:顺序表的结构需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁。

链表 (linked list)

- 链表(linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据,
而是每一个结点(数据存储单元)里存放下一个结点的信息(即地址)

- 相对于顺序表,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理且进行扩充时不需要进行数据搬迁。

数据结构的栈,队列,双端队列,顺序表,链表,二叉树

- 使用python实现单向链表

. is_empty():链表是否为空

. length():链表长度

. travel():遍历整个链表

. add(item):链表头部添加元素

. append(item):链表尾部添加元素

. insert(pos, item):指定位置添加元素

. remove(item):删除节点

. search(item):查找节点是否存在

# 代码
class node():
    def __init__(self,item):
        self.item = item
        self.next = none
        
class link():
    def __init__(self):
        #构造出一个空链表
        #_head存储的只能是空或者第一个节点的地址
        self._head = none
    #向链表的头部插入一个节点
    def add(self,item):
        #创建一个新的节点
        node = node(item)
        node.next = self._head
        self._head = node
        
    def travel(self):
        #_head在链表创建好之后一定是不可变
        cur = self._head
        while cur:
            print(cur.item)
            cur = cur.next
            
    def isempty(self):
        return self._head == none
    
    def size(self):
        cur = self._head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count
    
    def append(self,item):
        node = node(item)
        #特殊情况
        if self._head == none:
            self._head = node
            return
        
        cur = self._head
        pre = none#pre指向的是cur前一个节点
        while cur:
            pre = cur
            cur = cur.next
        pre.next = node
    
    def search(self,item):
        find = false
        
        cur = self._head
        while cur:
            if cur.item == item:
                find = true
                break
            cur = cur.next
        
        return find
    
    def insert(self,pos,item):
        node = node(item)
        pre = none
        cur = self._head
        for i in range(pos):
            pre = cur
            cur = cur.next
        pre.next = node
        node.next = cur
        
    def remove(self,item):
        cur = self._head
        pre = none
        #删除的是第一个节点
        if cur.item == item:
            self._head = cur.next
            return
        while cur:  
            pre = cur
            cur = cur.next
            if cur.next == none:
                return
            if cur.item == item:
                pre.next = cur.next
                return      
- 如何实现将单链表倒置

# 单链表(插入,删除,遍历)
class node():
   def __init__(self,item):
       self.item = item
       self.next = none
class link():
   def __init__(self):
       self._head = none
   def append(self,item):
       node = node(item)
       if self._head == none:
           self._head = node
           return
       cur = self._head
       pre = none
       
       while cur:
           pre = cur
           cur = cur.next
       pre.next = node
   def travel(self):
       cur = self._head
       while cur:
           print(cur.item)
           cur = cur.next
   def remove(self,item):
       cur = self._head
       pre = none
       #删除的是第一个节点
       if cur.item == item:
           self._head = cur.next
           return
       while cur:
           pre = cur
           cur = cur.next
           if item == cur.item:
               pre.next = cur.next
               return
   
   def reverse(self):
       cur = self._head
       pre = none
       next_node = cur.next
       
       while cur:
           cur.next = pre
           pre = cur
           cur = next_node
           if cur:
               next_node = cur.next
       self._head = pre
   
# 双向链表就是连续开辟三个内存空间,分别存放 数据 上个节点内存地址 下个节点内存地址   

二叉树

  • 二叉树
    • 根节点
    • 叶子节点:
      • 左叶子节点
      • 右叶子节点
    • 树的层级/树的高度
  • 二叉树的遍历
    • 广度优先遍历
      • 一层一层对节点进行遍历
    • 深度优先遍历
      • 前序:根左右
      • 中序:左根右
      • 后序:左右根

数据结构的栈,队列,双端队列,顺序表,链表,二叉树

# 使用python代码实现二叉树
class node():
    def __init__(self,item):
        self.item = item
        self.left = none
        self.right = none    
class tree():
    def __init__(self):
        self.root = none
    def addnode(self,item):
        node = node(item)
        #如果插入第一个节点的情况
        if self.root == none:
            self.root = node
            return
        cur = self.root
        q = [cur] #列表元素是我们进行遍历判断的节点
        while q:
            nd = q.pop(0)
            if nd.left == none:
                nd.left = node
                return
            else:
                q.append(nd.left)
            if nd.right == none:
                nd.right = node
                return
            else:
                q.append(nd.right)
    def travel(self):  #广度优先遍历
        cur = self.root
        q = [cur]
        while q:
            nd = q.pop(0)
            print(nd.item)
            if nd.left:
                q.append(nd.left)
            if nd.right:
                q.append(nd.right)
                
    def forwoar(self,root): #深度优先 前序:根左右
        if root == none:
            return
        print(root.item)
        self.forwoar(root.left)
        self.forwoar(root.right)
    def middle(self,root):  #深度优先 前序:左根右
        if root == none:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
    def back(self,root):   #深度优先 前序:左右根
        if root == none:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)
郭楷丰
出 处:https://www.cnblogs.com/guokaifeng/