# 基础数据结构 例：栈、队列、链表、数据、字典、树、等【玩转腾讯云】

### 栈 stack

Python实现

```# 栈的顺序表实现

class Stack(object):
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

def push(self, item):
return self.items.append(item)

def pop(self):
return self.items.pop()

def top(self):
return self.items[len(self.items)-1]

def size(self):
return len(self.items)

if __name__ == '__main__':
stack = Stack()
stack.push("Hello")
stack.push("World")
stack.push("!")
print(stack.size())
print(stack.top())
print(stack.pop())
print(stack.pop())
print(stack.pop())

# 结果
3
!
!
World
Hello```
```# 栈的链接表实现

class SingleNode(object):
def __init__(self, item):
self.item = item
self.next = None

class Stack(object):
def __init__(self):

def isEmpty(self):

def push(self, item):
node = SingleNode(item)

def pop(self):
return cur.item

def top(self):

def size(self):
count = 0
while cur != None:
count += 1
cur = cur.next
return count

if __name__ == '__main__':
stack = Stack()
stack.push("Hello")
stack.push("World")
stack.push("!")
print(stack.size())
print(stack.top())
print(stack.pop())
print(stack.pop())
print(stack.pop())

# 结果
3
!
!
World
Hello ```

### 队列

```class Queue:
"""

"""

def __init__(self):
"""

"""
self.__queue = []

def first(self):
"""

:return:如果队列为空，则返回None，否则返回第一个元素
"""
return None if self.isEmpty() else self.__queue[0]

def enqueue(self, obj):
"""

:param obj:要加入队列的对象
"""
self.__queue.append(obj)

def dequeue(self):
"""

:return:如果队列为空，则返回None，否则返回dequeued元素
"""
return None if self.isEmpty() else self.__queue.pop(0)

def clear(self):
"""

"""
self.__queue.clear()

def isEmpty(self):
"""

"""
return self.length() == 0

def length(self):
"""

"""
return len(self.__queue)```

```class PriorQueue:
"""

"""

def __init__(self, objs=[]):
"""

:参数objs:对象列表初始化
"""
self.__prior_queue = list(objs)
# 排序从最大值到最小值，最小值具有最高的优先级
# 使得“dequeue”的效率为O(1)
self.__prior_queue.sort(reverse=True)

def first(self):
"""

:return:如果优先队列为空，则返回None，否则返回优先级最高的元素
"""
return None if self.isEmpty() else self.__prior_queue[-1]

def enqueue(self, obj):
"""

:param obj:要加入队列的对象
"""
index = self.length()
while index > 0:
if self.__prior_queue[index - 1] < obj:
index -= 1
else:
break
self.__prior_queue.insert(index, obj)

def dequeue(self):
"""

:return:如果优先队列为空，则返回None，否则返回dequeued元素
"""
return None if self.isEmpty() else self.__prior_queue.pop()

def clear(self):
"""

"""
self.__prior_queue.clear()

def isEmpty(self):
"""

"""
return self.length() == 0

def length(self):
"""

"""
return len(self.__prior_queue)```

```class Loopqueue:
'''

'''
def __init__(self, length):
self.tail = 0
self.maxSize = length
self.cnt = 0
self.__list = [None]*length

def __len__(self):
'''

'''
return self.cnt

def __str__(self):
'''

'''
s = ''
for i in range(self.cnt):
index = (i + self.head) % self.maxSize
s += str(self.__list[index])+' '
return s

def isEmpty(self):
'''

'''
return self.cnt == 0

def isFull(self):
'''

'''
return self.cnt == self.maxSize

def push(self, data):
'''

'''
if self.isFull():
return False
if self.isEmpty():
self.__list[0] = data
self.tail = 0
self.cnt = 1
return True
self.tail = (self.tail+1)%self.maxSize
self.cnt += 1
self.__list[self.tail] = data
return True

def pop(self):
'''

'''
if self.isEmpty():
return False
self.cnt -= 1
return data

def clear(self):
'''

'''
self.tail = 0
self.cnt = 0
return True```

