博客

python数据结构之栈、队列及双端队列

  • Post category:Python

Python数据结构之栈、队列及双端队列

概述

栈（Stack）、队列（Queue）和双端队列（Deque）是Python中常用的数据结构。它们的主要应用是在计算机程序中存储和操作数据。

栈和队列都是线性数据结构，但与列表（List）或元组（Tuple）不同，它们有一些显著的特性。比如，栈只允许从顶部添加或删除项，而队列只允许从队列的前端（或末尾）添加或删除项；队列称为先进先出FIFO（First In First Out），而栈则被称为后进先出LIFO（Last In First Out）；双端队列则可以在前端或末尾添加或删除项。

在下面的内容中，我们将介绍如何使用Python内置的列表和集合（Deque）类型来实现栈、队列和双端队列。

栈(Stack)

栈是一种后进先出（LIFO）的数据结构，通常用中括号”[ ]“表示。栈中每个元素被称为一个”项“，在Python中使用列表来表示栈。栈的两个主要操作是推入（Push）和弹出（Pop），其中推入将添加一个项到栈顶，弹出将移除栈顶的项。

掌握栈数据结构的常用操作，提供以下代码示例：

  1. 创建空栈
stack = []
  1. 判断栈是否为空
if not stack:
    print("Stack is empty")
  1. 推入项

可以使用append()方法将项添加到列表末尾

stack.append("A")
stack.append("B")
print(stack) # ['A', 'B']
  1. 弹出项

可以使用pop()方法从列表末尾删除项

stack.pop()
print(stack) # ['A']

队列(Queue)

队列是一种先进先出(FIFO)的线性数据结构，简单来说就是在队列的末尾添加元素，从队列的头部删除元素。队列通常使用中括号”[ ]“表示。在Python中，使用列表来实现队列的操作。

掌握队列数据结构的常用操作，提供以下代码示例：

  1. 创建空队列
queue = []
  1. 判断队列是否为空
if not queue:
    print("Queue is empty")
  1. 向队列中添加一个元素

可以使用append()方法将项添加到列表末尾

queue.append("A")
queue.append("B")
print(queue) # ['A', 'B']
  1. 从队列中删除一个元素

可以使用pop(0)方法从列表的第一个位置删除项

queue.pop(0)
print(queue) # ['B']

双端队列(Deque)

双端队列同样是一种线性数据结构，区别在于双端队列两端都可以添加或删除元素。双端队列具有队列和栈的属性，所以它是一种非常有用的数据结构。在Python中，双端队列的实现方式是使用集合类collections中的deque。

掌握双端队列数据结构的常用操作，提供以下代码示例：

  1. 创建空的双端队列
from collections import deque
deq = deque()
  1. 判断双端队列是否为空
if not deq:
    print("Deque is empty")
  1. 向双端队列的末尾添加元素

可以使用append()方法将项添加到集合的末尾

deq.append("A")
deq.append("B")
print(deq) # deque(['A', 'B'])

  1. 从双端队列两端删除元素

    • 利用popleft()方法删除队列左端第一个元素
    • 用pop()方法删除队列右端第一个元素
    • 用pop()方法删除队列左端第一个元素
    • 利用popright()方法删除队列右端第一个元素

    代码示例：

    “`python
    deq.popleft()
    print(deq) # deque([‘B’])

    deq.pop()
    print(deq) # deque([])

    deq.appendleft(“C”)
    print(deq) # deque([‘C’])

    deq.pop()
    print(deq) # deque([])
    “`

结语

在Python中，栈、队列和双端队列是常用的数据结构。Python内置的列表和集合类型提供了方便的方法来实现栈、队列和双端队列。理解这些数据结构的实现和操作将对编程很有用。在实际应用中，用户需要根据实际情况灵活运用。

Tags: ,