3.1 ADT 栈

  • 「栈 stack」 是一个特殊的有序表,其插入和删除操作都在一端进行,插入和删除端称为「栈顶 top」。栈又称为「后进先出 LIFO」表。
  • 「系统栈」 一种特殊的栈,用来处理程序运行时的函数调用。每当函数被调用时,系统首先创建一个称为「活动记录」或「栈帧」的结构,将其存放在系统栈的栈顶。初始时,被调函数的活动记录只包含一个指向前一个活动记录的指针和一个返回地址。前一个活动记录的指针指向调用函数的活动记录,而返回地址包含的是函数调用结束后下一条执行语句的地址。因为在任意时刻,只有一个函数被执行,所以被执行的函数就是活动记录位于系统栈栈顶的函数。如果该函数又调用其他函数,那么,函数中的局部变量(静态局部变量除外)及其参数也将加到其活动记录中。然后,为被调函数创建一个新的活动记录并存放在系统栈的栈顶。当被调函数结束时,删除该活动记录。此时,调用函数的活动记录又位于系统栈的栈顶,继续该函数的运行。
  • 「ADT 栈」
class Stack
{
    Stack CreateS(uint max_stack_size) { 创建一个空栈,其大小为 max_stack_size }
    bool IsFull(Stack stack, uint max_stack_size) {
        if (栈 stack 的元素个数 stack == max_stack_size) return true
        else return false
    }
    Stack Add(Stack stack, Element item) {
        if (IsFull(stack)) stack full.
        else 将元素 item 插入栈 stack 顶,return stack
    }
    bool IsEmpty(Stack stack) {
        if (stack == CreateS(max_stack_size)) return true
        else return false
    }
    Element Delete(Stack stack) {
        if (IsEmpty(stack)) return stack
        else 删除并返回栈顶元素 item
    }
}

results matching ""

    No results matching ""