数据结构与算法 栈与队列

栈

基于数组的实现

class ArrayStack:
    def __init__(self) -> None:
        self.__stack = []
        
    def size(self):
        return len(self.__stack)
        
    def is_empty(self):
        if self.size() == 0:
            return True
        else:
            return False

    def push(self, val):
        self.__stack.append(val)

    def pop(self):
        if self.is_empty():
            raise IndexError('栈中无数据')
        else:
            return self.__stack.pop(-1)

    def peek(self):
        if self.is_empty():
            raise IndexError('栈中无数据')
        else:
            return self.__stack[-1]

    def to_list(self):
        return self.__stack

基于链表的实现

class ListNode:
    def __init__(self, value) -> None:
        self.val = value
        self.next = None

class ListStack:
    def __init__(self) -> None:
        self.__peek = None
        self.__size = 0

    def size(self):
        return self.__size

    def is_empty(self):
        if self.__peek == None:
            return True
        else:
            return False

    def push(self, val):
        node = ListNode(val)
        if self.is_empty():
            self.__peek = node
        else:
            stack_next = self.__peek
            self.__peek = node
            self.__peek.next = stack_next
            self.__size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError('栈中无数据')
        else:
            pop_listnode = self.__peek
            self.__peek = self.__peek.next
            return pop_listnode.val

    def peek(self):
        if self.is_empty():
            raise IndexError('栈中无数据')
        else:
            return self.__peek.val

    def to_list(self):
        lst = []
        peek = self.__peek
        while peek:
            lst.append(peek.val)
            peek = peek.next
        lst.reverse()
        return lst

两种类型栈的区别

• 时间效率
  • 基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高。
  • 基于链表实现的栈可以提供更加稳定的效率表现。
• 空间效率
  • 基于数组实现的栈可能造成一定的空间浪费。
  • 由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大。
  • 我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。

队列

基于数组的实现

class ArrayQueue:
    def __init__(self) -> None:
        self.__queue = []
        self.__size = 0

    def size(self):
        return self.__size
        
    def is_empty(self):
        if self.size() == 0:
            return True
        else:
            return False

    def push(self, val):
        self.__queue.append(val)
        self.__size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError('队列无数据')
        else:
            val = self.__queue.pop(0)
            self.__size -= 1
            return val
            
    def to_list(self):
        return self.__queue

基于链表的实现

class ListNode:
    def __init__(self, value) -> None:
        self.val = value
        self.next = None

class ListQueue:
    def __init__(self) -> None:
        self.__front = None
        self.__rear = None
        self.__size = 0

    def size(self):
        return  self.__size

    def is_empty(self):
        if self.size() == 0:
            return True
        else:
            return False

    def push(self, value):
        node = ListNode(value)
        if self.is_empty():
            self.__front = node
            self.__rear = node
        else:
            self.__rear.next = node
            self.__rear = node
        self.__size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError('队列无数据')
        else:
            node = self.__front
            self.__front = self.__front.next
            self.__size -= 1
            return node.val

    def to_list(self):
        lst = []
        node = self.__front
        while node:
            lst.append(node.val)
            node = node.next
        return lst

双向队列

基于数组的实现

class ArrayDeque:
    def __init__(self) -> None:
        self.__deque = []
        self.__size = 0
  
    def size(self):
        return self.__size
        
    def is_empty(self):
        if self.size() == 0:
            return True
        else:
            return False

    def push(self, val, where):
        if where == 'front':
            self.__deque.insert(0, val)
        elif where == 'rear':
            self.__deque.insert(-1, val)
        self.__size += 1

    def pop(self, where):
        if self.is_empty():
            raise IndexError('队列无数据')
        else:
            if where == 'front':
                val = self.__deque.pop(0)
            elif where == 'rear':
                val = self.__deque.pop(-1)
            self.__size -= 1
            return val

    def to_list(self):
        return self.__deque

基于链表的实现

class ListNode:
    def __init__(self, value) -> None:
        self.val = value
        self.next = None
        self.prev = None

class ListDeque:
    def __init__(self) -> None:
        self.__front = None
        self.__rear = None
        self.__size = 0

    def size(self):
        return self.__size

    def is_empty(self):
        if self.size() == 0:
            return True
        else:
            return False

    def push(self, value, where):
        node = ListNode(value)
        if self.is_empty():
            self.__front = node
            self.__rear = node
        else:
            if where == 'front':
                self.__front.prev = node
                node.next = self.__front
                self.__front = node
            elif where == 'rear':
                self.__rear.next = node
                node.prev = self.__rear
                self.__rear = node

        self.__size += 1

    def pop(self, where):
        if self.is_empty():
            raise IndexError('队列无数据')
        else:
            if where == 'front':
                node = self.__front.next
                if node:
                    self.__front.next = None
                    self.__front = node
                    self.__front.prev = None
            elif where == 'rear':
                node = self.__rear.prev
                if node:
                    self.__rear.prev = None
                    self.__rear = node
                    self.__rear.next = None

        self.__size -= 1

    def to_list(self):
        lst = []
        node = self.__front
        while node:
            lst.append(node.val)
            node = node.next
        return lst

重点回顾

• 栈是一种遵循先入后出原则的数据结构，可通过数组或链表来实现。
• 从时间效率角度看，栈的数组实现具有较高的平均效率，但在扩容过程中，单次入栈操作的时间复杂度会降低至 𝑂(𝑛) 。相比之下，基于链表实现的栈具有更为稳定的效率表现。
• 在空间效率方面，栈的数组实现可能导致一定程度的空间浪费。但需要注意的是，链表节点所占用的内存空间比数组元素更大。
• 队列是一种遵循先入先出原则的数据结构，同样可以通过数组或链表来实现。在时间效率和空间效率的对比上，队列的结论与前述栈的结论相似。
• 双向队列是一种具有更高自由度的队列，它允许在两端进行元素的添加和删除操作。