6
\$\begingroup\$

Below is my implementation of a stack in C. Is it correct? And/or is there anything that I should fix to make it better in any way?

stack.h

#ifndef STACK_H
#define STACK_H

#define EMPTY_STACK -1
typedef struct stack
{
  char ch;
  struct stack* prev;
} Stack;

extern Stack* init_stack(void);
extern char pop(Stack*);
extern void push(Stack*, char);

#endif

stack.c

#include "stack.h"
#include "stdlib.h"

Stack* init_stack()
{
  Stack* ret = (struct stack*)malloc(sizeof(struct stack));
  ret->prev = NULL;
  return ret;
}

char pop (Stack* stck)
{
  char ret;
  if (stck->prev)
  {
    ret = stck->ch;
    Stack* prv = stck->prev;
    stck->prev = prv->prev;
    stck->ch = prv->ch;
    free(prv);
    return ret;
  }
  else
    return EMPTY_STACK;
}

void push (Stack* stck, char ch)
{
  Stack* new_nd = (struct stack*)malloc(sizeof(struct stack));

  new_nd->prev = stck->prev;
  new_nd->ch = stck->ch;

  stck->prev = new_nd;
  stck->ch = ch;
}

Thanks!

\$\endgroup\$
6
\$\begingroup\$

I would advise you not implementing stacks with a linked list because for each char of info you consume 2 * sizeof(void*) because of memory alignment in your struct.

Because of this you won't be able to handle a big amount of data.

What happens if you push EMPTY_STACK ? Your pop will return a false EMPTY_STACK when going through the if. Isn't there a better way to handle this ?

\$\endgroup\$
3
\$\begingroup\$

Because your init_struct returns a struct that has no data, I think you need to set the data value:

ret->ch = EMPTY_STACK;

push() should then be modified to see if the char is currently EMPTY_STACK and if so, that should be updated, with no new struct allocated.

void push (Stack* stck, char ch)
{
   if ( stck->ch == EMPTY_STACK )
   {
      stck->ch = ch;
      return;
   }  

pop() should also deal with a struct that has no data:

char pop (Stack* stck)
{
  char ret = stck->ch;
  if (stck->prev)
  {
    Stack* prv = stck->prev;
    stck->prev = prv->prev;
    stck->ch = prv->ch;
    free(prv);
  }
  else
     /* set the stack to empty */
     stck->ch = EMPTY_STACK;
  return ret;
}

You might want to add a check for a NULL pointer passing in to push() and pop() as well.

I think the easiest way to do a stack is to have a struct that contains a pointer to your data, which gets the output of malloc() from stack_init() and realloc(), if necessary from push(). You also keep an int in the struct that keeps track of the current size of the stack, and probably the current allocated size.

struct stack {
   char *data;
   int items;
   int allocated_size;
}

Alternatively, there can be two structs. One for the base of the stack, and another to hold the data of the stack.

struct stack_node  {
     char ch;
     struct stack_node* prev;
}

struct stack {
     struct stack_node* top;
     int size;
}
\$\endgroup\$
1
\$\begingroup\$
#define EMPTY_STACK -1

This is weird. Maybe instead of returning a magic value, your pop function should have a different interface. For example, maybe your pop function has an output parameter (pointer) which receives the popped value, and returns a boolean indicating whether or not a value was popped.

Stack* ret = (struct stack*)malloc(sizeof(struct stack));

You are speaking C with a C++ accent. You do not need to cast from void * to struct stack*. Leave out the cast.

Stack* ret = (struct stack*)malloc(sizeof(struct stack));
ret->prev = NULL;

malloc can return NULL. In this case the next line will dereference a NULL pointer and crash. You should check for errors, then return some kind of failure status to the caller, which the caller should also react to.

You also have a init_stack which does allocations but no corresponding free_stack which frees it.

Come to think of it... Does init_stack really need to allocate? Maybe it should take a caller-allocated buffer. For example an interface like:

struct stack stack;

init_stack(&stack);

push(&stack, 1);    // XXX - there should be a way to check for errors here.

This also brings to mind... Why a vague name like push? C does not have namespaces and this is a name that could clash with others. Maybe it should be stack_push. Also more consistent with some of your other function names.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.