DSA 栈

栈

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

将栈想象成一叠煎饼。

在一叠煎饼中，煎饼的添加和移除都在顶部进行。因此，当移除一个煎饼时，它总是你最后添加的那个。这种组织元素的方式称为 LIFO：后进先出（Last In First Out）。

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

• Push：向栈中添加一个新元素。
• Pop：移除并返回栈顶的元素。
• Peek：返回栈顶的元素。
• isEmpty：检查栈是否为空。
• Size：查找栈中元素的数量。

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

栈可以通过数组或链表来实现。

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

栈经常与队列（Queue）一起提及，队列是下一页描述的类似数据结构。

使用数组实现栈

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

这就是我们使用数组作为栈时的样子

使用数组实现栈的原因

• 内存效率高：数组元素不像链表节点那样存储下一个元素的地址。
• 易于实现和理解：使用数组实现栈比使用链表需要更少的代码，因此通常也更容易理解。

不使用数组实现栈的原因

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

由于 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() 方法，会返回什么？

提交答案 »

开始练习