adt stack在c语言中如何实现？

ADT (Abstract Data Type)，即抽象数据类型，是一种描述数据结构的方式，它只定义了数据的逻辑特性和操作（如创建、销毁、插入、删除、查找等），而不关心这些操作的具体实现细节。

栈 是一种经典的 ADT，它遵循 后进先出 的原则，就像一摞盘子，你最后放上去的盘子，会最先被拿走。

ADT 栈的逻辑定义

我们定义“栈”这个 ADT 应该包含什么。

1 数据

• 一个线性元素的集合。
• 栈顶：允许插入和删除的一端。
• 栈底：固定的一端。

2 操作

• Stack createStack(int size): 创建一个指定大小的空栈。
• void push(Stack s, ElementType item): 将一个元素压入栈顶。
• ElementType pop(Stack s): 弹出并返回栈顶元素。
• ElementType peek(Stack s): 查看栈顶元素，但不移除它。
• int isEmpty(Stack s): 判断栈是否为空。
• int isFull(Stack s): 判断栈是否已满。
• void destroyStack(Stack s): 销毁栈，释放内存。

C 语言实现 ADT 栈

在 C 语言中，我们通常使用 头文件 来定义 ADT 的接口（结构体和函数原型），使用 源文件 来实现这些函数，这样做可以实现信息隐藏，用户只需要知道如何使用 stack.h，而不需要关心 stack.c 内部的实现细节。

1 栈的头文件 (stack.h)

这个文件定义了 ADT 的“蓝图”，它告诉使用者：栈是什么样的，以及可以对栈进行哪些操作。

// stack.h
#ifndef STACK_H
#define STACK_H
// 定义栈中元素的类型，可以根据需要修改
typedef int ElementType;
// 定义栈结构体
// 我们在这里使用结构体来封装栈的所有数据和操作
typedef struct {
    ElementType *data; // 指向存储元素的动态数组
    int top;           // 栈顶指针，指向栈顶元素的位置
    int capacity;      // 栈的容量
} Stack;
// 函数声明 (ADT 的操作接口)
// 创建一个指定容量的栈
Stack createStack(int capacity);
// 压入元素
void push(Stack *s, ElementType item);
// 弹出元素
ElementType pop(Stack *s);
// 查看栈顶元素
ElementType peek(Stack *s);
// 判断栈是否为空
int isEmpty(Stack *s);
// 判断栈是否已满
int isFull(Stack *s);
// 销毁栈，释放内存
void destroyStack(Stack *s);
#endif // STACK_H

关键点解释:

• #ifndef ... #define ... #endif：这是 C 语言的头文件保护，防止同一个头文件被重复包含。
• typedef int ElementType;：我们定义 ElementType 为 int，如果你想栈存储其他类型的数据（如 char, float 或自定义结构体），只需修改这一行即可，非常方便。
• struct Stack { ... }：这是栈的核心。
  • ElementType *data：使用动态数组来存储元素，这使得栈的大小可以灵活变化。
  • int top：top 指针的初始值通常为 -1，当 top == -1 时，栈为空，当 top == capacity - 1 时，栈已满。
  • int capacity：记录数组的最大长度。
• *为什么函数参数是 `Stack s而不是Stack s`？**
  • 因为 push、pop 等操作会修改栈的内容（如 top 指针，或者 data 数组中的值）。
  • 在 C 语言中，结构体作为参数传递时，默认是值传递，即会创建一个副本，修改副本不会影响原始的栈对象。
  • 为了直接修改原始栈,我们必须传递指针，即 Stack *。

2 栈的实现文件 (stack.c)

这个文件包含了 stack.h 中声明的所有函数的具体实现逻辑。

// stack.c
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
// 创建栈
Stack createStack(int capacity) {
    Stack s;
    s.data = (ElementType *)malloc(capacity * sizeof(ElementType));
    if (s.data == NULL) {
        fprintf(stderr, "内存分配失败!\n");
        exit(EXIT_FAILURE);
    }
    s.top = -1;       // 空栈时，top 指向 -1
    s.capacity = capacity;
    return s;
}
// 判断栈是否已满
int isFull(Stack *s) {
    return s->top == s->capacity - 1;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}
