数据结构初见-栈

cover
cover

如果说算法是程序的灵魂，那么数据结构就如同程序的躯体。 学习数据结构，一定少不了基础而经典的——栈(stack) 那么，栈是什么？

什么是栈

Stack 是东方Project同人音乐社团「暁records」主唱/作词/偶尔作曲/编曲，拥有的独特嗓音,虽然有些人不喜欢,但是从来不会被忽略,一入耳就能留下永远无法忘记的印象…… >

Stack姐
Stack姐

咳咳……正经的：

In computer science, a stack is an abstract data type that serves as a collection of elements, with two main operations:

  • Push, which adds an element to the collection, and
  • Pop, which removes the most recently added element that was not yet removed. ——from WIKIPEDIA

简言之，栈（stack，又称为堆栈或堆叠）就是符合 “后进先出”(Last In First Out, LIFO) 规则的线性存储结构，有PUSH和POP两种操作

  • PUSH: 压栈，把元素压入栈顶
  • POP: 弹出：从栈顶把元素弹出
    Lifo stack
    Lifo stack
    由此我们知道，元素只能从栈顶入、从栈顶出，而不能从栈底进出 把栈比作一个直径为一颗糖果大小、封底无盖的糖果盒，要想存取糖果，只能从开口的一端来——每次操作都只与栈顶元素相关

代码实现

例题

用一道例题来说明栈的用途：铁轨(Rails, ACM/ICPC CERC 1997, UVa 514) 题目略有改动

Summary > There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.

Explanation > The problem requires reordering items on a stack, specifically to determine if the reordering can be done in a single pass.

Input Sample

5
1 2 3 4 5
5
5 4 1 2 3
6
6 5 4 3 2 1

Ouput Sample

Yes
No
Yes

C++

C++ 的 STL 提供了包括栈在内等特殊的数据结构，可以很方便地调用。参考了刘汝佳老师的代码

rails.cpp

#include <cstdio>
#include <stack>
using namespace std;
const int MAXN = 1000 + 10;

int n, target[MAXN];

int main()
{
    while (scanf("%d", &n) == 1)
    {
        stack<int> s;
        int A = 1, B = 1;
        for (int i = 1; i <= n; i++)
            scanf("%d", &target[i]);
        int ok = 1;
        while (B <= n)
        {
            if (A == target[B]) { A++; B++; }
            else if (!s.empty() && s.top() == target[B]) { s.pop(); B++; }
            else if (A <= n) s.push(A++);
            else { ok = 0; break; }
        }
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
}

Python

Python再翻译

Python内置的数据结构相当强大，可以轻松模拟栈

rails.py

while 1:
    n = input()
    if n == "":
        break
    n = int(n)
    s = []
    target = [0] + list(map(int, input().split()))
    A, B, ok = 1, 1, 1
    while B <= n:
        if A == target[B]:
            A += 1
            B += 1
        elif len(s) != 0 and s[-1] == target[B]:
            s.pop(-1)
            B += 1
        elif A <= n:
            A += 1
            s.append(A)
        else:
            ok = 0
            break
    if ok == 1:
        print("Yes")
    else:
        print("No")

EX: Python类实现Stack

利用list这一好用的内置数据结构，我们可以用Python类来实现栈

stack.py

class Stack(object):
    __slots__ = ('__items')  # 限定Stack类的成员只有__items
    # 初始化栈为空列表
    def __init__(self):
        self.__items = []  # 私有属性

    # 判断栈是否为空，返回布尔值
    def empty(self):
        return self.__items == []

    # 返回栈顶元素
    def top(self):
        return self.__items[-1]

    # 返回栈的大小
    def size(self):
        return len(self.__items)

    # 把新的元素堆进栈里面（程序员喜欢把这个过程叫做压栈，入栈，进栈……）
    def push(self, item):
        self.__items.append(item)

    # 把栈顶元素丢出去（程序员喜欢把这个过程叫做出栈……）
    def pop(self):
        return self.__items.pop(-1)


if __name__ == '__main__':
    # 初始化一个栈对象
    my_stack = Stack()

    # 把'candy_01'丢进栈里
    my_stack.push('candy_01')

    # 把'candy_02'丢进栈里
    my_stack.push('candy_02')

    # 看一下栈的大小（有几个元素）
    print(my_stack.size())

    # 打印栈顶元素
    print(my_stack.top())

    # 把栈顶元素丢出去，并打印出来
    print(my_stack.pop())

    # 再看一下栈顶元素是谁
    print(my_stack.top())

    # 这个时候栈的大小是多少？
    print(my_stack.size())

    # 再丢一个栈顶元素
    print(my_stack.pop())

    # 看一下栈的大小
    print(my_stack.size())

    # 栈是不是空了？
    print(my_stack.empty())

    # 哇~真好吃~
    print('Yummy~')

yummy
yummy

冰轮韵

冰轮舞韵，代码凝魂。
天地与我并生，而万物与我为一。

简单而又不简单

发布日期：2022-10-30
最后更新：2022-10-30

目录：