Making Multiple Stacks

Question

I wanted to make an array of stacks in C, where I should be able to retain individual stacks and their respective information. I currently have the following implementation, which only works for one stack. How can I modify the functions push and pop to achieve multiple stacks each using the same function. (I was easily able to do this in Java, as I could create a class, but I have no idea in C)

    #include <stdio.h>
    #include <stdlib.h>

    struct node {
        int data;
        struct node *next;
    };

    struct node *first = NULL;

    void push(int x) {
        struct node *newnode = malloc(sizeof(struct node));
        newnode->data = x;
        newnode->next = first;
        first = newnode;
    }

    int pop() {
        int temp = first->data;
        first = first->next;
        return temp;
    }

Answer 1

The static implemetation of two stacks in a single array in C looks something like this...the stack structure will have two top variables top1 and top2.

struct stack
{
  int data[MAX];
  int top1,top2;
}s;

top1 is initialized to -1 while top2 is initialized to MAX

Overflow condtitions: 1]

if((s->top1)+1==s->top2)
    printf("Stack 1 overflow\n");

2]

 if((s->top2)-1==s->top1)
    printf("Stack 2 overflow\n");

The underflow conditions become pretty obvious. This method may not be memory efficient since we might run out of storage space in the array but it is the basic fundamentals of multiple stacks in a single array.

Answer 2

You have a memory leak in your code in the pop() function. You should free the memory that you have malloc'd.

Taking advice from @Jongware's comments below your question.

Here's a new version of the push() and pop() functions.

#include <stdlib.h>

struct node {
    int data;
    struct node *prev;
};

void push(struct node **stack, int x) {
    if (stack != NULL)
    {
        struct node *newnode = malloc(sizeof(struct node));
        newnode->data = x;
        newnode->prev = *stack;
        *stack = newnode;
    } else
    {
        // You didn't give me a valid pointer to a stack, so I'm ignoring you!
    }
}

int pop(struct node **stack) {
    int temp = 0; // This is the default value that is returned when there is an error.
    struct node *oldnode;

    if (stack != NULL)
    {
        if (*stack != NULL)
        {
            oldnode= *stack;
            temp = oldnode->data;
            (*stack) = oldnode->prev;
            free(oldnode);
        } else
        {
            // The stack is empty. I will just ignore you and return the default value for temp.
        }
    } else
    {
        // You didn't give me a valid pointer to a stack so I'm ignoring you and returning the default value of 0 for temp!
    }

    return temp;
}

And here's an example of how to use them:

#include <stdio.h>

int main()
{
    struct node *stack1 = NULL, *stack2 = NULL;
    int value;

    // Push some values onto the stacks
    printf("Pushing 7 and then 8 onto stack1\n");
    push(&stack1, 7);
    push(&stack1, 8);

    printf("Pushing 3 onto stack2\n");
    push(&stack2, 3);

    // Pop and print both stacks
    value = pop(&stack2);
    printf("Popped %d from stack2\n", value);

    value = pop(&stack1);
    printf("Popped %d from stack1\n", value);
    value = pop(&stack1);
    printf("Popped %d from stack1\n", value);

    return 0;
}

As for where you should be declaring your stack pointers that is really up to you and how you intend to use them.

Have a read about C variable scope for some options and how you might use them.

Also, I will have to include a warning with declaring these pointers inside functions. In whichever function you declare your pointer you must make sure that you pop everything off the stack before you exit the function, otherwise you will lose the pointer and leak all the allocated memory. If this is not what you want, or you want the pointer to outlive the function then you can declare the pointer globally or pass it around, making sure that everything is popped off the stack before your program exists or loses the pointer.

Another thing that you might want to consider is what happens when you use pop() on an empty stack? The implementation that I have given you simply returns 0 and ignores you. You might want to handle that a little better.

Answer 3

You can only have one stack because you defined it as a global variable:

struct node *first = NULL;

In Java you would have used a class. In C, you can likewise do "object based" programming by defining an abstract data type which holds your instance variables, instead of using global variables:

struct stack {
  struct node *first;
};

there are no class features like constructors or destructors, so you write functions to initialize a stack, destroy a stack and so forth. To achieve multiple instantiation, you explicitly pass a stack * argument to each function in the stack module. You might want to name your functions in some consistent way, like stack_init, stack_cleanup, stack_push and so on.

There are design questions to settle such as: does the caller allocate struct stack, for which you provide stack_init function? Or do you provide a one-step stack_alloc function that allocates and returns a stack? Or perhaps both, so the user can choose performance or convenience?

void stack_init(struct stack *);
void stack_cleanup(struct stack *);