// 压入元素
void push(Stack *s, ElementType item) {
    if (isFull(s)) {
        fprintf(stderr, "栈已满，无法压入元素!\n");
        return; // 或者可以选择动态扩容
    }
    s->top++;
    s->data[s->top] = item;
}
// 弹出元素
ElementType pop(Stack *s) {
    if (isEmpty(s)) {
        fprintf(stderr, "栈为空，无法弹出元素!\n");
        // 通常这里应该有错误处理，比如返回一个特殊值或退出程序
        // 这里简单返回一个0，实际应用中可能需要更健壮的方式
        return -1; 
    }
    ElementType item = s->data[s->top];
    s->top--;
    return item;
}
// 查看栈顶元素
ElementType peek(Stack *s) {
    if (isEmpty(s)) {
        fprintf(stderr, "栈为空，无法查看栈顶元素!\n");
        return -1; // 同上，错误处理
    }
    return s->data[s->top];
}
// 销毁栈
void destroyStack(Stack *s) {
    free(s->data);
    s->data = NULL;
    s->top = -1;
    s->capacity = 0;
}

3 使用示例 (main.c)

这个文件展示了如何使用我们刚刚创建的 ADT 栈，它只需要包含 stack.h，而不需要关心 stack.c 的内部实现。

// main.c
#include <stdio.h>
#include "stack.h"
int main() {
    // 创建一个容量为 5 的栈
    Stack myStack = createStack(5);
    printf("将 10, 20, 30 压入栈中...\n");
    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);
    // 查看栈顶元素
    printf("栈顶元素是: %d\n", peek(&myStack)); // 应该输出 30
    // 弹出元素
    printf("弹出元素: %d\n", pop(&myStack));   // 应该输出 30
    printf("弹出元素: %d\n", pop(&myStack));   // 应该输出 20
    // 再次压入元素
    printf("将 40 压入栈中...\n");
    push(&myStack, 40);
    printf("当前栈顶元素是: %d\n", peek(&myStack)); // 应该输出 40
    // 弹出所有剩余元素
    printf("弹出所有剩余元素...\n");
    while (!isEmpty(&myStack)) {
        printf("弹出: %d\n", pop(&myStack));
    }
    // 尝试从空栈弹出
    printf("尝试从空栈弹出...\n");
    pop(&myStack);
    // 销毁栈
    destroyStack(&myStack);
    printf("栈已销毁，\n");
    return 0;
}

如何编译和运行

你需要将这三个文件放在同一个目录下,然后使用 gcc 进行编译：

# 将 .c 文件编译成目标文件
gcc -c stack.c -o stack.o
gcc -c main.c -o main.o
# 将目标文件链接成可执行文件
gcc stack.o main.o -o stack_program
# 运行程序
./stack_program

预期输出:

将 10, 20, 30 压入栈中...
栈顶元素是: 30
弹出元素: 30
弹出元素: 20
将 40 压入栈中...
当前栈顶元素是: 40
弹出所有剩余元素...
弹出: 40
弹出: 10
尝试从空栈弹出...
栈为空，无法弹出元素!
栈已销毁。

总结与扩展

• ADT 的核心思想：将数据（data 数组）和操作（push, pop 等）封装在一起（struct Stack），并通过清晰的接口（stack.h）暴露给用户，用户只需要知道“做什么”，而不需要知道“怎么做”。
• 优点：
  • 模块化：代码结构清晰，易于维护。
  • 信息隐藏：用户无法意外地破坏栈的内部结构（不能直接修改 top 指针）。
  • 可重用性：stack.h 和 stack.c 可以被任何项目使用，只要需要栈结构。
• 扩展：
  • 动态扩容：当 isFull(s) 为真时，可以创建一个更大的新数组，将旧数组的数据复制过去，然后释放旧数组，这是许多标准库（如 C++ 的 std::vector）采用的方式。
  • 链表实现：除了用数组实现，栈也可以用链表来实现，链表实现的栈可以没有容量上限，但需要额外的指针域开销。
  • 错误处理：pop 和 peek 在栈为空时的处理可以更健壮，例如通过返回指针或设置全局错误码，而不是简单地打印信息。