数据结构双端栈基本操作

双端栈（deque）是一种特殊的栈，支持从两端进行插入和删除操作。其基本操作包括：

1. 创建双端栈：可以使用数组或链表来实现双端栈，需要定义两个指针分别指向栈的两端。

2. 判断双端栈是否为空：如果两端指针相遇，说明双端栈为空。

3. 元素入栈：可以从栈的左端或右端插入元素，需要更新相应的指针。

4. 元素出栈：可以从栈的左端或右端删除元素，需要更新相应的指针。

5. 获取栈顶元素：可以获取栈的左端或右端的元素，不会改变栈的结构。

6. 获取栈的大小：可以通过计算左右端指针之间的距离来获取栈的大小。

需要注意的是，双端栈的插入和删除操作比普通栈更加复杂，需要考虑指针的移动和边界情况。正确地实现这些操作可以提高程序的效率和可靠性。

相关问题

）实现双端栈定义一个空栈类，并定义入栈、出栈、取栈元素基本操作。然后在主程序中对给定的N个数据进行验证，输出各个操作结果

在Python中，我们可以创建一个简单的双端栈（Deque）类，利用内置的数据结构`collections.deque`来实现这个功能。deque支持在两端添加和删除元素，非常适合做栈的操作。下面是一个基础的实现：

from collections import deque

class StackWithMaxElement:
    def __init__(self):
        self.stack = deque()
        self.max_stack = deque()

    # 入栈操作
    def push(self, item):
        self.stack.append(item)
        if not self.max_stack or item > self.max_stack[-1]:
            self.max_stack.append(item)

    # 出栈操作
    def pop(self):
        if not self.is_empty():
            max_val = self.max_stack.pop() if self.max_stack else None
            return self.stack.pop(), max_val

    # 取栈顶元素操作
    def top(self):
        if not self.is_empty():
            return self.stack[-1]

    # 判断栈是否为空
    def is_empty(self):
        return len(self.stack) == 0

    # 获取栈的最大值
    def get_max(self):
        return self.max_stack[-1] if self.max_stack else None

# 主程序示例
def main(n):
    stack = StackWithMaxElement()
    data = [i for i in range(1, n+1)]
    
    for num in data:
        print(f"Pushing {num}:")
        stack.push(num)
        print(f"Top element: {stack.top()}")
        print(f"Max element so far: {stack.get_max()}")

        print("Popping:")
        popped_num, max_val = stack.pop()
        print(f"Popped: {popped_num}, Max: {max_val}")

if __name__ == "__main__":
    main(5)

在这个例子中，我们定义了一个名为`StackWithMaxElement`的类，它维护了两个栈：一个是正常的栈（`stack`），另一个用于存储最大值（`max_stack`）。当有新元素入栈时，会检查是否更新最大值；出栈时同时返回了当前栈顶元素和最大值。

在`main`函数中，我们展示了如何使用这个栈类，并对给定的N=5个数字进行了一系列的入栈、取栈顶和出栈操作。