堆栈和队列 ||蟒蛇 ||数据结构和算法

堆

Stack - 它是一个存储容器，支持按后进先出 (LIFO) 顺序检索。当检索顺序根本不重要时（例如处理批处理作业时），堆栈可能是正确的容器。

例如，考虑自助餐厅中使用的一叠盘子：从盘子中取出盘子的顺序与添加盘子的顺序相反，因为只有顶部的盘子可以访问.

堆栈上的 INSERT 操作通常称为 PUSH，而不带元素参数的 DELETE 操作通常称为 POP。

压入 (x,s): 将项目 x 插入堆栈 s 的顶部。

Pop(s) : 返回（并删除）堆栈 s 的顶部项目。

尽管有保质期的激励，放入冰箱的食物通常也会以同样的方式取出。从算法上来说，后进先出往往发生在执行递归算法的过程中。

堆栈的应用 -

1. 函数调用：用于管理函数执行和递归。
2. 撤消操作： 跟踪编辑器中“撤消/重做”的更改。
3. 浏览器历史记录：存储访问过的页面以进行回溯。
4. 表达式解析： 计算并转换数学表达式。
5. 语法验证： 匹配代码中的括号或标签。
6. 内存管理：在程序执行期间管理调用堆栈。
7. DFS： 在图算法中实现深度优先搜索。

使用数组实现堆栈 -

• push() - 将元素插入堆栈
• pop() - 从堆栈中删除一个元素
• top() - 返回堆栈的顶部元素。
• isEmpty() - 如果堆栈为空则返回 true，否则返回 false。

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

队列

队列 - 它是一个存储容器，支持按先进先出（FIFO）顺序检索。我们将队列上的 INSERT 操作称为 ENQUEUE，将 DELETE 操作称为 DEQUEUE。与堆栈操作 POP 一样，DEQUEUE 不带元素参数。堆栈和队列是动态集合，其中通过 DELETE 操作从集合中删除的元素是预先定义的。

入队(x,q):将项目x插入队列q的后面。

出队（q）： 返回（并删除）队列 q 中最前面的项。

队列有头和尾。

• 当一个元素入队时，它会在队列尾部占据一席之地，就像新到达的顾客在队列末尾占据一席之地一样。

• 出队的元素总是排在队列最前面的那个，就像排在队伍最前面的顾客，他等待的时间最长。

队列的应用 -

1. 任务调度：按顺序管理CPU进程和作业。
2. BFS： 在图中实现广度优先搜索。
3. 打印队列： 按顺序处理打印作业。
4. 网络路由：缓冲数据包的传输。
5. 呼叫中心：管理等待订单中的客户呼叫。
6. 流媒体：实时缓冲视频或音频流。
7. 输入事件： 处理 GUI 系统中的键盘和鼠标输入。

使用数组实现队列-

• enqueue() – 将元素插入队列。
• dequeue() – 从队列中删除元素。
• peek() 或 front()- 获取队列前端节点可用的数据元素，但不删除它。
• isEmpty() – 检查队列是否为空。

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

使用堆栈实现队列 -

• push(x) - 将所有元素从 stack1 移至堆栈 2 以反转其顺序，然后一次又一次将所有元素从 stack2 移回堆栈 1。
• pop() - 从队列前面移除元素并返回它
• peek() - 返回队列前面的元素
• empty() - 如果队列为空则返回 true，否则返回 false

class MyQueue:
    def __init__(self):
        # Store elements
        self.queue = []
        # A pointer to indicate the start position
        self.p_start = 0

    def enQueue(self, x):
        #Insert an element into the queue. 
        self.queue.append(x)
        return True # Return True if the operation is successful

    def deQueue(self):
        #Delete an element from the queue. 
        if self.isEmpty():
            return False
        self.p_start += 1
        return True #Return True if the operation is successful

    def Front(self):
        #Get the front item from the queue.
        if not self.isEmpty():
            return self.queue[self.p_start]
        return None  # Return None if the queue is empty

    def isEmpty(self):
        #Checks whether the queue is empty or not
        return self.p_start >= len(self.queue)

使用队列实现堆栈 -

• push(x) - 将新元素添加到第二个队列，然后将所有元素从队列 1 移动到队列 2 以维持堆栈顺序 (LIFO) 并交换队列。
• pop() - 移除栈顶元素并返回
• peek 或 top() - 返回队列前面的元素
• empty() - 如果队列为空则返回 true，否则返回 false

class MyQueue:

    def __init__(self):
        self.stack_1 = []  # Main stack for enqueue operations
        self.stack_2 = []  # Temporary stack for dequeue operations
        self.front = None

    # Pushes element x to the back of the queue.
    def push(self, x):

        # Move all elements from stack1 to stack 2 to reverse their order
        while self.stack_1:
            self.stack_2.append(self.stack_1.pop())
        self.stack_2.append(x)

        # Move all elements back from stack2 to stack 1 as a queue
        while self.stack_2:
            self.stack_1.append(self.stack_2.pop())

    # Removes the element from the front of the queue and returns it
    def pop(self):
        return self.stack_1.pop()

    # Returns the element at the front of the queue
    def peek(self):
        return self.stack_1[-1]

    # Returns true if the queue is empty, false otherwise
    def empty(self):
        return not self.stack_1

以上是堆栈和队列 ||蟒蛇 ||数据结构和算法的详细内容。更多信息请关注PHP中文网其他相关文章！