4
\$\begingroup\$

Follow up of - Which is a better implementation of a stack data structure (based on an array)?

Please review my stack implementation from before. I've made it dynamically sized if needed and made a few tweaks.

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

typedef struct
{
    int *elementData;
    unsigned int stackSize;
    unsigned int capacityIncrement;
    unsigned int elementCount;
} Stack;

void initializeStack(Stack*, unsigned int, unsigned int);
void stackPush(Stack*, int);
int stackPop(Stack*);
int stackPeek(Stack*);
bool isStackEmpty(const Stack*);
void setCapacityIncrement(Stack*, unsigned int);
int getNumberOfElements(const Stack*);
int getStackSize(const Stack*);

int main()
{
    Stack s1;
    initializeStack(&s1, 4, 10);
    for(int i = 0; i < 25; i++)
    {
        stackPush(&s1, i + 1);
    }
    stackPop(&s1);
    stackPush(&s1, 88);
    stackPush(&s1, 25);
    printf("The top of the stack is %d.\n", stackPeek(&s1));
    while(!isStackEmpty(&s1))
    {
        int top = stackPop(&s1);
        printf("Popping %d from the top of the stack.\n", top);
    }
    return 0;
}

void initializeStack(Stack *p, unsigned int stackSize, unsigned int capacityIncrement)
{
    p->elementData = calloc(stackSize, sizeof(int));
    p->stackSize = stackSize;
    p->capacityIncrement = capacityIncrement;
    p->elementCount = 0;
}

void stackPush(Stack *p, int value)
{
    if (p->elementCount == p->stackSize)
    {
        p->stackSize *= p->capacityIncrement; 
        p->elementData = (int*)realloc(p->elementData, sizeof(int) * p->stackSize);
    }
    p->elementData[p->elementCount] = value;
    p->elementCount++;
}

int stackPop(Stack *p)
{
    if (!isStackEmpty(p))
    {
        p->elementCount--;
        return p->elementData[p->elementCount];
    }
    fputs("ERROR : Stack is empty!", stderr);
    return 0;
}

int stackPeek(Stack *p)
{
    if (!isStackEmpty(p))
    {
        p->elementCount--;
        int topValue = p->elementData[p->elementCount];
        p->elementCount++;
        return topValue;
    }
    fputs("ERROR : Stack is empty!", stderr);
    return 0;
}

bool isStackEmpty(const Stack *p)
{
    return p->elementCount == 0;
}

void setCapacityIncrement(Stack *p, unsigned int capacityIncrement)
{
    p->capacityIncrement = capacityIncrement;
}

int getNumberOfElements(const Stack *p)
{
    return p->elementCount;
}

int getStackSize(const Stack *p)
{
    return p->stackSize;
}
\$\endgroup\$
3
\$\begingroup\$

First of all, bad naming.

Try prefixing everything with stack, this makes it a bit more useful as a library where you won't name clash

  • stack_count
  • stack_top
  • stack_push
  • stack_pop
  • stack_is_empty

etc

A lot of stack implementations now don't let pop both return a value and change the stack. It goes against CQS (Command Query Separation). Instead, just use top to get the the top of the stack, and pop simply removes one if one exists.

Your reallocs need to be tested to see if they work, if not, handle the situation nicely rather than the havoc that currently will happen.

Don't use fputs(). A stack should have no dependencies on a "UI"

you should have a stack_destroy which free's up your stack memory.

Bad things will happen if your capacity increment is 1.

Having a multiplier as a capacity increment will make for a super expensive stack for larger amounts of memory.

Changing your elementcount-- then ++ again in peek is just weird. Just change all this:

p->elementCount--;
int topValue = p->elementData[p->elementCount];
p->elementCount++;
return topValue;

to

