Python 数据结构和算法简介

数据结构是一种组织和存储数据的方式，以便可以有效地访问和使用数据，而算法是用于解决问题或完成给定任务的明确定义的指令序列。

本文详细介绍了最常用的数据结构Stack和队列以及它们在python中的实现。

堆

堆栈是计算机科学中最早定义的数据结构之一，它是一种线性数据结构，使用 LIFO（后进先出）原则存储项目进行插入和删除。

为了更清楚地理解“书堆”，想象一下一堆书。你把一本书放在书堆的顶部，所以第一个被拿起的书将是最后放进书堆的书。

栈有两种操作：

• 推送 - 将项目添加到堆栈顶部。

• 弹出 - 从堆栈中移除一个项目。

我们为什么要使用堆栈？

• 堆栈易于学习和实现。
• 堆栈允许我们按顺序存储和检索数据。
• 堆栈的插入和删除操作需要 O(1) 时间。

堆栈的真实世界用例。

• Web 浏览器使用堆栈来跟踪你之前访问过的 URL。当你访问一个新页面时，它会被添加到堆栈中。点击“后退”按钮后，堆栈会被弹出，并访问之前的 URL。
• 文本编辑器中的撤消机制使用堆栈来保存所有更改。
• 实现其他数据结构 - 使用堆栈来实现图形和树中的搜索。
• 编译器和解析器使用堆栈

Stack数据结构的更多应用

堆栈方法

堆栈操作通过以下方法实现：

• stack.IsEmpty- 如果堆栈为空，则返回 True，否则返回 false。
• stack.length()-返回堆栈的长度。
• stack.top()-返回指向堆栈顶部元素的指针/引用。
• stack.push(x)-将元素 x 插入到堆栈顶部。
• stack.pop()-删除堆栈顶部元素并返回它。

Python 中的堆栈实现。

在 python 中，我们可以使用以下方式实现堆栈；

1. 使用内置的 List 数据结构。
2. 使用双端队列库，它可以在一个对象中有效地提供堆栈操作。

使用列表进行堆栈。

要使用列表实现堆栈，需要使用append和pop
方法。python 中的 append() 方法将单个项目添加到现有列表中，
pop() 删除指定位置的元素

例子

s = []

s.append('stack')
s.append('queue')
s.append('list')
s.append('tuple')

print(s)

输出

['stack', 'queue', 'list', 'tuple']

使用 pop

s.pop()
>>tuple
s.pop()
>>list
s.pop()
>>queue
s.pop()
>>stack
s.pop()
>>IndexError: pop from empty list

检查此实现

了解有关堆栈的更多信息

队列

与堆栈类似，队列是一种线性数据结构。
队列使用 FIFO（先进先出）原则存储元素，并进行插入和删除。

Python 中与队列相关的操作。

• 入队：将元素添加到队列末尾。当队列达到其总容量时，即达到溢出状态。

  • 出队：从队列中移除一个元素。当队列为空时，即达到下溢状态。
  • 前面：返回队列中的第一个项目。
  • 罕见：返回队列中的最后一项。

队列的应用

队列在以下场景中很有用；

• 处理实时系统中的中断——中断按照到达的顺序进行处理。
• 处理网站流量。
• 在单个共享资源（如打印机或 CPU 任务调度）上提供请求。

队列数据结构的应用

如何在 Python 中实现队列

在 Python 中，实现队列的方法有很多种。
常见的方法有：

• 使用内置的 List 数据结构。
• 使用 collections.deque 库

使用列表在 Python 中实现队列

列表的 append() 和 pop() 方法用于在队列中插入和删除元素。

# Initialize a queue

queue = []

# Adding elements to the queue

queue.append('Python')

queue.append('Javascript')

queue.append('Typescript')
print(queue)

输出

['Python', 'Javascript', 'Typescript']

# Removing elements from the queue



print(queue.pop(0))

print(queue.pop(0))

print(queue.pop(0))


print(queue)

输出

Python
Javascript
Typescript
[]

使用 collections.deque 在 Python 中实现队列

Python collections 模块中的 deque 类也可以用来实现队列。deque 类提供了更快的入队和出队操作，因此效率更高。

from collections import deque

queue = deque()

queue.append('Black')

queue.append('White')

queue.append('Orange')

print(queue)

输出

deque(['Black', 'White', 'Orange'])

我希望您喜欢阅读这篇文章，就像我喜欢写这篇文章一样，以下是我使用的有用资源和参考资料。

完整源代码请见此处

在 Python 中使用队列数据结构

如何在 Python 中实现队列