数据结构：数组栈的操作实现（ Implementation os Stack using Array）

发布于：2025-08-12 ⋅ 阅读:(12) ⋅ 点赞:(0)

目录

前提：我们已经确定的“公理”

入栈 (Push)

出栈 (Pop)

查看栈顶 (Peek)

前提：我们已经确定的“公理”

在开始推导具体操作前，我们先明确一下已知条件，这是我们推导的基石，是我们自己定下的“规则”。

  1. 我们的目标：实现一个严格遵守“后进先出”（LIFO）规则的数据容器。

  2. 我们的工具：一块连续的内存空间，也就是数组。

  3. 我们的设计图 (struct)：我们已经将实现这个容器所需要的部分打包好，它看起来是这样：

typedef struct {
    int* data;      // 一个指针，指向我们用来存数据的数组
    int top;        // 一个整数，用来追踪“栈顶”在哪
    int capacity;   // 一个整数，记录这个数组总共能装多少东西
} SequentialStack;

我们的基本约定：我们规定，当 top 这个变量的值为 -1 时，代表栈是空的。这是我们判断的唯一标准。

数据结构：栈（Stack）-CSDN博客

好了，所有的“已知公理”都在这里了。现在，我们面对一个初始化好的、空空如也的 SequentialStack 实例，开始推导它的行为。

入栈 (Push)

核心问题：我们要如何把一个新元素 value 放入栈中？

这个过程就像把一个新盘子放到一摞盘子上面。我们需要解决两个子问题：放在哪里和放了之后要更新什么。

  1. 第一问：我们真的能“放”吗？—— 思考边界条件

    • 我们用来放东西的容器是数组，它的容量 capacity 是有限的。在放新东西之前，一个严谨的程序员首先应该问：“万一已经放满了怎么办？”

    • 如何判断“满了”？我们的数组下标是从 0 到 capacity - 1。top 变量追踪的是最顶端元素的下标。如果 top 已经等于 capacity - 1，说明数组的最后一个位置都已经被占用了。

    • 推论 1：操作的第一步，必须是检查栈是否已满。如果 top == capacity - 1，则操作失败，必须立即停止并告知用户“栈满了”。

  2. 第二问：如果没满，应该放在哪个位置？—— 确定目标位置

    • 假设栈不是空的，top 指向的是当前最顶上的元素。新元素 value 必须放在它的“上面”。

    • 在数组里，“上面”就是指下标更大的下一个位置。如果当前栈顶在 data[top]，那么新位置自然就是 data[top + 1]。

    • 推论 2：新元素 value 的存放位置是 data 数组中 top + 1 这个索引所对应的格子。

  3. 第三问：如何完成“放入”这个动作？—— 确定操作顺序

    • 我们现在有两个任务： a. 把 value 赋给 data[top + 1]。 b. 更新 top 的值，让它也变成 top + 1，因为它将成为新的栈顶。

    • 这两个任务的顺序有关系吗？我们来分析一下：

      • 方案A：先放值，再更新 top data[top + 1] = value; top = top + 1;

      • 方案B：先更新 top，再放值 top = top + 1; data[top] = value;

    • 两种方案都能实现目的。但方案 B 在代码上更简洁，可以写成 s->top++，然后 s->data[s->top] = value。它的逻辑也更顺畅：“首先，我把栈顶的标记向上移动一格，为新元素‘预定’出一个位置；然后，我把新元素放到这个‘预定’好的位置上。”

    • 推论 3：一个清晰的入栈操作流程是：① 栈顶索引 top 自增 1。② 将 value 存入 top 索引指向的位置。

结合以上推论，我们得出 Push 函数的完整逻辑：

void Push(SequentialStack* s, int value)
{
// 第1步: 检查边界条件
if (s->top == s->capacity - 1) {
    // 栈满了，打印错误信息，然后返回
    printf("错误：栈已满，无法入栈！\n");
    return;
}

// 第2步: 移动栈顶指针
s->top++; // 或者 s->top = s->top + 1;

// 第3步: 在新的栈顶位置存入数据
s->data[s->top] = value;
}

出栈 (Pop)

核心问题：我们要如何从栈顶取出一个元素？