2个附加操作： 支持阻塞的插入方法：队列满时，队列会阻塞插入元素的线程，直到队列不满。 支持阻塞的移除方法：队列空时，获取元素的线程会等待队列变为非空。

```import threading #引入线程 上锁
import time
from collections import deque # 导入队列

class BlockQueue:
def __init__(self, maxsize=0):
'''

'''
self.maxsize = maxsize
self.unfinished = 0

'''

'''
unfinish = self.unfinished - 1
if unfinish <= 0:
if unfinish < 0:
raise ValueError("The number of calls to task_done() is greater than the number of queue elements")
self.unfinished = unfinish

def join(self):
'''

'''
while self.unfinished:

def put(self, item, block=True, timeout=None):
'''
block=True一直阻塞直到有一个空闲的插槽可用，n秒内阻塞，如果在那个时间没有空闲的插槽，则会引发完全的异常。
Block=False如果一个空闲的槽立即可用，则在队列上放置一个条目，否则就会引发完全的异常（在这种情况下，“超时”将被忽略）。

'''
with self.not_full:
if self.maxsize > 0:
if not block:
if self._size() >= self.maxsize:
raise Exception("The BlockQueue is full")
elif timeout is not None:
self.not_full.wait()
elif timeout < 0:
raise Exception("The timeout period cannot be negative")
else:
endtime = time.time() + timeout
while self._size() >= self.maxsize:
remaining = endtime - time.time()
if remaining <= 0.0:
raise Exception("The BlockQueue is full")
self.not_full.wait(remaining)
self.queue.append(item)
self.unfinished += 1
self.not_empty.notify()

def get(self, block=True, timeout=None):
'''

'''
with self.not_empty:
if not block:
if self._size() <= 0:
raise Exception("The queue is empty and you can't call get ()")
elif timeout is None:
while not self._size():
self.not_empty.wait()
elif timeout < 0:
raise ValueError("The timeout cannot be an integer")
else:
endtime = time.time() + timeout
remaining = endtime - time.time()
if remaining <= 0.0:
raise Exception("The BlockQueue is empty")
self.not_empty.wait(remaining)
item = self._get()
self.not_full.notify()
return item```

```class QueueNode():
def __init__(self):
self.data = None
self.next = None
def __init__(self):
tQueueNode = QueueNode()
self.front = tQueueNode
self.rear = tQueueNode
'''判断是否为空'''
def IsEmptyQueue(self):
if self.front == self.rear:
iQueue = True
else:
iQueue = False
return iQueue
'''进队列'''
def EnQueue(self,da):
tQueueNode = QueueNode()
tQueueNode.data = da
self.rear.next = tQueueNode
self.rear = tQueueNode
print("当前进队的元素为：",da)
'''出队列'''
def DeQueue(self):
if self.IsEmptyQueue():
print("队列为空")
return
else:
tQueueNode = self.front.next
self.front.next = tQueueNode.next
if self.rear == tQueueNode:
self.rear = self.front
return tQueueNode.data
if self.IsEmptyQueue():
print("队列为空")
return
else:
return self.front.next.data
def CreateQueueByInput(self):
data = input("请输入元素（回车键确定，#结束）")
while data != "#":
self.EnQueue(data)
data = input("请输入元素（回车键确定，#结束）")
'''遍历顺序队列内的所有元素'''
def QueueTraverse(self):
if self.IsEmptyQueue():
print("队列为空")
return
else:
while self.front != self.rear:
result = self.DeQueue()
print(result,end = ' ')
lq.CreateQueueByInput()
print("队列里元素为：")
lq.QueueTraverse()

# 结果

5 8 9 ```

### 链表

