Page 1 of 2
Stack implementation.
Posted: Wed Jan 11, 2012 11:35 pm
by centip3de
I've been lurking on the forums for a long time now and I will happily admit that I'm a super-noob (uber-noob?) in the OS development arena. I've only been programming for about 5-6 years now, and only pushing myself at learning more difficult topics for about 7 months now. So, I apologize if I'm completely wrong. Now, to the meat-and-potato's of this post:
I recently tried making a stack implementation just for fun, learning, and the likes. The question was that when I read a paper on it (
http://www.cs.bu.edu/teaching/c/stack/array/) it varied completely from the way I did it, though I'm pretty sure mine works in a similar way. In my implementation I have an array simulating the stack. When pushing to the stack, all I do is add to the array like you normally would. Where-as when popping from the stack, I just remove the most recently added element. I don't do anything like he did in that paper (though we both followed a similar principle from what I could tell). Maybe I just need to beef up my programming skills more than I already thought I did, but I'm just wondering why he did his differently.
Here's my 50% C, 50% C++ code (trying to transition from C++ to C):
Code: Select all
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int i = 0;
int arraySize;
char * stack[100];
string stackPopped;
int stackPoppedI;
void stackPush(char * pushed)
{
if(i == 100)
{
cout << "ERROR: Stack overflow!";
free(stack);
exit(EXIT_FAILURE);
}
else
{
int length;
length = strlen(pushed);
stack[i] = (char*)malloc(sizeof(i));
strcpy(stack[i], pushed);
i++;
cout << "Stack currently contains;" << endl;
for(int x; x < i; x++)
{
cout << stack[x] << endl;
}
}
}
void stackPop(int arrayNumber)
{
if(i == 0)
{
cout << "Stack underflow!" << endl;
exit(EXIT_FAILURE);
}
int j;
if((j = atoi(stack[arrayNumber])) > 0)
{
stackPoppedI = atoi(stack[arrayNumber]);
stack[arrayNumber] = 0;
--i;
cout << "stackPoppedI currently contains your number." << endl;
cout << stackPoppedI;
free(stack[arrayNumber]);
}
else
{
char stackPoppedc[256]; // (Stack Popped Copy) So that I can copy the string from the stack, into my string
strcpy(stackPoppedc, stack[arrayNumber]);
stackPopped = stackPoppedc;
stack[arrayNumber] = 0;
--i;
cout << "stackPopped currently contains your string." << endl;
cout << stackPopped << endl;
free(stack[arrayNumber]);
}
}
Are these the same (besides the fact that mine's more noobish)? If not, what advantages does his code have over mine?
Sorry if this is obvious,
~Cent
Re: Stack implementation.
Posted: Thu Jan 12, 2012 12:11 am
by AndrewBuckley
it feels like a real headache to make a psudo stack in higher levels, but the first thing that might send you in a tailspin is most stacks grow downward. you gave yourself an array of 100 bytes and started on the bottom. start at the top and work your way down. things might make more sense then. ill look a little closer at your code to see if i can make heads or tails of it, keep in mind im a rookie here too.
Re: Stack implementation.
Posted: Thu Jan 12, 2012 12:16 am
by centip3de
Merlin wrote:it feels like a real headache to make a psudo stack in higher levels, but the first thing that might send you in a tailspin is most stacks grow downward. you gave yourself an array of 100 bytes and started on the bottom. start at the top and work your way down. things might make more sense then. ill look a little closer at your code to see if i can make heads or tails of it, keep in mind im a rookie here too.
I know they grow downward, that's why I was confused when my code worked much like it would in a normal implementation.
Re: Stack implementation.
Posted: Thu Jan 12, 2012 12:19 am
by AndrewBuckley
ooh fun, your stack allows a variable length input but does not bother to check if it has room for it. make a string that is longer than 100 chars and see what happens.
Re: Stack implementation.
Posted: Thu Jan 12, 2012 12:22 am
by AndrewBuckley
his style is cleaner and allows for multiple well defined stacks. it also looks a little different because he only allows one byte to be pushed at a time.
Re: Stack implementation.
Posted: Thu Jan 12, 2012 12:59 pm
by centip3de
Merlin wrote:ooh fun, your stack allows a variable length input but does not bother to check if it has room for it. make a string that is longer than 100 chars and see what happens.
Whoops. Haha, I'll have to change that.
Merlin wrote:his style is cleaner and allows for multiple well defined stacks. it also looks a little different because he only allows one byte to be pushed at a time.
Well yes, I'm still very new to C and C-styled languages for that matter. A clean style such as his will be a goal later on, when I understand the language itself a bit better. Though, the fact that it's only one byte at a time is interesting...
berkus wrote:He has a stack of chars, you have a stack of strings.
Can't compare as it's not essentially the same.
Hmmm... I'll see if I can't rework my code a bit to make it more similar to his and report back. Thanks for all the information!
Re: Stack implementation.
Posted: Fri Jan 13, 2012 5:00 am
by turdus
I use this for stack. I think you overcomplicate things. K.I.S.S. you know...
Code: Select all
#define stackelementtype int
#define STACKBUFF 1024
typedef struct {
int idx;
stackelementtype items[STACKBUFF];
} stack;
#define push(stck,item) {stck.items[stck.idx++]=item;if(stck.idx>=STACKBUFF)error(OUTOFMEM);}
#define pop(stck) ((stck.idx>0)?stck.items[--stck.idx]:0)
#define top(stck) ((stck.idx>0)?stck.items[stck.idx-1]:0)
#define isempty(stck) (stck.idx<1)
Re: Stack implementation.
Posted: Fri Jan 13, 2012 7:32 am
by turdus
@berkus: you won
Re: Stack implementation.
Posted: Fri Jan 13, 2012 12:52 pm
by gravaera
Berkus' post was just too pro
Re: Stack implementation.
Posted: Thu Feb 02, 2012 8:02 am
by brain
Have you considered using strdup rather than strlen/strcpy/malloc:
instead of:
Code: Select all
int length;
length = strlen(pushed);
stack[i] = (char*)malloc(sizeof(i));
strcpy(stack[i], pushed);
(Just noticed as well your allocating the size of an int with malloc not the length of your string? That's definitely not what you wanted to do?)
do this:
Its faster and easier to read
Also as other have said watch those fixed length buffers, they will bite you in the @$$ in bigger projects!
Re: Stack implementation.
Posted: Fri Feb 03, 2012 1:43 am
by bluemoon
How do you think of the life cycle of each element? Who is responsible to free that strdup'ed string after pop()?
IMO It's not a good interface if the object itself allocate something internally, but require the user to release it.
Re: Stack implementation.
Posted: Fri Feb 03, 2012 3:35 am
by brain
bluemoon wrote:
How do you think of the life cycle of each element? Who is responsible to free that strdup'ed string after pop()?
IMO It's not a good interface if the object itself allocate something internally, but require the user to release it.
True, however doesn't the same apply to the malloc implementation?
Re: Stack implementation.
Posted: Fri Feb 03, 2012 4:01 am
by Solar
I think bluemoon went after a wild goose here. Whether you use strlen() / malloc() / strcpy() or strdup() doesn't matter, interface-wise. (Either way you free() in pop().)
The way I see it, strdup() has the advantage of being concise, and the disadvantage of being POSIX, not standard C. How much of a disadvantage that is (showstopper or non-issue) is up to personal tastes. In examples, I generally prefer strict (if somewhat more elaborate) standard C over POSIX, but that's just me.
Re: Stack implementation.
Posted: Fri Feb 03, 2012 4:27 am
by bluemoon
Solar wrote:(Either way you free() in pop().)
No. If I use a string stack, I push a string into it I don't care how it stored internally, but I like to access the string *after* pop.
So, I see some choices of implementation:
Code: Select all
int push(string); // copy the string to internal storage
int pop(buffer, buffer_len); // copy from internal storage into user-provided buffer
OR
Code: Select all
int push(string); // do not copy, but just reference
char* pop();
OR
Code: Select all
int push(string); // copy the string to internal storage
const char* pop(); // return a pointer to internal storage
int release(const char* p); // release the internal storage
From my guess, the code from OP tends to the third model, which allocate internally but require user to release it; I personally don't like this.
Re: Stack implementation.
Posted: Fri Feb 03, 2012 4:27 am
by Combuster
bluemoon wrote:IMO It's not a good interface if the object itself allocate something internally, but require the user to release it.
That's IMNSHO complete nonsense because it implies you can never
transfer ownership of objects (and as pointed out, criminalizes any use of *alloc and operator new).
In each of your cases there is a functional equivalent of free(container) required at some point which is missing from the first two examples