搜索
C语言

C语言seqstacks如何实现栈的基本操作？

99ANYc3cd6
99ANYc3cd6 / / 0 评论 / 2 阅读
作者有点忙，还没来得及写简介......
预计阅读时长 26 分钟
位置： 首页 › C语言 › 正文

顺序栈是栈的一种最简单、最直观的实现方式，它利用数组来存储栈中的元素，并通过一个指针来记录栈顶元素的位置。

什么是栈？

在深入代码之前,我们必须先理解栈这个数据结构。

栈是一种后进先出 的线性数据结构,这就像一摞盘子或者一枪子弹夹：

  • 入栈：你只能把新盘子放在最上面，或者把新子弹压入弹夹的顶部，在数据结构中，这叫 push 操作。
  • 出栈：你也只能从最上面拿走盘子，或者打出最顶上的子弹，这叫 pop 操作。
  • 栈顶：允许进行插入和删除操作的一端。
  • 栈底：固定的一端,不允许进行操作。

顺序栈的设计与实现

顺序栈的核心思想就是用数组来模拟这个“盘子堆”。

1 栈的结构体定义

我们需要一个结构体来封装栈的所有信息：

  1. data: 一个数组,用于存储栈中的元素。
  2. top: 一个整数，作为栈顶指针，它指向最后一个有效元素的下一个位置，这是一种常见的实现方式，可以简化 push 和 pop 的逻辑。
  3. capacity: 数组的最大容量，用于判断栈是否已满,防止溢出。
// 定义栈中元素的数据类型，这里用 int 作为示例
// 如果需要存储其他类型（如 char, float, struct 等），只需修改这里即可
typedef int SElemType;
// 顺序栈的结构体定义
typedef struct {
    SElemType *data;      // 动态分配的数组，存储栈元素
    int top;              // 栈顶指针，指向栈顶元素的下一个位置
    int capacity;         // 栈的最大容量
} SeqStack;

2 核心操作函数

下面是实现顺序栈所需的各种函数。

2.1 初始化栈

创建一个空栈，我们需要为 data 数组在堆上动态分配内存，并将 top 初始化为 0（表示栈为空），capacity 设置为一个初始值。

#include <stdio.h>
#include <stdlib.h> // 用于 malloc 和 free
// 初始化栈
void InitStack(SeqStack *S, int initialCapacity) {
    S->data = (SElemType *)malloc(initialCapacity * sizeof(SElemType));
    if (!S->data) {
        printf("内存分配失败！\n");
        exit(1);
    }
    S->top = 0;      // 栈顶指针初始化为0，表示空栈
    S->capacity = initialCapacity;
    printf("栈初始化成功，初始容量为 %d，\n", initialCapacity);
}

2.2 销毁栈

当栈不再使用时，需要释放动态分配的内存,防止内存泄漏。

// 销毁栈，释放内存
void DestroyStack(SeqStack *S) {
    free(S->data);
    S->data = NULL;
    S->top = 0;
    S->capacity = 0;
    printf("栈已销毁，\n");
}

2.3 判断栈是否为空

top 指针为 0,说明栈中没有元素。

// 判断栈是否为空
int IsEmpty(SeqStack S) {
    return S.top == 0;
}

2.4 判断栈是否已满

top 指针等于 capacity，说明数组已满,无法再添加新元素。

// 判断栈是否已满
int IsFull(SeqStack S) {
    return S.top == S.capacity;
}

2.5 入栈

将一个新元素压入栈顶。

  1. 检查栈是否已满，如果已满，可以返回错误，或者进行扩容（这里我们先做简单处理，返回错误）。
  2. 将新元素存入 data[top] 的位置。
  3. 栈顶指针 top 自增 1。
// 入栈
int Push(SeqStack *S, SElemType e) {
    // 检查栈是否已满
    if (IsFull(*S)) {
        printf("栈已满，无法入栈！\n");
        return 0; // 入栈失败
    }
    // 1. 将元素放入栈顶
    S->data[S->top] = e;
    // 2. 栈顶指针上移
    S->top++;
    printf("元素 %d 入栈成功，\n", e);
    return 1; // 入栈成功
}

2.6 出栈

从栈顶弹出一个元素。

  1. 检查栈是否为空，如果为空,则无法出栈。
  2. 栈顶指针 top 自减 1。
  3. 取出 data[top] 位置的元素。
// 出栈
int Pop(SeqStack *S, SElemType *e) {
    // 检查栈是否为空
    if (IsEmpty(*S)) {
        printf("栈为空，无法出栈！\n");
        return 0; // 出栈失败
    }
    // 1. 栈顶指针下移
    S->top--;
    // 2. 取出栈顶元素
    *e = S->data[S->top];
    printf("元素 %d 出栈成功，\n", *e);
    return 1; // 出栈成功
}

2.7 获取栈顶元素

只查看栈顶元素,但不将其弹出。

// 获取栈顶元素
int GetTop(SeqStack S, SElemType *e) {
    if (IsEmpty(S)) {
        printf("栈为空，没有栈顶元素！\n");
        return 0;
    }
    *e = S.data[S.top - 1]; // 栈顶元素在 top-1 的位置
    printf("栈顶元素是: %d\n", *e);
    return 1;
}

完整示例代码

下面是一个完整的 C 程序,演示了如何使用上面定义的顺序栈。