struct stack *stack_alloc(void); /* also calls stack_init on new stack */
void stack_free(struct stack *); /* calls stack_cleanup, then frees */

It's possible to do information hiding in C, whereby you can completely conceal from the client code (which uses the stack module) what a struct stack is.

However, if you provide a stack_init, then the client has to know how large a stack is, since it provides the memory for it. Generally, modules which completely hide an implementation also hide how large it is, and so provide only a stack_alloc and stack_free type interface.

An advantage of that is that client code doesn't have to be recompiled if the stack module is changed and the structure is larger. This is very good if you're writing a widely-used library: it is easy for users to upgrade or possibly downgrade.

However, revealing the implementation allows for more efficient code, since the client has the freedom to choose memory management for stacks. Stacks can be declared as local variables in automatic storage ("on the stack", so to speak), statically as global variables, or packed into arrays.

The user can do things like:

{
  struct stack temp_stack;

  stack_init(&temp_stack); /* stack is good to go! */

  /* ... use stack ... */

  stack_cleanup(&temp_stack); /* don't forget to clean up */
}

and things like:

struct stack array_of_stacks[42];
int i;

for (i = 0; i < 42; i++)
  stack_init(&array_of_stacks[i]); /* no memory allocation taking place */

All this code has a compile-time dependency of the definition of struct stack; whenever struct stack is touched, it must be recompiled.

Note that if the above struct stack definition is the exact definition for a stack (the only property of a stack is that it has a pointer to a top node which can be null) then, physically speaking, a struct stack * pointer is actually a pointer to a pointer. We can use a typedef name to write the code so that we can use either definition:

/* Alternative "A" */
typedef struct node *stack_t; /* a stack_t type is a pointer to a node */

/* Alternative "B" */
typedef struct stack {
  struct node *top;
} stack_t; /* stack_t is a structure containing a pointer to a node */

Either way, the API in terms of stack_t then looks like this:

void stack_init(stack *s);
int stack_push(stack *s, int item);

or whatever. If stack is a pointer (alternative "A" above) then stack *s is a pointer-to-pointer, and so your code will be full of pointer-to-pointer manipulation.

If you're not comfortable with pointer-to-pointer syntax all over the place, then you can give yourself a macro to pretend that it's a structure anyway.

/* Alternative "A" */
typedef struct node *stack_t; /* a stack_t type is a pointer to a node */
#define stack_top(s) (*(s))   /* dereference stack s to obtain the top pointer */

/* Alternative "B" */
typedef struct stack {
  struct node *top;
} stack_t; /* stack_t is a structure containing a pointer to a node */
#define stack_top(s) ((s)->top)  /* dereference struct pointer to get top pointer */

In the code you can then do things like:

/* push new_node onto stack */

new_node->next = stack_top(s);
stack_top(s) = new_node;

If you consistently use the stack_top accessor, you can now flip the representation of the stack type between alternative "A" and "B" without rewriting any of your code (only recompiling it).

Some nit-picky C programmers will cringe at stack_top(s) = new_node since it looks like a function call is being assigned (which is impossible in C without using macros to bend the language), and prefer a "setter" function for that stack_top_set(s, new_node). That's mostly just outdated, parochial thinking.

Answer 4

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int Item;

#define ItemFormat "%d"

struct node {
    Item data;
    struct node *next;
};

typedef struct node *Stack;

void push(Stack *st, Item x){
    struct node *newnode = malloc(sizeof(struct node));
    newnode->data = x;
    newnode->next = *st;
    *st = newnode;
}

bool isEmpty(Stack st){
    return st == NULL;
}

Item pop(Stack *st) {
    if(!isEmpty(*st)){
        struct node *p = *st;
        Item value = p->data;
        *st = p->next;
        free(p);
        return value;
    }
    fprintf(stderr, "Stack is Empty!\n");
    return (Item)0;
}

bool inputItem(Item *x){
    int stat;
    if(1==(stat=scanf(ItemFormat, x)))
        return true;
    if(stat == EOF)
        return false;
    scanf("%*[^\n]");
    return false;
}

void printItem(Item x){
    printf(ItemFormat, x);
}

int main(void){
    Stack st = NULL, array[5] = { NULL };
    Item x;
    while(inputItem(&x)){
        push(&array[1], x);
    }
    while(!isEmpty(array[1])){
        x = pop(&array[1]);
        printItem(x);
        printf("\n");
    }
/*
    while(inputItem(&x)){
        push(&st, x);
    }
    while(!isEmpty(st)){
        x = pop(&st);
        printItem(x);
        printf("\n");
    }
*/
    return 0;
}