```class Node(object):
"""节点"""

def __init__(self, elem):
self.elem = elem
self.next = None # 初始设置下一节点为空

'''

'''

# 下面创建单链表，并实现其应有的功能

"""单链表"""

def __init__(self, node=None): # 使用一个默认参数，在传入头结点时则接收，在没有传入时，就默认头结点为空

def is_empty(self):
'''链表是否为空'''

def length(self):
'''链表长度'''
# cur游标，用来移动遍历节点
# count记录数量
count = 0
while cur != None:
count += 1
cur = cur.next
return count

def travel(self):
'''遍历整个列表'''
while cur != None:
print(cur.elem, end=' ')
cur = cur.next
print("\n")

'''链表头部添加元素'''
node = Node(item)

def append(self, item):
'''链表尾部添加元素'''
node = Node(item)
# 由于特殊情况当链表为空时没有next，所以在前面要做个判断
if self.is_empty():
else:
while cur.next != None:
cur = cur.next
cur.next = node

def insert(self, pos, item):
'''指定位置添加元素'''
if pos <= 0:
# 如果pos位置在0或者以前，那么都当做头插法来做
elif pos > self.length() - 1:
# 如果pos位置比原链表长，那么都当做尾插法来做
self.append(item)
else:
count = 0
while count < pos - 1:
count += 1
per = per.next
# 当循环退出后，pre指向pos-1位置
node = Node(item)
node.next = per.next
per.next = node

def remove(self, item):
'''删除节点'''
pre = None
while cur != None:
if cur.elem == item:
# 先判断该节点是否是头结点
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next

def search(self, item):
'''查找节点是否存在'''
while not cur:
if cur.elem == item:
return True
else:
cur = cur.next
return False

if __name__ == "__main__":

# node = Node(100) # 先创建一个节点传进去

print(ll.is_empty())
print(ll.length())

ll.append(3)
ll.insert(-3, 110)
ll.insert(99, 111)
print(ll.is_empty())
print(ll.length())
ll.travel()
ll.remove(111)
ll.travel()```

```class Node(object):
def __init__(self,val,p=0):
self.data = val
self.next = p
self.prev = p

def __init__(self):

def __getitem__(self, key):

if self.is_empty():
return

elif key <0 or key > self.getlength():
print 'the given key is error'
return

else:
return self.getitem(key)

def __setitem__(self, key, value):

if self.is_empty():
return

elif key <0 or key > self.getlength():
print 'the given key is error'
return

else:
self.delete(key)
return self.insert(key)

def initlist(self,data):

for i in data[1:]:
node = Node(i)
p.next = node
node.prev = p
p = p.next

def getlength(self):

length = 0
while p!=0:
length+=1
p = p.next

return length

def is_empty(self):

if self.getlength() ==0:
return True
else:
return False

def clear(self):

def append(self,item):

q = Node(item)
else:
while p.next!=0:
p = p.next
p.next = q
q.prev = p

def getitem(self,index):

if self.is_empty():
return
j = 0

while p.next!=0 and j <index:
p = p.next
j+=1

if j ==index:
return p.data

else:

print 'target is not exist!'

def insert(self,index,item):

if self.is_empty() or index<0 or index >self.getlength():
return

if index ==0:

j = 0
while p.next!=0 and j<index:
post = p
p = p.next
j+=1

if index ==j:
q = Node(item,p)
post.next = q
q.prev = post
q.next = p
p.prev = q

def delete(self,index):

if self.is_empty() or index<0 or index >self.getlength():
return

if index ==0:

j = 0
while p.next!=0 and j<index:
post = p
p = p.next
j+=1

if index ==j:
post.next = p.next
p.next.prev = post

def index(self,value):

if self.is_empty():
return

i = 0
while p.next!=0 and not p.data ==value:
p = p.next
i+=1

if p.data == value:
return i
else:
return -1

l.initlist([1,2,3,4,5])
print l.getitem(4)
l.append(6)
print l.getitem(5)

l.insert(4,40)
print l.getitem(3)
print l.getitem(4)
print l.getitem(5)

l.delete(5)
print l.getitem(5)

l.index(5)

# 结果
5
6
4
40
5
6```

