patterncMinor
Dynamically-sized stack - follow up
Viewed 0 times
sizeddynamicallyfollowstack
Problem
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.
Please review my stack implementation from before. I've made it dynamically sized if needed and made a few tweaks.
#include
#include
#include
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 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;
}Solution
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
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
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
to
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]Code Snippets
p->elementCount--;
int topValue = p->elementData[p->elementCount];
p->elementCount++;
return topValue;return p->elementData[p->elementCount-1]Context
StackExchange Code Review Q#62589, answer score: 3
Revisions (0)
No revisions yet.