2
\$\begingroup\$

This is a version I made:

#include <stdio.h>
#include <stdbool.h>

#define MAX_STACK_SIZE 255

typedef struct
{
    int array[MAX_STACK_SIZE];
    unsigned int count;
    unsigned int max;
} Stack;

void initialize(Stack*);
void push(Stack*, int value);
int* pop(Stack*);
bool isEmpty(Stack*);
bool isFull(Stack*);

int main()
{
    Stack s1;
    initialize(&s1);
    for(int i = 0; i < 7; i++)
    {
        push(&s1, i);
    }
    pop(&s1);
    push(&s1, 88);
    push(&s1, 6);
    int *top;
    while((top = pop(&s1)) != NULL)
    {
        printf("Popping %d from the top of the stack.\n", *top);
    }
    return 0;
}

void initialize(Stack *p)
{
    p->count = 0;
    p->max = MAX_STACK_SIZE;
}

void push(Stack *p, int value)
{
    if(!isFull(p))
    {
        p->array[p->count] = value;
        p->count++;
    }
}

int* pop(Stack *p)
{
    if (!isEmpty(p))
    {
        p->count--;
        return p->array + p->count;
    }
    return NULL;
}

bool isEmpty(Stack *p)
{
    return p->count == 0;
}

bool isFull(Stack *p)
{
    return p->count == p->max;
}

This is a version of how it was done from the source I'm learning from:

#include <stdio.h>

#define MAX_STACK_SIZE 255
#define true 1
#define false 0
#define bool unsigned short int

struct stack
{
    int *topOfStack;
    int *pointer;
    int count;
    int max;
    int theStack[MAX_STACK_SIZE];
};

void initStack(struct stack *stackStruct)
{
    stackStruct->topOfStack = stackStruct->theStack;
    stackStruct->pointer = stackStruct->theStack;
    stackStruct->max = MAX_STACK_SIZE;
    stackStruct->count = 0;
}
bool pushStack(struct stack *stackStruct, int inputValue)
{
    if(stackStruct->count < stackStruct->max)
    {
        *stackStruct->pointer = inputValue;
        stackStruct->count++;
        stackStruct->pointer++;
        return true;
    }
    else
        return false;
}
int* popStack(struct stack *stackStruct)
{
    if(stackStruct->count > 0)
    {
        stackStruct->pointer--;
        stackStruct->count--;
        return stackStruct->pointer;
    }
    return NULL;
}

I think there's not so much of a difference between theb, but I just wanted to be sure. In their version, they've used 2 additional pointers in their Stack struct and I removed them because I thought it was not necessary because we could use the array address + count to get the pointer address in their example. I think they used it for convenience reasons. More differences are that I included <stdbool.h> instead of using macros (not really important).

On top of that, I've implemented isEmpty() and isFull() methods just for convenience, but don't take it into account when comparing the two implementations since I'm sure they could do the same. I just chose to show the 2 main functions that could be used on a stack.

Other than that, since it's an array-based implementation of a stack, I think it was possible to not include the max field in the struct since we define in a macro the stack maximum size, but I added it as well to my implementation for the heck of it.

Is there any differences between our implementations? Since I chose to do my own implementation I just want to make sure I that I did implemented it correctly and efficiently.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I think you should only post your implementation. We want to review code that you own/maintain; if you only had the 2nd snippet ("theirs"), this question would already be on hold. Please edit/reformulate your question to be on-topic per our help center. \$\endgroup\$ – Mathieu Guindon Sep 9 '14 at 23:55
  • \$\begingroup\$ @Mat'sMug What I want is comparison between the 2 implementation for learning purposes to make sure I didn't do any mistakes compared to the source I'm learning from. \$\endgroup\$ – gues532 Sep 10 '14 at 0:02
  • \$\begingroup\$ @gues532 : You would really do yourself a favor if you removed the code you didn't write and didn't ask for comparison; that's not what Code Review is about. If you really need a comparison and help with better implementation, this would be a question more on-topic for Software Engineering \$\endgroup\$ – Phrancis Sep 10 '14 at 0:39
  • 2
    \$\begingroup\$ I removed the off topic portion of the question. A vs B questions are on topic and OP is not asking for a review of the code he did not write, that code is only there for context. \$\endgroup\$ – RubberDuck Sep 10 '14 at 0:52
4
\$\begingroup\$
  1. push() and pop() have an asymmetry that should be reconciled. push() does not indicate any thing special when the stack is full and a push is attempted. It silently does not do the push. Yet when an pop of an emty stack occurs, a NULL is returned (versus a pointer to int) allowing the calling routine to take evasive action. A symmetric solution would both do something special - or not - on full/empty.

  2. A function to inspect the top of stack, without popping, could be added. This IMO would be useful. Additional routines to report current stack depth or stack space left are something to consider.

  3. Using unsigned int is OK, especially if the fixed array size is known to always be less than UINT_MAX. I favor size_t for array indexing as it has better portability for large arrays.

  4. A way to deal with popping or inspecting an empty stack is, as part of initialize(), to pass an int as the bottom-of-stack. This value does not actually ever get "popped off".

  5. The names of the functions are too generic ("initialize") and could well collide with other code. Suggest something like Stack_initialize(), and Stack_push().

  6. The OO part of me wants to see a copy and destructor function too. The destructor could simple do count = max = 0;

\$\endgroup\$
8
  • \$\begingroup\$ I didn't learn yet about size_t so I'll leave that a side for now. About the asymmetry between push() and pop() do you have a suggestion on what can I do ? on push I can return a true / false if a push had occur, but from my experience with the stack data structure in java, pop() used to return the value of the element, so in c for example if we're making an int[] array based stack and we want to return the value it'll be kind of a problem. we check that the stack is not empty and if so return the value else return what exactly ? that's the problem I've encountered. \$\endgroup\$ – gues532 Sep 10 '14 at 1:39
  • \$\begingroup\$ Also I wanted to ask, is there a way to make the implementation more dynamic size wise and type wise (Stack of int, double, floats other structures/unions etc..)? \$\endgroup\$ – gues532 Sep 10 '14 at 1:40
  • \$\begingroup\$ @gues532 For symmetry, I would favor int pop() rather than int * pop(). This becomes even more important should code want a dynamic sized stack for the address returned may become meaningless. If call wants to know if pop() is OK, call isempty() first. This lends to a symmetric void push(stack*, int). If a test for emptiness and a pop() need to be atomic, then int pop(stack*, bool*mt). \$\endgroup\$ – chux - Reinstate Monica Sep 10 '14 at 1:45
  • \$\begingroup\$ So how should I change the pop() function ? make it so push values only from the array[1] position towards the end of the array and pop everything except array[0] ? or use pass a boolean parameter isEmpty(&s1) to the pop() function ? Also can you give me a clue on how to implement dynamic sized stack and dynamic typed stack ? \$\endgroup\$ – gues532 Sep 10 '14 at 1:58
  • \$\begingroup\$ To make dynamic size wise is a worthy goal. The typical method uses a field int *darray initialized to NULL rather than array[255]. As needed, call realloc() to change the size. Recommend increasing the size by a factor of 4 or 16 when the need arises. \$\endgroup\$ – chux - Reinstate Monica Sep 10 '14 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.