这个过程就像从一摞盘子顶部拿走一个盘子。我们同样需要解决两个子问题：从哪里拿和拿了之后要更新什么。

  1. 第一问：我们真的有东西可“拿”吗？—— 思考边界条件

    • 在伸手去拿之前，我们得先看看有没有盘子。如果栈里本来就是空的，那这个操作就无法完成。

    • 如何判断“空的”？根据我们的“公理”，top == -1 就代表栈空。

    • 推论 1：操作的第一步，必须是检查栈是否为空。如果 top == -1，则操作失败，必须立即停止并告知用户“栈是空的”。

  2. 第二问：如果没空，应该拿哪个元素？—— 确定目标元素

    • top 变量的定义就是“指向栈顶元素的索引”。所以，我们要拿的元素，就是 data[top]。

    • 推论 2：需要被取出的元素，就存放在 data[s->top]。

  3. 第三问：如何完成“拿走”这个动作？—— 确定操作顺序

    • “拿走”在数组里意味着什么？我们不能真的把那个内存单元删掉。这里的“拿走”仅仅意味着：我们不再认为它是栈的一部分了。

    • 如何实现这一点？只要把 top 指针向下移动一格，top 指向的元素就变成了新的栈顶，原来那个旧的栈顶元素虽然还存在于内存里，但已经被我们“抛弃”了，下次入栈时就会被覆盖。

    • 出栈操作通常需要返回被拿走的那个元素的值。所以，我们有两个任务： a. 获取 data[top] 的值。 b. 更新 top 的值，让它变成 top - 1。

    • 这两个任务的顺序至关重要：

      • 错误方案：先更新 top，再取值 s->top--; int value = s->data[s->top]; // 错了！这里取到的是新栈顶的值，不是我们要的旧栈顶的值。

      • 正确方案：先取值，再更新 top int value = s->data[s->top]; // 先把要返回的值保存下来 s->top--; // 然后再移动栈顶指针，完成“抛弃”操作 return value; // 最后返回保存好的值

    • 推论 3：一个清晰的出栈操作流程是：① 将 data[top] 的值存入一个临时变量。② 栈顶索引 top 自减 1。③ 返回临时变量中的值。

结论：Pop 操作的完整逻辑

int Pop(SequentialStack* s)
{
// 第1步: 检查边界条件
if (s->top == -1) {
    printf("错误：栈为空，无法出栈！\n");
    return -1; // 约定返回一个特殊值代表错误
}

// 第2步: 保存栈顶元素的值
int value_to_return = s->data[s->top];

// 第3步: 移动栈顶指针
s->top--;

// 第4步: 返回保存的值
return value_to_return;
}

查看栈顶 (Peek)

核心问题：我们只想看一眼栈顶的元素，但不想把它拿走，该怎么做？

这是一个比 Pop 更简单的操作。

  1. 第一问：有东西可“看”吗？—— 思考边界条件

    • 和 Pop 一样，如果栈是空的，那就没什么可看的。

    • 推论 1：操作的第一步，必须是检查栈是否为空 (top == -1)。

  2. 第二问：如果没空，看的是哪个元素？—— 确定目标元素

    • top 指针指向的就是栈顶元素。

    • 推论 2：我们要查看的元素就是 data[top]。

  3. 第三问：如何完成“看”这个动作？—— 确定操作

    • “看”的意思是，我们只读取它的值，不对任何状态做任何修改。

    • 因此，我们只需要返回 data[top] 的值即可。绝对不能修改 top 指针。

    • 推论 3：Peek 操作就是直接返回 data[top] 的值。

结论：Peek 操作的完整逻辑

 int Peek(SequentialStack* s)
{
// 第1步: 检查边界条件
if (s->top == -1) {
    printf("错误：栈为空！\n");
    return -1; // 约定返回一个特殊值代表错误
}

// 第2步: 直接返回栈顶元素的值，不修改任何东西
return s->data[s->top];
}

完整代码

#include <stdio.h>  // 用于 printf

#define MAX_SIZE 100  // 最大容量

// 栈的结构
struct Stack {
    int array[MAX_SIZE];  // 存储数据的数组
    int top;              // 栈顶位置
};

// 初始化栈
void initStack(struct Stack *s) {
    s->top = -1;  // 空栈
}

// 判断是否为空
int isEmpty(struct Stack *s) {
    if (s->top == -1) {
        return 1;  // 是空的
    }
    return 0;  // 不空
}

// 判断是否已满
int isFull(struct Stack *s) {
    if (s->top == MAX_SIZE - 1) {
        return 1;  // 已满
    }
    return 0;  // 未满
}

// 入栈
void push(struct Stack *s, int data) {
    if (isFull(s)) {
        printf("栈已满，不能入栈\n");
        return;
    }
    s->top = s->top + 1;  // top 上移
    s->array[s->top] = data;  // 放入数据
}

// 出栈
int pop(struct Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空，不能出栈\n");
        return -1;  // 返回错误值
    }
    int data = s->array[s->top];  // 取出数据
    s->top = s->top - 1;  // top 下移
    return data;
}

// 查看栈顶
int peek(struct Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        return -1;  // 返回错误值
    }
    return s->array[s->top];
}

// 测试代码
int main() {
    struct Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("栈顶: %d\n", peek(&s));  // 输出 30

    int data = pop(&s);
    printf("出栈: %d\n", data);  // 输出 30

    printf("栈顶: %d\n", peek(&s));  // 输出 20

    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布