c - 链接栈和队列

Question

在一本书中遇到了 Linked Stacks and Queues(它不是​​使用链表的堆栈/队列实现)。它说，如果我们只有一个栈/队列，那么栈/队列可以顺序表示。但是，当多个栈/队列共存时，就没有有效的方法来顺序表示它们了。下面是给出的代码

#define MAX_STACKS 10 //maximum number of stacks;
typedef struct {
        int key;
        //other fields.
}element;
typedef struct stack *stackpointer;
typedef struct {
        element data;
        stackpointer link;
}stack;
stackpointer top[MAX_STACKS];

void push(int i ,element item) {
     stackpointer temp;
     malloc(temp,sizeof(*temp));
     temp->data = item;
     temp->link = top[i];
     top[i] = temp;
}

我是数据结构的新手。我可以得到上述概念的简要解释，即链接堆栈/队列。

Answer 1

所以我看了你的书，我有点明白你的问题是什么。

Such a representation proved efficient if we had only one stack or one queue. However, when several stacks and queues co−exist, there was noefficient way to represent them sequentially

所以说sequential，你要明白是用数组来表示栈，而不是链表。现在假设您有一个由 10 个数组组成的矩阵来表示每个数组的大小为 100，然后您将一些数据放入每个数组。假设您只在每个堆栈中压入几个元素，结果是您最终浪费了大量数据，因为矩阵中有 1000 个元素。这个问题在使用单个数组时存在，但当你有多个数组用于多个堆栈时，它会变得更加明显。

现在您可能已经理解，使用堆栈的链表表示会根据需要使用尽可能多的内存，只需要很少的开销来跟踪下一个元素，在本例中为堆栈指针链接。

堆栈指针顶部[MAX_STACKS]

所以我们在这里所做的是创建一个堆栈指针类型的数组来跟踪每个堆栈的顶部位置。所以现在每当用户希望输入一个元素时，他们必须传递索引(int i)以及数据(元素项)。

void push(int i ,element item) 
{
     stackpointer temp;
     malloc(temp,sizeof(*temp));
     temp->data = item;
     temp->link = top[i];
     top[i] = temp;
}

所以我们要做的是创建一个临时变量来存储我们的数据，它现在将成为我们堆栈的顶部但在这样做之前我们必须将它指向以前的堆栈顶部，(在第 5 行完成)和在第 6 行中，我们只是将 top[i] 指向 temp。但是，您可能想用这个更正您的代码

stackpointer temp = (stackpointer)malloc(sizeof(element));

如果有疑问，关于malloc，引用this即可.如果您有任何疑问，请告诉我，我会澄清您需要的一切。