```class ListNode:
def __init__(self, x):
self.val = x
self.next = None

# 定义反转的初始状态
pre = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp

if __name__ == '__main__':
p1 = ListNode(2) # 建立链表1->2->3->4->None;
p2 = ListNode(3)
p3 = ListNode(4)
p1.next = p2
p2.next = p3
p = reverse(head) # 输出链表 4->3->2->1->None
while p:
print(p.val)
p = p.next```

```class ListNode:
def __init__(self, x):
self.val = x
self.next = None

return
else:

if __name__ == '__main__':
p1 = ListNode(2) # 建立链表1->2->3->4->None
p2 = ListNode(3)
p3 = ListNode(4)
p1.next = p2
p2.next = p3
while p:
print(p.val)
p = p.next```

### 数组

Python 没有内置对数组的支持，但可以使用 Python 列表代替。

### 字典实现原理 NSDictionary

Python 中 dict 对象是表明了其是一个原始的Python数据类型，按照键值对的方式存储，其中文名字翻译为字典，顾名思义其通过键名查找对应的值会有很高的效率，时间复杂度在常数级别O(1)

dict底层实现 在Python中，字典是通过 哈希表 实现的。也就是说，字典是一个数组，而数组的索引是键经过哈希函数处理后得到的。

```>>> map(hash, (0, 1, 2, 3))

[0, 1, 2, 3]

>>> map(hash, ("namea", "nameb", "namec", "named"))

[-1658398457, -1658398460, -1658398459, -1658398462] ```

1.根据 key 计算出它的哈希值 h。

2.假设箱子的个数为 n，那么这个键值对应该放在第 (h % n) 个箱子中。

3.如果该箱子中已经有了键值对，就使用开放寻址法或者拉链法解决冲突。

1.如果哈希表中本来箱子就比较多，扩容时需要重新哈希并移动数据，性能影响较大。

2.如果哈希函数设计不合理，哈希表在极端情况下会变成线性表，性能极低。

Python中所有不可变的内置类型都是可哈希的。 可变类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。

### 树

(1)空二叉树——如图(a)； (2)只有一个根结点的二叉树——如图(b)； (3)只有左子树——如图(1)； (4)只有右子树——如图(3)； (5)完全二叉树——如图(3)。

hash树 哈希树（或哈希特里）是一种持久性数据结构，可用于实现集合和映射，旨在替换纯函数式编程中的哈希表。 在其基本形式中，哈希树在trie中存储其键的哈希值（被视为位串），其中实际键和（可选）值存储在trie的“最终”节点中

### B-tree/B+tree

Btree Btree是一种多路自平衡搜索树，它类似普通的二叉树，但是Btree允许每个节点有更多的子节点。Btree示意图如下：

B+tree

B+树是B树的变体，也是一种多路平衡查找树，B+树的示意图为：

0 条评论

• ### 数据结构基础知识: 表 栈 队列 树 散列 堆

表，栈和队列是计算机科学中最简单和最基本的三种底层数据结构。事实上，每一个有意义的程序都将明晰地至少使用一种这样的数据结构，而栈则在程序中总是要间接地用到，不管...

• ### 打牢算法基础，从动手出发！

大家好，我是光城。算法在计算机领域的重要性，就不用我多说了，每个人都想要学算法，打牢算法基础，可是不知道如何做，今天我来推荐一波学习思路。

• ### 重温四大基础数据结构：数组、链表、队列和栈

数组、链表、队列、栈，是数据结构中最基础的四大结构，数组和链表更是基础中的基础，后续所有复杂的数据结构都是在它们的基础上演变而来的。

• ### 【阅读清单】系列文章清单列表（一）

Centreon+Nagios实战 https://cloud.tencent.com/developer/inventory/272

• ### 经典数据结构实现与分析：顺序表，单链表，栈，队列，树结构，图结构；

本博客在在这里重新总结了一下，当前常用的经典数据结构；这里只针对链表，顺序表，简单树和图进行总结；具体实现请参考：https://github.com/yaow...

• ### 喜讯！腾讯多个智慧文旅案例入选2020年文化和旅游信息化发展典型案例

