patterncModerate
Implementation of an Stack without Linked Lists in C
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
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
stack.h
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
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
-
-
-
Upon the return,
To actually copy the string, do
which may introduce other problems in interacting with client (who owns the string after
-
You may want to shrink the stack when
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.