数据结构--栈和队列

个人介绍

hello hello~ ，这里是 code袁~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹

🦁作者简介：一名喜欢分享和记录学习的在校大学生
💥个人主页：code袁
💥 个人QQ：2647996100
🐯 个人wechat：code8896

专栏导航

code袁系列专栏导航
1.毕业设计与课程设计：本专栏分享一些毕业设计的源码以及项目成果。🥰🥰🥰
2.微信小程序开发：本专栏从基础到入门的一系开发流程，并且分享了自己在开发中遇到的一系列问题。🤹🤹🤹
3.vue开发系列全程线路：本专栏分享自己的vue的学习历程。

非常期待和您一起在这个小小的互联网世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨ 

1、 什么是栈？

栈是一种线性数据结构，具有后进先出（LIFO）的特点。栈可以简单地理解为一摞盘子，我们只能在盘子的顶部放入或取出盘子，不能在中间插入或者从底部取出盘子。

栈的基本操作

栈的基本操作包括压入（push）和弹出（pop）两种操作：

• 压入（push）：将元素放入栈顶。
• 弹出（pop）：从栈顶取出元素。

除了基本操作，栈还有其他常用的操作，比如查看栈顶元素（top）、判断栈是否为空（isEmpty）等。

栈的实现

栈可以使用数组或链表来实现。下面是一个使用数组实现栈的示例代码：

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()
        else:
            return None

    def top(self):
        if not self.isEmpty():
            return self.stack[-1]
        else:
            return None

    def isEmpty(self):
        return len(self.stack) == 0

栈的应用

栈在计算机科学中有着广泛的应用，比如：

• 函数调用：函数调用时使用栈来保存函数的局部变量和返回地址。
• 表达式求值：中缀表达式转换为后缀表达式时常用栈来实现。
• 浏览器的返回按钮：浏览器的返回按钮使用栈来记录访问过的页面。

栈的例子

1. 使用栈判断括号是否匹配

def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping.values():
            stack.append(char)
        elif char in mapping.keys():
            if not stack or mapping[char] != stack.pop():
                return False
    
    return not stack

2. 使用栈实现逆波兰表达式求值

def evalRPN(tokens):
    stack = []
    operators = {'+', '-', '*', '/'}
    
    for token in tokens:
        if token not in operators:
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(int(a / b))
    
    return stack[0]

2、 什么是队列？

队列是一种线性数据结构，具有先进先出（FIFO）的特点。队列可以简单地理解为排队，先到先得，后到后得。

队列的基本操作

队列的基本操作包括入队（enqueue）和出队（dequeue）两种操作：

• 入队（enqueue）：将元素放入队列的末尾。
• 出队（dequeue）：从队列的头部取出元素。

除了基本操作，队列还有其他常用的操作，比如查看队列头部元素（front）、查看队列尾部元素（rear）、判断队列是否为空（isEmpty）等。

队列的实现

队列可以使用数组或链表来实现。下面是一个使用链表实现队列的示例代码：

class QueueNode:
    def __init__(self, value):
        self.value = value
        self.next = None

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

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

    def dequeue(self):
        if not self.isEmpty():
            item = self.front.value
            self.front = self.front.next
            if self.front is None:
                self.rear = None
            return item
        else:
            return None

    def front(self):
        if not self.isEmpty():
            return self.front.value
        else:
            return None

    def rear(self):
        if not self.isEmpty():
            return self.rear.value
        else:
            return None

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

队列的应用

队列在计算机科学中有着广泛的应用，比如：

• 任务调度：操作系统中的任务调度通常使用队列来实现。
• 广度优先搜索：图的广度优先搜索算法中使用队列来保存待访问的节点。
• 消息队列：在分布式系统中，消息队列常用来实现异步通信。

队列的例子

1. 使用队列实现烫手山芋游戏

from collections import deque

def hot_potato(names, num):
    queue = deque(names)
    while len(queue) > 1:
        for _ in range(num):
            queue.append(queue.popleft())
        queue.popleft()
    return queue.pop()

2. 使用队列实现广度优先搜索

def bfs(graph, start):
    visited = set()
    queue = Queue()
    queue.enqueue(start)
    visited.add(start)
    while not queue.isEmpty():
        node = queue.dequeue()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.enqueue(neighbor)
                visited.add(neighbor)

🎉写在最后

🍻伙伴们，如果你已经看到了这里，觉得这篇文章有帮助到你的话不妨点赞👍或 Star ✨支持一下哦！手动码字，如有错误，欢迎在评论区指正💬~

你的支持就是我更新的最大动力💪~