Array implementation of Stack

Discussion in 'C Programming' started by arnuld, Jun 16, 2011.

  1. arnuld

    arnuld Guest

    WANTED: To write an array implementation of Stack.
    WHAT I GOT: It works fine.

    I think program is still little too complex. Any ideas to improve ?



    /* Array implementation of Stack - Aho, Hopcraft and Ullman, page 68-70
    * section 2.3. We will add element at the bottom and we will grow the
    * stack to top. top_index will keep track of index where element was
    * added as latest. We will use top_index to push/pop elements.
    *
    * VERSION 0.0.
    *
    */

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    enum {
    SIZE_NAME = 10, SIZE_ARR = 3,
    VAL_SUCC = 0, VAL_ERR = 1
    };

    struct elm
    {
    int num;
    char name[SIZE_NAME+1];
    };


    struct elm_stack
    {
    int top_index;
    struct elm* arr[SIZE_ARR];
    };


    int push(struct elm_stack* , struct elm* );
    void pop(struct elm_stack* );
    struct elm_stack* stack_init(void);
    void print_stack(struct elm_stack* );
    struct elm* get_element(const char* c, int n);


    int main(void)
    {
    struct elm_stack* s = stack_init();

    struct elm* e0 = get_element("comp", 2);
    struct elm* e1 = get_element("lang", 1);
    struct elm* e2 = get_element("c", 0);

    int ret_elem = push(s, e0);
    if(VAL_ERR == ret_elem)
    {
    printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
    free(e0);
    }

    ret_elem = push(s, e1);
    if(VAL_ERR == ret_elem)
    {
    printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
    free(e1);
    }

    ret_elem = push(s, e2);
    if(VAL_ERR == ret_elem)
    {
    printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
    free(e2);
    }

    print_stack(s);


    printf("-----------------------------------------\n\n");
    pop(s);
    print_stack(s);
    printf("-----------------------------------------\n\n");

    pop(s);
    print_stack(s);
    printf("-----------------------------------------\n\n");

    pop(s);
    print_stack(s);

    return EXIT_SUCCESS;
    }



    int push(struct elm_stack* s, struct elm* e)
    {
    int ret;

    if(NULL == s || NULL == e)
    {
    printf("IN:%s @%d Invalid Args!\n", __FILE__, __LINE__);
    ret = VAL_ERR;
    }
    else if(s->top_index == 0)
    {
    ret = VAL_ERR;
    }
    else
    {
    --(s->top_index);
    /* printf("s->top_index = %d\n", s->top_index); */
    s->arr[s->top_index] = e;
    /* printf("%s = %d\n", e->name, e->num); */
    ret = VAL_SUCC;
    }

    return ret;
    }


    void pop(struct elm_stack* s)
    {
    if(NULL == s)
    {
    printf("IN:%s @%d: Invalid Args!\n", __FILE__, __LINE__);
    }
    else if(SIZE_ARR <= s->top_index)
    {
    printf("Nothing to pop()\n");
    }
    else
    {
    struct elm* e = s->arr[s->top_index];
    free(e);
    ++(s->top_index);
    }
    }



    struct elm_stack* stack_init(void)
    {
    int idx;
    struct elm_stack* p = malloc(1 * sizeof *p);
    if(NULL == p)
    {
    printf("IN: %s @%d: Out of Memory!\n", __FILE__, __LINE__);
    }
    else
    {
    p->top_index = SIZE_ARR;
    for(idx = 0; idx < SIZE_ARR; ++idx) p->arr[idx] = NULL;
    }

    return p;
    }


    struct elm* get_element(const char* c, int n)
    {
    struct elm* p = malloc(1 * sizeof *p);

    if(NULL == p)
    {
    printf("IN:%s @%d: Out of Memory!\n", __FILE__, __LINE__);
    }
    else if(SIZE_NAME < strlen(c))
    {
    printf("IN: %s @ %d: ", __FILE__, __LINE__);
    printf("Name too big, Not adding element\n");
    free(p);
    p = NULL;
    }
    else
    {
    p->num = n;
    strcpy(p->name,c);
    }

    return p;
    }


    void print_stack(struct elm_stack* s)
    {
    if(NULL == s)
    {
    printf("IN:%s @%d: Invalid Args!\n", __FILE__, __LINE__);
    }
    else
    {
    int idx = SIZE_ARR - 1;
    struct elm* e;
    /*printf("idx %d, top_index = %d\n", idx, s->top_index); */
    for(; (idx >= 0) && (idx >= s->top_index); --idx)
    {
    /*printf("idx %d, top_index = %d\n", idx, s->top_index);*/
    e = s->arr[idx];
    printf("%s = %d\n", e->name, e->num);
    }
    }
    }

    =================== OUTPUT ========================
    [arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra lifo-array.c
    [arnuld@dune C]$ ./a.out
    comp = 2
    lang = 1
    c = 0
    -----------------------------------------

    comp = 2
    lang = 1
    -----------------------------------------

    comp = 2
    -----------------------------------------

    [arnuld@dune C]$



    --
    www.lispmachine.wordpress.com
    find my email-ID @above blog
     
    arnuld, Jun 16, 2011
    #1
    1. Advertising

  2. On Jun 16, 1:00 pm, arnuld <> wrote:
    > WANTED:  To write an array implementation of Stack.
    > WHAT I GOT:  It works fine.
    >
    > I think program is still little too complex. Any ideas to improve ?
    >

    ..
    Stacks are inherently simple. You have a chunk of memory, and a stack
    top pointer or index. You push by adding an intem and incrementing
    stack top, you pop by reading the top item and decrementing stack top.
    Stacks are used in lots of places. The tricky part is deciding on the
    interface for your particular stack.

    For instance stacks are often used for global states. You have a
    drawing package. You don't want every subroutine to have to query
    every colour, linestyle, and font, store the state, and put them back.
    So you might provide pushdrawingstate and popdrawing state. Probably
    you want to store the stack as globals.
    However on other occasions globals make it impossible to achieve what
    you want, because you can only have one instance of each global stack
    per program.

    Then you've got to consider what happens if the caller pushes too many
    items, or tries to pop an item that isn't there. If the user controls
    the stack operations directly, then of course you've got to assume
    that overflows and underflows will happen. If you are caller yourself,
    it might be OK to be careful never to push more than 256 levels of
    nested parentheses. Or maybe ypu want the stack to expand to fill all
    available memory. This might open the program up to a denial of
    service attack. The strategy of always passing errors up is a bad one,
    as is the strategy of always crashing out - you have to decide what
    the right interface is for your particular situation.

    This is why software engineering is hard. Many projects fail because
    of an accumulation of poor decisions, each small in themselves,
    eventually makes further development impossible.
    --
    Read my book MiniBasic - how to write a script interpreter
    http://www.lulu.com/bgy1mm
     
    Malcolm McLean, Jun 16, 2011
    #2
    1. Advertising

  3. arnuld

    Mark Bluemel Guest

    On 06/16/2011 11:00 AM, arnuld wrote:
    > WANTED: To write an array implementation of Stack.


    Really?

    > void pop(struct elm_stack* );


    Why would pop() not return a value?
     
    Mark Bluemel, Jun 16, 2011
    #3
  4. arnuld

    Rui Maciel Guest

    Mark Bluemel wrote:

    > On 06/16/2011 11:00 AM, arnuld wrote:
    >> WANTED: To write an array implementation of Stack.

    >
    > Really?
    >
    >> void pop(struct elm_stack* );

    >
    > Why would pop() not return a value?


    Why should pop return a value?


    Rui Maciel
     
    Rui Maciel, Jun 16, 2011
    #4
  5. arnuld

    Willem Guest

    Rui Maciel wrote:
    ) Mark Bluemel wrote:
    )
    )> On 06/16/2011 11:00 AM, arnuld wrote:
    )>> WANTED: To write an array implementation of Stack.
    )>
    )> Really?
    )>
    )>> void pop(struct elm_stack* );
    )>
    )> Why would pop() not return a value?
    )
    ) Why should pop return a value?

    For the same reason as push() takes two arguments.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Jun 16, 2011
    #5
  6. "Rui Maciel" <> wrote in message
    news:4dfa55b3$0$23522$...
    > Mark Bluemel wrote:
    >
    >> On 06/16/2011 11:00 AM, arnuld wrote:
    >>> WANTED: To write an array implementation of Stack.

    >>
    >> Really?
    >>
    >>> void pop(struct elm_stack* );

    >>
    >> Why would pop() not return a value?

    >
    > Why should pop return a value?


    Because you can use the return value of the function itself as a predicate
    for a condition? Perhaps a better name would be `try_pop()'; humm...
     
    Chris M. Thomasson, Jun 16, 2011
    #6
  7. arnuld

    Ian Collins Guest

    On 06/17/11 08:35 AM, Chris M. Thomasson wrote:
    > "Rui Maciel"<> wrote in message
    > news:4dfa55b3$0$23522$...
    >> Mark Bluemel wrote:
    >>
    >>> On 06/16/2011 11:00 AM, arnuld wrote:
    >>>> WANTED: To write an array implementation of Stack.
    >>>
    >>> Really?
    >>>
    >>>> void pop(struct elm_stack* );
    >>>
    >>> Why would pop() not return a value?

    >>
    >> Why should pop return a value?

    >
    > Because you can use the return value of the function itself as a predicate
    > for a condition? Perhaps a better name would be `try_pop()'; humm...


    Or simply use top() to read and pop() to pop.

    --
    Ian Collins
     
    Ian Collins, Jun 16, 2011
    #7
  8. "Ian Collins" <> wrote in message
    news:...
    > On 06/17/11 08:35 AM, Chris M. Thomasson wrote:
    >> "Rui Maciel"<> wrote in message
    >> news:4dfa55b3$0$23522$...
    >>> Mark Bluemel wrote:
    >>>
    >>>> On 06/16/2011 11:00 AM, arnuld wrote:
    >>>>> WANTED: To write an array implementation of Stack.
    >>>>
    >>>> Really?
    >>>>
    >>>>> void pop(struct elm_stack* );
    >>>>
    >>>> Why would pop() not return a value?
    >>>
    >>> Why should pop return a value?

    >>
    >> Because you can use the return value of the function itself as a
    >> predicate
    >> for a condition? Perhaps a better name would be `try_pop()'; humm...

    >
    > Or simply use top() to read and pop() to pop.


    That does create a "gap" between `top()' and `pop()'; no problem for
    single-threaded access...
     
    Chris M. Thomasson, Jun 16, 2011
    #8
  9. "Chris M. Thomasson" <> wrote in message
    news:unuKp.7810$...
    > "Ian Collins" <> wrote in message
    > news:...
    >> On 06/17/11 08:35 AM, Chris M. Thomasson wrote:
    >>> "Rui Maciel"<> wrote in message
    >>> news:4dfa55b3$0$23522$...
    >>>> Mark Bluemel wrote:
    >>>>
    >>>>> On 06/16/2011 11:00 AM, arnuld wrote:
    >>>>>> WANTED: To write an array implementation of Stack.
    >>>>>
    >>>>> Really?
    >>>>>
    >>>>>> void pop(struct elm_stack* );
    >>>>>
    >>>>> Why would pop() not return a value?
    >>>>
    >>>> Why should pop return a value?
    >>>
    >>> Because you can use the return value of the function itself as a
    >>> predicate
    >>> for a condition? Perhaps a better name would be `try_pop()'; humm...

    >>
    >> Or simply use top() to read and pop() to pop.

    >
    > That does create a "gap" between `top()' and `pop()'; no problem for
    > single-threaded access...


    WRT multi-threaded access it seems like the combined success to a call to
    `top()' and a call to `pop()' would be analogous to a committed
    transactional memory operation. Or simply lock the whole damn thing!

    ;^)
     
    Chris M. Thomasson, Jun 16, 2011
    #9
  10. arnuld

    Rui Maciel Guest

    Chris M. Thomasson wrote:

    > Because you can use the return value of the function itself as a predicate
    > for a condition? Perhaps a better name would be `try_pop()'; humm...


    You have top for that, which, from that code, you can get with:

    stack->arr[stack->top_index]

    In this case, if you write your pop() to return the value then at worse you
    perform a set of instructions which more often than not you don't even need
    and at best end up needlessly using more code to perform a task that you
    already get with a simple, single LoC.


    Rui Maciel
     
    Rui Maciel, Jun 16, 2011
    #10
  11. arnuld

    Rui Maciel Guest

    Willem wrote:

    > ) Why should pop return a value?
    >
    > For the same reason as push() takes two arguments.
    >


    And what reason is that?


    Rui Maciel
     
    Rui Maciel, Jun 16, 2011
    #11
  12. arnuld

    Rui Maciel Guest

    Chris M. Thomasson wrote:

    > That does create a "gap" between `top()' and `pop()'; no problem for
    > single-threaded access...


    And what leads you to believe that writing pop() so that it returns a value
    will make the code immune to concurrency issues, or at least more vulnerable
    than the version which doesn't return a value?


    Rui Maciel
     
    Rui Maciel, Jun 16, 2011
    #12
  13. Rui Maciel <> writes:
    > Willem wrote:
    >> ) Why should pop return a value?
    >>
    >> For the same reason as push() takes two arguments.

    >
    > And what reason is that?


    Convenience.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Jun 16, 2011
    #13
  14. "Rui Maciel" <> wrote in message
    news:4dfa7ac7$0$23523$...
    > Chris M. Thomasson wrote:
    >
    >> That does create a "gap" between `top()' and `pop()'; no problem for
    >> single-threaded access...

    >
    > And what leads you to believe that writing pop() so that it returns a
    > value
    > will make the code immune to concurrency issues, or at least more
    > vulnerable
    > than the version which doesn't return a value?


    NO IMMUNITY!


    I simply prefer the conditional `try_pop()' function because it can be so
    easily used by the inherent pattern contained within the almighty
    "eventcount" algorithm:

    http://groups.google.com/group/comp.programming.threads/browse_frm/thread/6cf4655c4e0b7c95

    ;^)
     
    Chris M. Thomasson, Jun 16, 2011
    #14
  15. arnuld

    Willem Guest

    Rui Maciel wrote:
    ) Willem wrote:
    )
    )> ) Why should pop return a value?
    )>
    )> For the same reason as push() takes two arguments.
    )>
    )
    ) And what reason is that?

    I don't know. Ask the person who proposed the API upthread.

    If you insist that pop() shouldn't return a value, then push()
    should not take a value either, just a stack. Otherwise it
    is plainly inconsistent.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Jun 17, 2011
    #15
  16. Willem <> writes:
    > Rui Maciel wrote:
    > ) Willem wrote:
    > )
    > )> ) Why should pop return a value?
    > )>
    > )> For the same reason as push() takes two arguments.
    > )>
    > )
    > ) And what reason is that?
    >
    > I don't know. Ask the person who proposed the API upthread.
    >
    > If you insist that pop() shouldn't return a value, then push()
    > should not take a value either, just a stack. Otherwise it
    > is plainly inconsistent.


    pop() not returning a value makes some sense if you think that
    shrinking the stack and retrieving the top element should be
    separate operations.

    push() without an argument would have to push an indeterminate or
    default value onto the stack.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Jun 17, 2011
    #16
  17. arnuld

    Willem Guest

    Keith Thompson wrote:
    ) pop() not returning a value makes some sense if you think that
    ) shrinking the stack and retrieving the top element should be
    ) separate operations.

    push() not taking a value makes some sense if you think that
    expanding the stack and setting the top element should be
    separate operations.

    ) push() without an argument would have to push an indeterminate or
    ) default value onto the stack.

    pop() without a return value would have to discard the value it
    takes from the stack.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Jun 17, 2011
    #17
  18. In article <>,
    Keith Thompson <> wrote:

    > Willem <> writes:
    > > Rui Maciel wrote:
    > > ) Willem wrote:
    > > )
    > > )> ) Why should pop return a value?
    > > )>
    > > )> For the same reason as push() takes two arguments.
    > > )>
    > > )
    > > ) And what reason is that?
    > >
    > > I don't know. Ask the person who proposed the API upthread.
    > >
    > > If you insist that pop() shouldn't return a value, then push()
    > > should not take a value either, just a stack. Otherwise it
    > > is plainly inconsistent.

    >
    > pop() not returning a value makes some sense if you think that
    > shrinking the stack and retrieving the top element should be
    > separate operations.
    >
    > push() without an argument would have to push an indeterminate or
    > default value onto the stack.


    Maybe the names are just poorly chosen. I always think of pop()
    returning the top value and shrinking the stack. I would use drop() to
    just shrink the stack. A push() without arguments could just duplicate
    the top of the stack, but then you'd be better off calling that dup().
     
    Mark Storkamp, Jun 17, 2011
    #18
  19. Willem <> writes:
    > Keith Thompson wrote:
    > ) pop() not returning a value makes some sense if you think that
    > ) shrinking the stack and retrieving the top element should be
    > ) separate operations.
    >
    > push() not taking a value makes some sense if you think that
    > expanding the stack and setting the top element should be
    > separate operations.


    *And* if you don't mind the new top of the stack having a meaningless
    value. The two cases are not equivalent.

    > ) default value onto the stack.
    >
    > pop() without a return value would have to discard the value it
    > takes from the stack.


    Of course. Sometimes that's what you want to do.

    I'm not arguing that pop() *shouldn't* have a return value, just
    that it's not entirely insane for it not to.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Jun 17, 2011
    #19
  20. arnuld

    Joe Pfeiffer Guest

    Willem <> writes:

    > Keith Thompson wrote:
    > ) pop() not returning a value makes some sense if you think that
    > ) shrinking the stack and retrieving the top element should be
    > ) separate operations.
    >
    > push() not taking a value makes some sense if you think that
    > expanding the stack and setting the top element should be
    > separate operations.


    This would be an extraordinarily idiosyncratic usage.

    > ) push() without an argument would have to push an indeterminate or
    > ) default value onto the stack.
    >
    > pop() without a return value would have to discard the value it
    > takes from the stack.


    pop() without a return value wouldn't actually have to take a value from
    the stack; it just moves the pointer.

    > SaSW, Willem
     
    Joe Pfeiffer, Jun 17, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Mabee
    Replies:
    4
    Views:
    502
    Jonathan Mcdougall
    Dec 26, 2004
  2. Surinder Singh
    Replies:
    1
    Views:
    1,213
    Richard Bos
    Dec 20, 2007
  3. Casey Hawthorne
    Replies:
    3
    Views:
    1,104
    Flash Gordon
    Nov 1, 2009
  4. Debajit Adhikary
    Replies:
    36
    Views:
    2,318
    Andre Kaufmann
    Feb 10, 2011
  5. luser- -droog

    Re: Array implementation of Stack

    luser- -droog, Jul 7, 2011, in forum: C Programming
    Replies:
    2
    Views:
    266
    luser- -droog
    Jul 7, 2011
Loading...

Share This Page