Stack implementation.

[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

[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.

[centip3de]

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.

[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.

[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.

[centip3de]

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.

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...

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!

[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)

[turdus]

@berkus: you won

[gravaera]

Berkus' post was just too pro

[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:

Code: Select all

stack[i] = strdup(pushed);

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!

[bluemoon]

Code: Select all

stack[i] = strdup(pushed);

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.

[brain]

Code: Select all

stack[i] = strdup(pushed);

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?

[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.

[bluemoon]

(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.

[Combuster]

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