? 近年来，5G、大数据、区块链、人工智能等信息技术与各行各业的融合发展成为时代新趋势，文旅产业表现亮眼，出现了云旅游、云直播、云看展等新业态，尤其在疫情期间...

• ### 从Java程序员到架构师，从工程师到技术专家，迷茫之路

怎样学习才能从一名Java初级程序员成长为一名合格的架构师，或者说一名合格的架构师应该有怎样的技术知识体系，这是不仅一个刚刚踏入职场的初级程序员也是工作三五年之...

• ### 后台开发：校招中遇到的问题总结

楼主的秋招也算是今天开始结束了，期间也迷茫过，最终拿到了百度sp、腾讯sp、360sp、京东、招行信用卡中心、华为、中兴、陌陌sp 等的offer（具体的面经前...

• ### 腾讯课堂 IMWeb 七天前端求职提升营 Day 1

本次的系列博文主要是针对 腾讯课堂七天前端求职提升营 课程中，所推送的面试题目及编程练习的一次汇总，期间还包括三次直播课的分享，均由腾讯导师给大家讲解，该系列博...

• ### 2018技术精华汇集！聚焦运维与数据库年度热点

历经一年时间，Gdevops全球敏捷运维峰会再次从成都、上海、北京成功巡回至广州，即将于11月30日举办2018年度收官盛会！

• ### 新疆学子的腾讯后台开发的面经

4月26日收到了腾讯的offer,终于安心了,很多小伙伴们要我写面经介绍下,其实自己能拿到腾讯的offer 99%是运气~, 这里就介绍下自己的面经跟总结自己的...

• ### 夯实安全“三大体系”建设，腾讯云打造安全可靠的云上高速公路

产业互联网时代，5G、AI、云计算等新一代信息技术与应用不断深化，加速了各行业数字化和产业升级的进程。在企业上云、资产数字化的背景下，安全不只是企业经营的底线，...

• ### 【玩转腾讯云】征文活动获奖名单公布

由云+社区联合腾讯云免费体验馆及各产品团队举办【玩转腾讯云】征文活动，吸引入驻作者积极参加，非常感谢各位作者的参与。经过评委老师从产品创新性、实用性、可借鉴性、...

• ### 腾讯安全打造真实云端攻防战 GeekPwn 云安全挑战赛0ops摘冠

由腾讯安全云鼎实验室联合GeekPwn发起的 全球首个基于真实通用云环境的云安全挑战赛 今天下午正式结束。 ? 来自紫荆花、复旦白泽、0ops、AAA、Nu1...

• ### 《北京大学、腾讯联合在Coursera开设课程》分享有礼中奖信息

之前推送的《教授们说了，我们的目标是培养中国最优秀的程序员》分享有礼活动，中奖名单如下，恭喜幸运参与者！我们将按照问卷中填写的信息尽快邮寄奖品！ 洪瑞琦 梓鑫 ...

• ### 腾讯物联网操作系统正式开源，最小体积仅1.8 KB

? 9月18日，腾讯宣布将开源自主研发的轻量级物联网实时操作系统TencentOS tiny。相比市场上其它系统，腾讯TencentOS tiny在资源占用、...

• ### 【植树节专题】回顾TcaplusDB的十年发展史

植下一棵树，收获万点绿，种下一棵树，也就代表着种下了一份希望，这棵树在会抽枝发叶，开花结果，这些变化都是值得期待的。

• ### 腾讯发布千帆区块链云市场，首批17家优质区块链企业入驻

近日，腾讯云区块链联合腾讯千帆云市场、腾讯区块链加速器正式发布腾讯千帆区块链云市场，将以链动产业、合作共赢为原则，汇聚生态优质区块链解决方案，促进区块链在产业数...

• ### Java的8道数据结构面试题（附答案），你会几道？

40多年后，这个等式仍被奉为真理。这就是为什么在面试过程中，需要考察软件工程师对数据结构的理解。

IT行业Python开发