算法系列15天速成 第八天 线性表【下】

算法系列15天速成 第八天 线性表【下】完整攻略

前言

在线性表【上】的基础上，我们再来讲一些新的线性表特性及其相关算法。

栈

栈是一种特殊的线性表，只能在表尾插入和删除数据，简单来说就是类似于装东西的箱子。它有以下几个特点：

1. 先进后出，后进先出，即最先入栈的元素最后出栈；
2. 只能在表尾插入和删除数据，元素的加入和删除只发生在栈顶。

栈的应用

1. 递归；
2. 计算器；
3. 括号匹配。

栈的实现方式

可以使用数组或链表实现。

栈的实现示例

这里我们使用链表来实现栈。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head == None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.is_empty():
            return None
        temp = self.head
        self.head = self.head.next
        return temp.data

    def peek(self):
        if self.is_empty():
            return None
        return self.head.data

队列

队列也是一种线性表，它与栈不同的地方在于，队列只能在表尾插入数据，在表头删除数据。

队列的应用

1. 操作系统中的任务调度；
2. 模拟实验。

队列的实现方式

可以使用数组或链表实现。

队列的实现示例

这里我们使用链表来实现队列。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        return self.head == None

    def enqueue(self, data):
        new_node = Node(data)
        if self.tail == None:
            self.head = self.tail = new_node
            return
        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.is_empty():
            return None
        temp = self.head
        self.head = temp.next
        if(self.head == None):
            self.tail = None
        return temp.data

    def peek(self):
        if self.is_empty():
            return None
        return self.head.data

双端队列

双端队列（deque，全称double-ended queue）是一种具有队列和栈的性质的数据结构。

双端队列的应用

经常用于解决某些问题时，数据需要「先进先出」（队列），但同时在某些操作时需要「后进先出」（栈）。

双端队列的实现方式

可以使用数组或链表实现。

双端队列的实现示例

这里我们使用双向链表来实现双端队列。

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class Deque:
    def __init__(self):
        self.front = None
        self.rear = None

    def is_empty(self):
        return self.front == None

    def add_front(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.front = self.rear = new_node
            return
        self.front.prev = new_node
        new_node.next = self.front
        self.front = new_node

    def add_rear(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        new_node.prev = self.rear
        self.rear = new_node

    def remove_front(self):
        if self.is_empty():
            return None
        temp = self.front
        self.front = temp.next
        if(self.front == None):
            self.rear = None
        else:
            self.front.prev = None
        return temp.data

    def remove_rear(self):
        if self.is_empty():
            return None
        temp = self.rear
        self.rear = temp.prev
        if(self.rear == None):
            self.front = None
        else:
            self.rear.next = None
        return temp.data

    def peek_front(self):
        if self.is_empty():
            return None
        return self.front.data

    def peek_rear(self):
        if self.is_empty():
            return None
        return self.rear.data

总结

以上就是关于栈、队列和双端队列的所有内容。希望你能够从这些算法中，深刻了解线性表的应用和实现方式。