#include <stdio.h>
#include <stdlib.h>
// 定义栈中元素的数据类型
typedef int SElemType;
// 顺序栈的结构体定义
typedef struct {
    SElemType *data;
    int top;
    int capacity;
} SeqStack;
// 函数声明
void InitStack(SeqStack *S, int initialCapacity);
void DestroyStack(SeqStack *S);
int IsEmpty(SeqStack S);
int IsFull(SeqStack S);
int Push(SeqStack *S, SElemType e);
int Pop(SeqStack *S, SElemType *e);
int GetTop(SeqStack S, SElemType *e);
void PrintStack(SeqStack S);
int main() {
    SeqStack myStack;
    SElemType value;
    // 1. 初始化栈
    InitStack(&myStack, 5);
    // 2. 入栈操作
    Push(&myStack, 10);
    Push(&myStack, 20);
    Push(&myStack, 30);
    Push(&myStack, 40);
    Push(&myStack, 50); // 此时栈已满
    // 尝试再入栈，会失败
    Push(&myStack, 60);
    // 3. 查看栈顶元素
    GetTop(myStack, &value);
    // 4. 出栈操作
    Pop(&myStack, &value);
    Pop(&myStack, &value);
    // 再次查看栈顶元素
    GetTop(myStack, &value);
    // 5. 打印当前栈内元素 (从栈顶到栈底)
    printf("\n当前栈内元素 (从栈顶到栈底): ");
    PrintStack(myStack);
    // 6. 销毁栈
    DestroyStack(&myStack);
    return 0;
}
// --- 函数实现 ---
void InitStack(SeqStack *S, int initialCapacity) {
    S->data = (SElemType *)malloc(initialCapacity * sizeof(SElemType));
    if (!S->data) {
        printf("内存分配失败！\n");
        exit(1);
    }
    S->top = 0;
    S->capacity = initialCapacity;
    printf("栈初始化成功，初始容量为 %d，\n", initialCapacity);
}
void DestroyStack(SeqStack *S) {
    free(S->data);
    S->data = NULL;
    S->top = 0;
    S->capacity = 0;
    printf("栈已销毁，\n");
}
int IsEmpty(SeqStack S) {
    return S.top == 0;
}
int IsFull(SeqStack S) {
    return S.top == S.capacity;
}
int Push(SeqStack *S, SElemType e) {
    if (IsFull(*S)) {
        printf("栈已满，无法入栈！\n");
        return 0;
    }
    S->data[S->top] = e;
    S->top++;
    printf("元素 %d 入栈成功，\n", e);
    return 1;
}
int Pop(SeqStack *S, SElemType *e) {
    if (IsEmpty(*S)) {
        printf("栈为空，无法出栈！\n");
        return 0;
    }
    S->top--;
    *e = S->data[S->top];
    printf("元素 %d 出栈成功，\n", *e);
    return 1;
}
int GetTop(SeqStack S, SElemType *e) {
    if (IsEmpty(S)) {
        printf("栈为空，没有栈顶元素！\n");
        return 0;
    }
    *e = S.data[S.top - 1];
    printf("栈顶元素是: %d\n", *e);
    return 1;
}
// 辅助函数：打印栈内容（注意：这会改变栈的状态，实际应用中应谨慎）
void PrintStack(SeqStack S) {
    if (IsEmpty(S)) {
        printf("栈为空，\n");
        return;
    }
    // 为了打印，我们创建一个临时指针
    int tempTop = S.top;
    while (tempTop > 0) {
        printf("%d ", S.data[tempTop - 1]);
        tempTop--;
    }
    printf("\n");
}

代码运行结果分析：

栈初始化成功，初始容量为 5。
元素 10 入栈成功。
元素 20 入栈成功。
元素 30 入栈成功。
元素 40 入栈成功。
元素 50 入栈成功。
栈已满，无法入栈！
栈顶元素是: 50
元素 50 出栈成功。
元素 40 出栈成功。
栈顶元素是: 30
当前栈内元素 (从栈顶到栈底): 30 20 10 
栈已销毁。

顺序栈的优缺点

优点：

  1. 实现简单：基于数组，逻辑直观,易于理解和实现。
  2. 效率高：入栈和出栈操作的时间复杂度均为 O(1)，因为它们只涉及数组的索引访问和指针的移动,非常快。

缺点：

  1. 容量固定：在初始化时需要指定容量，如果容量设置过小，可能导致栈溢出；如果设置过大,则会浪费内存。
  2. 扩容麻烦：虽然可以通过 realloc 动态扩容，但这涉及到重新分配内存和数据拷贝，会降低性能,并且需要处理复杂的边界情况。

进阶：动态扩容的顺序栈

为了克服容量固定的缺点，我们可以实现一个可以自动扩容的顺序栈，当栈满时，我们创建一个更大的新数组（通常是容量的2倍），将旧数组的数据拷贝到新数组中,然后释放旧数组的内存。

// 动态扩容的入栈函数
int PushWithResize(SeqStack *S, SElemType e) {
    // 检查栈是否已满
    if (IsFull(*S)) {
        printf("栈已满，正在尝试扩容...\n");
        // 1. 创建一个新数组，容量是原来的2倍
        int newCapacity = S->capacity * 2;
        SElemType *newData = (SElemType *)realloc(S->data, newCapacity * sizeof(SElemType));
        if (!newData) {
            printf("扩容失败！内存不足，\n");
            return 0; // 扩容失败
        }
        // 2. 更新栈的结构体信息
        S->data = newData;
        S->capacity = newCapacity;
        printf("扩容成功！新容量为 %d，\n", newCapacity);
    }
    // 3. 正常入栈
    S->data[S->top] = e;
    S->top++;
    printf("元素 %d 入栈成功，\n", e);
    return 1;
}

使用这个新的 PushWithResize 函数，你的栈就能在需要时自动增长,变得更加灵活和健壮。

-- 展开阅读全文 --
头像
void参数在C语言中如何使用？
« 上一篇 03-26
dede ajax提交
下一篇 » 03-26

相关文章

取消
微信二维码
支付宝二维码

目录[+]