Implement an array of stacks in C

Question

Implement an array of stacks where stacks are defined :

typedef struct StackNode {

   int data;

   StackNode* next;

} StackNode;

Each array element points to a stack, each stack is initialized as an empty stack. When you start adding elements it will start adding them to the stack in Stacks[0]; if you say -2 in stdin and then 4 for example, the next entries will go to Stacks[4];

For example:

5 10 -2 3 9 7 89 -1
will result in :
Stacks[0] -> 10 -> 5
Stacks[1]
Stacks[2]
Stacks[3] -> 89 -> 7 -> 9

-1 will stop the code from running.

I am having problem with implementing an array of stacks so any help would be appreciated :)

Answer 1

In line 3 of

typedef struct StackNode {
   int data;
   StackNode* next;          /* line 3 */
} StackNode;

the type StackNode does not yet exist. The type StackNode only begins to exist once the type struct StackNode is fully parsed.

But the type struct StackNode already exists at that point. It is still incomplete, but you can declare pointers to it.

typedef struct StackNode {
   int data;
   struct StackNode* next;          /* line 3 */
} StackNode;

Answer 2

This doesn't look like a stack, it looks like a linked list. Of course you can implement stack-like semantics using a linked list, but it's generally not what is meant by "a stack".

To push a new number, you would need to:

• Allocate a new StackNode.
• Initialize it with the new number.
• Link it to the previous.

You could encapsulate this into a function:

void stack_push(StackNode *root, int value)
{
    /* Code omitted */
}

Then you'd just need to provide the proper stack in order to control onto which of your many stacks to push the new number:

stack_push(&Stacks[2], 4711);

Answer 3

If you go to the bottom of this Wikipedia article, you'll see an example of what I think you are trying to implement. What you have is a linked list. Additionally, here are some handy doubly linked list helpers which might serve as example.

If you post the actual usage of your code as-is, you might receive a better (more specific) answer.

Answer 4

You must first get an array of StackNodes:

StackNode ** stacks = malloc(sizeof(StackNode*) * 5); /* allocate 5 stack nodes */
stacks[0] = malloc(sizeof(StackNode)); /* allocate first stack */
...

Now you have a function push(StackNode *, int value). To push on a certain stack, call it with push(stacks[2], value) (to push on the third stack, for example).

Answer 5

int t = 0, index = 0;
while(t != -1)
{
  scanf("%d", &t);
  if(t == -2)
  {
    scanf("%d", &t);
    index = t;
    continue;
  }
  if(t >= 0)
    push(stacks[index], t);
}