HiveBrain v1.2.0
Get Started
← Back to all entries
patterncModerate

Implementation of an Stack without Linked Lists in C

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
withoutstacklistsimplementationlinked

Problem

I'm a beginning C programmer. As an exercise, I have attempted to implement a stack of strings in C. This is my first real exercise working with pointers. I looked at some other similar posts on here, and read through the comments. It seems that most individuals have chosen to do this by using linked lists, whereas I've just created an ArrayStack.

Maybe it would have been better to go the linked list route. Nonetheless, this is how I did it. I'm hoping there's not any glaring errors, but I'm sure there will be.

Also, question: I have a variable for the number of slots available in the array, which is used to determine when more memory needs to be allocated. But it would seem to me that I can use sizeof on the array, and sizeof on a single pointer in the array, and use division to get the number of slots, thus eliminating a variable. Would this be a better approach?

stack.h

#include 

typedef struct stringstack {
    int count;
    int slots;
    char** stack;
} stringstack;

void * makestack(void);
void push(struct stringstack* ptr, char stringtext[]);
char * pop(struct stringstack* ptr);
char * peek(struct stringstack* ptr);
int isempty(struct stringstack* ptr);
void destroy(struct stringstack* ptr);


stack.c

```
#include "stack.h"

/ Function creates a new stringstack object and returns a pointer to it /
void * makestack(void) {
stringstack ptr = (stringstack ) malloc(sizeof(stringstack));
ptr->count = 0;
ptr->slots = 1;
ptr->stack = (char **) malloc(sizeof(char*));
return ptr;
}

/ Pushes a string onto the top of a stack /
void push(struct stringstack* ptr, char stringtext[]) {
ptr->count++;
if (ptr->count == ptr->slots) / Allocate more space if necessary /
ptr->stack = (char **) realloc(ptr->stack, sizeof(char )((ptr->slots*=2)+1));
char stringptr = (char ) malloc(sizeof(stringtext));
stringptr = stringtext;
*(ptr->stack + ptr->count) = stringptr;
}

/* Removes the top item from the st

Solution

-
makestack should return a struct stringstack instead of void .

-
malloc and realloc may fail. Check their return values.

-
push doesn't copy the string (it only makes a redundant copy of the pointer). It is OK as long as you can guarantee that the string parameter has a lifetime long enough. Consider a scenario:

void foo(struct stringstack * stack)
{
    char bar[] = "aaa";
    push(stack, bar);
}


Upon the return, bar disappears, and the stack entry points to the pretty random place in the application stack. Do not expect to have "aaa" there.

To actually copy the string, do

*(ptr->stack + ptr->count) = strdup(stringtext);


which may introduce other problems in interacting with client (who owns the string after peek?). Unfortunately, C doesn't offer a clean solution.

-
You may want to shrink the stack when ptr->count hits the low watermark of ptr->slots.

Code Snippets

void foo(struct stringstack * stack)
{
    char bar[] = "aaa";
    push(stack, bar);
}
*(ptr->stack + ptr->count) = strdup(stringtext);

Context

StackExchange Code Review Q#70256, answer score: 10

Revisions (0)

No revisions yet.