基础数据结构（基础数据结构— 栈）

基础数据结构

栈（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://cnblogs.com/guokaifeng/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。