DSA 栈

栈

栈是一种可以保存多个元素的数据结构。

想象一个煎饼堆。

在煎饼堆中，煎饼都是从顶部添加和移除的。所以当移除一个煎饼时，它总是你添加的最后一个煎饼。这种组织元素的方式称为 LIFO：后进先出。

我们可以在栈上进行的基本操作是

• Push: 在栈上添加一个新元素。
• Pop: 从栈中移除并返回顶部的元素。
• Peek: 返回栈顶部的元素。
• IsEmpty: 检查栈是否为空。
• Size: 查找栈中元素的数量。

在上面的栈动画中尝试这些基本操作。

栈可以使用数组或链表来实现。

栈可以用来实现撤销机制，以恢复到以前的状态，为图中的深度优先搜索创建算法，或者用于回溯。

栈通常与队列一起提及，队列是下一页面描述的类似数据结构。

使用数组实现栈

为了更好地理解使用数组或链表来实现栈的优势，你应该查看此页面，它解释了数组和链表如何在内存中存储。

当我们使用数组作为栈时，它看起来像这样

使用数组实现栈的原因

• 内存效率: 与链表节点不同，数组元素不包含指向下一个元素的地址。
• 更易于实现和理解: 使用数组来实现栈所需的代码比使用链表更少，因此它通常也更容易理解。

不使用数组来实现栈的原因

• 固定大小: 数组占用内存的固定部分。这意味着它可能占用比需要的内存更多，或者如果数组填满了，它就不能容纳更多元素。

由于 Python 列表很好地支持实现栈所需的功能，因此我们可以从创建一个栈并使用几行代码进行栈操作开始

stack = []

# Push
stack.append('A')
stack.append('B')
stack.append('C')
print("Stack: ", stack)

# Pop
element = stack.pop()
print("Pop: ", element)

# Peek
topElement = stack[-1]
print("Peek: ", topElement)

# isEmpty
isEmpty = not bool(stack)
print("isEmpty: ", isEmpty)

# Size
print("Size: ",len(stack))

但为了明确地创建用于栈的数据结构，并进行基本操作，我们应该创建一个栈类。这种在 Python 中创建栈的方法也更类似于在其他编程语言（如 C 和 Java）中创建栈的方法。

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, element):
        self.stack.append(element)
    
    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.stack.pop()
    
    def peek(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.stack[-1]
    
    def isEmpty(self):
        return len(self.stack) == 0
    
    def size(self):
        return len(self.stack)

# Create a stack
myStack = Stack()

myStack.push('A')
myStack.push('B')
myStack.push('C')
print("Stack: ", myStack.stack)

print("Pop: ", myStack.pop())

print("Peek: ", myStack.peek())

print("isEmpty: ", myStack.isEmpty())

print("Size: ", myStack.size())

使用链表实现栈

使用链表来实现栈的原因

• 动态大小: 与数组不同，栈可以动态地增长和收缩。

不使用链表来实现栈的原因

• 额外的内存: 每个栈元素必须包含指向下一个元素（下一个链表节点）的地址。
• 可读性: 代码对于某些人来说可能更难阅读和编写，因为它更长更复杂。

这是一个使用链表实现栈的示例。

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

class Stack:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def push(self, value):
        new_node = Node(value)
        if self.head:
            new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        popped_node = self.head
        self.head = self.head.next
        self.size -= 1
        return popped_node.value
    
    def peek(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.head.value
    
    def isEmpty(self):
        return self.size == 0
    
    def stackSize(self):
        return self.size

myStack = Stack()
myStack.push('A')
myStack.push('B')
myStack.push('C')

print("Pop: ", myStack.pop())
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.stackSize())

DSA 练习

通过练习测试自己

练习

下面的图片代表一个“栈”数据结构。

在上面的栈上运行 peek() 方法，返回什么？

提交答案 »

开始练习