return p->elementData[p->elementCount-1]
\$\endgroup\$
  • \$\begingroup\$ Interesting read about the Command Query Separation. It cites a common exception is the pop function \$\endgroup\$ – chux Sep 11 '14 at 3:53
  • \$\begingroup\$ @chux if you read what martin says about it, you can see there is debate over pop, he likes it, like a lot of people like it because it makes for a kind of nicer interface. I tend towards separation myself. \$\endgroup\$ – Keith Nicholas Sep 11 '14 at 4:10
  • 1
    \$\begingroup\$ There can actually be performance implications of a returning pop. In particular, imagine you have extremely heavy elements of your stack. peek can return a pointer to the element letting you avoid a copy (bonus: you could even return a non-const ptr and mutate the item inside of the stack in place), and then you can copy it yourself if you want to. pop can't return a pointer since it would be risk becoming a dangling pointer unless the stack made some rather odd memory guarantees.This actually is part of the rationale behind void pop() in C++ the other part being and exception safety. \$\endgroup\$ – Corbin Sep 11 '14 at 4:57
  • \$\begingroup\$ @KeithNicholas About the CQS, don't you think returning the value could have some benefits in some cases ? Also, I didn't quite understand from the wiki page what are the benefits of following the CQS exactly ? If you could pinpoint me on the answer I would appreciate it. \$\endgroup\$ – gues532 Sep 11 '14 at 13:25
  • \$\begingroup\$ Forgot to add, I've added an option to set the capacity increment variable so it'll be the decision of the programmer who use the lib, is it still a bad thing ? \$\endgroup\$ – gues532 Sep 11 '14 at 13:31
3
\$\begingroup\$
  1. After using @Keith Nicholas idea concerning stackPeek(), change int stackPeek(Stack*); --> int stackPeek(const Stack*);.

  2. Consider if code had an large array of stacks. Some used, some not. Keeping unused instances small is a good goal. Recommend changing initializeStack() so that p->elementData = NULL; p->stackSize = 0;.

  3. The whole "how fast to grow" and if able "how fast to shrink" is something to ponder. Code certainly should not call realloc() on every increment, nor should it be called only once. An efficient median somewhere in between is best, but depends on the nature of the application. Consider a grow-only or a growing and shrinking stack. Should growth be linear (+4 to +16) or geometric (*1.5 to *4.0)? Note: if code uses a grow/shrink stack, insure the grow levels are offset from the shrink level to prevent thrashing. One could write a small book on this issue. Use what works for you.

  4. Recommend the following style for realloc() usage - easier to maintain and better OOM (out-of-memory) handling. Note: drop the cast.

    // p->elementData = (int*)realloc(p->elementData, sizeof(int) * p->stackSize);
    void *temp = realloc(p->elementData, sizeof(p->elementData) * p->stackSize);
    if (temp == NULL && p->stackSize > 0) {
      OOM_Handler();
    }
    p->elementData = temp;
    
  5. getNumberOfElements() and getStackSize() should return the same type as the fields: unsigned.

  6. Agree with most of @Keith Nicholas fine answer, except details about growth.

\$\endgroup\$
  • \$\begingroup\$ growth is a tricky one, I'd do chunked growth, so it grows in fix sized increments with a progression of the fixed size. It could be made so you have a configurable growth strategy. Also might want a shrinking strategy, because if this stack peaks, it could be taking most all of your available memory very easily \$\endgroup\$ – Keith Nicholas Sep 11 '14 at 4:38
  • \$\begingroup\$ @chux But let's assume we have an array of stacks, wouldn't it be the programmer responsibility to initialize only the stacks that he will use in that array ? If someone would use that lib and make an array of stacks and go through each stack and initialize all of them but won't use them all is a problem on the programmer side for initializing stacks he doesn't use and as result allocating memory he won't use no ? \$\endgroup\$ – gues532 Sep 11 '14 at 13:38
  • \$\begingroup\$ Also, let's assume we do the following in the initialization: p->elementData=NULL p->stackSize=0 when we try and push an element we allocate 0 bytes to the temp pointer every time because stackSize is initialized to 0 and elementData, also can we do sizeof(*p->elementData) if it points to NULL? I'm not sure what will result from this assignment to temp. Will temp point to some address or will it point to NULL? and what is this new OOM_Handler function do ? I got kind of confused, if you could clear thing for me as I'm still trying to learn about how memory and pointers works as best as I can. \$\endgroup\$ – gues532 Sep 11 '14 at 13:39
  • \$\begingroup\$ In the array of stack example: it is good programming to immediately initialize each element of the array rather than only initialize elements of the array to be used and leave the others in a questionable state. \$\endgroup\$ – chux Sep 11 '14 at 14:40
  • \$\begingroup\$ sizeof(*p->elementData) is evaluated at compile time. The value in *p->elementData, be it NULL or not makes no difference. On the first push(), when p->stackSize=0, A new stack size > 0 is determined (maybe 1, 2, or 4) and realloc(*p->elementData, new_size) is called. It is OK that *p->elementData is NULL at this point. OOM_Handler() handles the out-of-memory condition. This is TBD. 2 ideas: 1) exit the program. 2) simply do not do the push. If the return value is NULL (and the size requested > 0), then the original pointer passed to realloc() is still valid. \$\endgroup\$ – chux Sep 11 '14 at 14:51

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.