What does it mean to actually "Implement a stack"?

Question

Is my professor asking me to draw the stack? Does he want me to draw it in action? I feel stupid but it's not like anyone ever told me! Thank you for your help.

Wow you guys are quick. Thank you already. The complete question is: Consider two stacks, each of size n (i.e., each one can hold a maximum of n elements). If the sum of the number of elements in the two stacks is n, then any additional PUSH operation should result in an overflow error. (Note: Your implementation should take care of the fact that elements should POP opposite to the order in which they are PUSHed).

***I'm not asking for the answer I'm just wondering... what do you think he's asking me to do? Cause he still hasn't answered my email and I need it done by midnight.

Answer 1

Given your professor's description, he is almost certainly asking you to write a stack by hand.

That is, write (code) your Stack Abstract Data Type, its associated operations - push, and pop, at the very least, and some sort of driver to test that your stack works as expected and follows the specification (overflow errors and the like).

Do you know anything about stacks? Have you been to the lecture/lab on stacks if one was available? What does your textbook or favourite website say about them?

As for finishing this assignment by midnight, I would certainly try my best to write a stack by hand and to draw what is happening at each step (perhaps as a separate document, or embedded in the comments if this is electronic submission). You probably won't get a great mark since you don't seem to know what to do, but you will have hopefully learned something and shown that you put a little bit of effort into this assignment.

Answer 2

"Implement" generally means write, pure and simple. Your educator wants you to write code that can do what the assignment says.

Stacks of fixed size (n) can be easily implemented as an array with a current stack depth but you have an extra twist to your assignment inasmuch as you're only alowed to have n elements on both stacks combined rather than each stack.

I would implement it as follows (pseudo-code only since it's homework and, in any case, you haven't specified a language):

# Create the two stacks, each of size sz.
init_stack (sz):
    allocate stack1 as array[1 to sz] of integer
    allocate stack2 as array[1 to sz] of integer
    set stack1sz to 0
    set stack2sz to 0
    set maxsz to sz

 

# Push the value val onto stack stk.
push_stack (stk,val):
    if stk is not equal to 1 or 2:
        return error
    if stack1sz + stack2sz is equal to maxsz:
        return error
    if stk is 1:
        add 1 to stack1sz
        set element stack1sz of stack1 to val
    else:
        add 1 to stack2sz
        set element stack2sz of stack2 to val

 

# Pop a value off stack stk.
pop_statkck (stk):
    if s is not equal to 1 or 2:
        return error
    if stk is 1:
        if stack1sz is 0:
            return error
        set val to element stack1sz of stack1
        subtract 1 from stack1sz
    else:
        if stack2sz is 0:
            return error
        set val to element stack2sz of stack2
        subtract 1 from stack2sz
    return val

The variables stack1, stack2, stack1sz, stack2sz and maxsz should be declared in such a way that they survive in between function calls (i.e., not locals). All others are transitory.

If you have troubles converting that to a specific language, leave a comment and I'll provide pointers on what to look for.