数据结构与算法 栈与队列

简介: 数据结构与算法 栈与队列

基于数组的实现

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

重点回顾

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


目录
相关文章
|
5天前
|
算法 C语言 C++
【practise】栈的压入和弹出序列
【practise】栈的压入和弹出序列
|
3天前
|
缓存 算法 Java
刷算法,你应该知道的队列经典应用
文章介绍了队列的基本特性和经典应用,包括如何用队列实现栈、使用优先级队列解决Top K问题,并通过LeetCode题目示例展示了队列在算法实现中的应用。
刷算法,你应该知道的队列经典应用
|
3天前
栈的几个经典应用,真的绝了
文章总结了栈的几个经典应用场景,包括使用两个栈来实现队列的功能以及利用栈进行对称匹配,并通过LeetCode上的题目示例展示了栈在实际问题中的应用。
栈的几个经典应用,真的绝了
|
4天前
|
存储 网络协议 Linux
用户态协议栈06-TCP三次握手
用户态协议栈06-TCP三次握手
|
3天前
|
算法
【数据结构与算法】优先级队列
【数据结构与算法】优先级队列
6 0
|
3天前
|
存储 算法
【数据结构与算法】队列(顺序存储)
【数据结构与算法】队列(顺序存储)
5 0
|
4天前
|
存储
全局变量和局部变量在堆和栈的区别
全局变量和局部变量在堆和栈的区别
12 0
|
5天前
|
存储 人工智能 运维
高质量存储力发展问题之浪潮信息发布的大模型智算软件栈的定义如何解决
高质量存储力发展问题之浪潮信息发布的大模型智算软件栈的定义如何解决
8 0
|
5天前
|
设计模式 算法 C语言
【CPP】栈、双端队列、队列、优先级队列与反向迭代器
【CPP】栈、双端队列、队列、优先级队列与反向迭代器
|
2月前
|
算法 C++ Python
数据结构与算法===贪心算法
数据结构与算法===贪心算法

热门文章

最新文章