堆栈和数据结构

Question

我是数据结构和算法的新手，我想问为什么需要通过结构体数据类型使用数组来实现堆栈我们可以直接制作全局pop和push函数，全局数组和top变量那么为什么我们创建一个结构体在该结构内部，我们声明一个 top 变量和一个数组指针。

我试图了解使用数组实现堆栈的方法有哪些优点或缺陷，一种方法是在结构内部声明数组，另一种方法是直接创建全局数组。

Answer 1

完整的答案需要很长很长的答案。它可以变成基于意见的例子（这在 SO 上是不受欢迎/禁止的。但下面我写了一些你新要考虑的事情。

你把两个不相关的东西混在一起了。使用结构体（a

struct

）并不妨碍您将堆栈设为全局变量。不使用结构并不妨碍您使用本地堆栈。

int stack_data[N];     // Global stack
int stack_size = 0;    // without a struct

struct stack {
    int data[N];
    int size;
};
struct stack stack = {0};   // Global stack using struct

void foo(void) {
    int foo_stack_data[N];     // Local stack
    int foo_stack_index = -1;  // without a struct
    ...
    ...
}

void bar(void) {
    struct stack bar_stack = {0};  // Local stack using struct
    ...
    ...
}

使用

struct

有几个原因。在

struct

中收集密切相关的变量，例如“堆栈数据”和“堆栈大小”，在许多情况下将使您的代码更易于阅读和维护。

举个例子，假设您的程序需要 100 个堆栈。如果没有

struct

，您将需要 2 * 100 = 200 行代码。使用

struct stack

，您只需要 100 行（加上 4 行定义）。随着与数据结构相关的变量数量的增加，情况会变得更糟。

如果您需要动态分配的堆栈，则只需使用

malloc

即可调用一次

struct

，而无需使用

malloc

，则需要 2 次

struct

调用。

全局变量....嗯，在某些情况下（几个）全局变量是有意义的。但是（几乎）广泛使用全局变量总是会导致混乱。一个好的规则是避免全局变量，除非你有一个非常有力的论据。

看这个：

int stack_data[N];     // Global stack
int stack_size = 0;    // without a struct

void push(int value) {
    // error check omitted
    stack_data[stack_size] = value;
    stack_size = stack_size + 1;
}

void bar(void) {
    push(42);
}

嗯...它会起作用的。 但是... 如果我需要两堆或八堆怎么办？那么我应该编写 8 版本的

push

函数吗？对我来说听起来不太有趣...

所以我这样做：

void push(int value, int* d, int* sz) {
    // error check omitted
    d[*sz] = value;
    *sz = *sz + 1;
}

void bar(void) {
    push(42, stack_data, &stack_size);
    push(65, another_stack_data, &another_stack_size);
}

传递堆栈相关变量可以让我拥有多个堆栈。

但是我必须同时传递数据和大小。两个论点。如果我需要 5 个变量来描述我的数据结构怎么办……那么我就必须传递 5 个参数。 除了所有的打字之外，它还会/可能会损害性能。

通过使用

struct

方法，我可以使用单个参数，即指向

struct

变量的指针：

void push(int value, struct stack *s) {
    // error check omitted
    s->data[s->size] = value;
    s->size = s->size + 1;
}

void bar(void) {
    struct stack stack1 = {0};
    push(42, &stack1);
    struct stack stack2 = {0};
    push(65, &stack2);
    ...
}