堆栈与队列实现方式

前言

堆栈和队列是计算机科学中两种基本的数据结构，广泛应用于算法设计和程序开发中。它们的主要区别在于数据元素的插入、删除操作所遵循的原则不同：堆栈遵循后进先出（LIFO）原则，而队列则遵循先进先出（FIFO）原则。

堆栈实现方式

1. 数组实现

数组是一种常见的堆栈实现方法。通过设置一个指针top来跟踪当前堆栈的顶部位置，并使用一个固定大小的数组来存储元素。

class ArrayStack:
    def __init__(self, capacity):
        self.top = -1
        self.data = [None] * capacity

    def push(self, item):
        if self.top + 1 < len(self.data):
            self.top += 1
            self.data[self.top] = item
        else:
            raise Exception("Stack is full")

    def pop(self):
        if self.top == -1:
            raise Exception("Stack is empty")
        result = self.data[self.top]
        self.top -= 1
        return result

    def peek(self):
        if self.top == -1:
            raise Exception("Stack is empty")
        return self.data[self.top]

    def isEmpty(self):
        return self.top == -1

2. 链表实现

链表也可用于堆栈的实现，其主要优势在于不需要预先确定大小，并且在插入和删除元素时效率较高。

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

class LinkedListStack:
    def __init__(self):
        self.top = None

    def push(self, item):
        new_node = Node(item)
        if not self.top:
            self.top = new_node
        else:
            new_node.next = self.top
            self.top = new_node

    def pop(self):
        if not self.top:
            raise Exception("Stack is empty")
        result = self.top.item
        self.top = self.top.next
        return result

    def peek(self):
        if not self.top:
            raise Exception("Stack is empty")
        return self.top.item

    def isEmpty(self):
        return self.top is None

队列实现方式

1. 数组实现

数组同样可以用于队列的实现，通过设置头指针front和尾指针rear来跟踪队列的首尾位置。

class ArrayQueue:
    def __init__(self, capacity):
        self.front = 0
        self.rear = 0
        self.capacity = capacity
        self.data = [None] * capacity

    def enqueue(self, item):
        if (self.rear + 1) % self.capacity == self.front:
            raise Exception("Queue is full")
        self.data[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity

    def dequeue(self):
        if self.front == self.rear:
            raise Exception("Queue is empty")
        result = self.data[self.front]
        self.front = (self.front + 1) % self.capacity
        return result

    def peek(self):
        if self.front == self.rear:
            raise Exception("Queue is empty")
        return self.data[self.front]

    def isEmpty(self):
        return self.front == self.rear

2. 链表实现

链表同样适用于队列的实现，使用一个节点来表示队首，另一个节点来表示队尾。

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

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

    def enqueue(self, item):
        new_node = Node(item)
        if not self.rear:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if not self.front:
            raise Exception("Queue is empty")
        result = self.front.item
        self.front = self.front.next
        if not self.front:
            self.rear = None
        return result

    def peek(self):
        if not self.front:
            raise Exception("Queue is empty")
        return self.front.item

    def isEmpty(self):
        return self.front is None

结语

堆栈和队列作为基本的数据结构，在许多算法设计中发挥着重要作用。通过上述实现方式，可以更好地理解和应用这两种数据结构。无论是选择数组还是链表来实现，都应根据具体的应用场景和技术要求做出合适的选择。