为什么队列和堆栈被声明为指针？

Question

我学习数据结构，而我没有得到为什么栈和队列需要声明如下：

struct stack *Stack; 

（忘了struct语法）

我的意思是，为什么它总是声明为指针？

Answer 1

他们并不总是这样宣布！

通常，将变量声明为指针对于稍后动态分配它非常有用。这可能是由于两个原因：

• 变量是太大程序堆栈
• 你想从一个函数

在你的情况下返回变量，让我们想到的栈的两种不同的实现：

struct stack 
{ 
    void *stuff[10000]; 
    int size; 
}; 

这是一个可怕的实现，但是假设你有一个这样的，那么你很可能不希望把它的程序堆栈。

或者，如果您有：

struct stack 
{ 
    void **stuff; 
    int size; 
    int mem_size; 
}; 

你动态地改变0​​大小无论如何，所以也绝对在程序堆栈，即这样的声明struct stack类型的变量没有坏处：

struct stack stack; 

除非你想从函数中返回它。例如：

struct stack *make_stack(int initial_size) 
{ 
    struct stack *s; 

    s = malloc(sizeof(*s)); 
    if (s == NULL) 
     goto exit_no_mem; 

    if (initial_size == 0) 
     initial_size = 1; 
    s->stuff = malloc(initial_size * sizeof(*s->stuff)); 
    if (s->stuff == NULL) 
     goto exit_no_stuff_mem; 

    s->size = 0; 
    s->mem_size = initial_size; 

    return s; 
exit_no_stuff_mem: 
    free(s); 
exit_no_mem: 
    return NULL; 
} 

就个人而言，虽然，我会宣布这样的功能：

int make_stack(struct stack *s, int initial_size); 

和程序栈上分配的struct stack。

Answer 2

不，他们不必被声明为指针。

人们可以以及分配栈和队列为全局变量：

struct myHash { int key; int next_idx; int data[4]; } mainTable[65536]; 
struct myHash duplicates[65536*10]; 
int stack[16384]; 

myHash也包括使用索引重复条目的链接列表。

但正如评论中所述，如果必须在结构中添加更多元素，那最初是计划好的，然后指针就会变得方便。

将结构声明为指针的另一个原因是它通常使用指针可以访问整个结构，结构的任何单独元素或元素的一些子集。这使得语法更通用。另外，当结构作为参数传递给某个外部函数时，指针是不可避免的。

Answer 3

这取决于您的堆栈结构是如何定义的（不仅仅是struct的布局，还包括操作它的操作）。

这是完全可能的，以限定堆叠作为一个简单的阵列和索引，如

struct stack_ { 
    T data[N]; // for some type T and size N 
    size_t stackptr; // Nobody caught that error, so it never existed, right? ;-) 
} stack; 

stack.stackptr = N; // stack grows towards 0 

// push operation 
if (stack.stackptr) 
    stack.data[--stack.stackptr] = some_data(); 
else 
    // overflow 

// pop operation 
if (stack.stackptr < N) 
    x = stack.data[stack.stackptr++]; 
else 
    // underflow 

然而，固定大小的阵列被限制。执行堆栈的一个简单的方法是使用一个列表结构：

struct stack_elem { 
    T data; 
    struct stack_elem *next; 
}; 

的想法是，列表的头是堆栈的顶部。将项目推入堆栈会在列表头部添加一个元素;弹出一个项目从列表中删除的头元素：

int push(struct stack_elem **stack, T data) 
{ 
    struct stack_elem *s = malloc(sizeof *s); 
    if (s) 
    { 
    s->data = data; // new element gets data 
    s->next = *stack; // set new element to point to current stack head 
    *stack = s;  // new element becomes new stack head 
    } 
    return s != NULL; 
} 

int pop(struct stack_elem **stack, T *data) 
{ 
    int stackempty = (*stack == NULL); 

    if (!stackempty) 
    { 
    struct stack_elem *s = *stack; // retrieve the current stack head 
    *stack = (*stack)->next;  // set stack head to point to next element 
    *data = s->data;    // get the data 
    free(s);      // deallocate the element 
    } 

    return r; 
} 

int main(void) 
{ 
    struct stack_elem *mystack = NULL; // stack is initially empty 
    T value; 
    ... 
    if (!push(&mystack, some_data())) 
    // handle overflow 
    ... 
    if (!pop(&mystack, &value)) 
    // handle underflow 
    ... 
} 

由于push和pop需要能够写入新的指针值mystack，我们需要一个指针传递给它，故名为双间接stack，push和pop。

Answer 4

真的不需要用指针来实现堆栈和队列 - 其他人已经清楚地说明了这个事实。查看@JohnBode关于如何使用数组完美实现堆栈的答案。问题在于，使用指针对某些数据结构（如堆栈，队列和链表）进行建模，可以让您在执行速度和内存消耗方面以非常有效的方式对它们进行编程。

如果您的用例需要对结构中的元素进行频繁的随机访问（假定它是位置索引（这是FAST与数组）），通常用于保存数据结构的底层数组是非常好的实现选择。然而，增加结构超过其初始容量可能会很昂贵，并且会浪费阵列中未使用的元素的内存。插入和删除操作也可能非常昂贵，因为您可能需要重新安排元素以缩小结构或为新元素腾出空间。

由于队列和堆栈没有此随机接入要求，因此您不需要在它们中间插入或删除元素，因此“动态地动态分配每个单独元素是更好的实施选择“，在需要新元素时请求内存（这是malloc的功能），并且将元素释放为元素将被删除。这很快，并且不会消耗比您数据结构实际需要的更多的内存。

Answer 5

正如aleady指出，它取决于结构有多大。

另一个原因是封装。堆栈实现可能不会在其头文件中公开结构堆栈的定义。这隐藏了用户的实现细节，缺点是需要免费的商店分配。