Stacks

Today I will be re-learning how to write a stack. A stack is a simple data structure that allows the first input to come out last. It is a First in Last out type of data structure. A more proper definition for a stack seems to be a Last In First Out type of data structure. In essence, a stack has two methods, pop and push. Push is used when data needs to be pushed into the stack and pop is used when data needs to be taken out of the stack. Basically, a stack can be viewed to something as a pancake stack. The last pancake that is put on top of the stack will be the first pancake that will be taken out and eaten.

I've been reading that creating algorithms before programming will tremendously help the coding. I think I will try that out today by writing algorithms before writing the stack code. In addition to that, it seems that writing the test code for the methods before it is finished is another method that will ensure good quality code. I think for the moment, I will just stick with writing the algorithm first. By algorithm, at this time I mean pseudo code. I haven't really written pseudo code in a long time so I will be googling most of the constants name.

Algorithms:

METHOD void push(Object A)

GET the object required to put into the stack.

CREATE Node aNode in which (Object A, Reference to Next Node)

IF stack is empty

PUT aNode the firstNode (Where firstNode will be the first node to be taken)

ELSE

PUT tempNode = firstNode

firstNode = aNode

aNode.reference_to_nextNode = tempNode

END METHOD

METHOD Object pop()

CREATE returnNode

PUT returnNode = firstNode

firstNode = firstNode.reference (This is to ensure that the first node is popped)

RETURN returnNode

The algorithms above for the stacks use a Linked List. I believe that using an array or soemthign similar will be easier but for learning purposes, I think I should use a linked list. At the moment, I cannot think of any negative side effects to using a Linked List over the Array. The only negative side effect that I could think of is that it will take longer to use as Linked Lists are of an object type whereas arrays could be simplified to contain simple primitives.

I have not made any test cases for these methods and I wasn't planning to do that in the beginning. However, after writing all the pseudocode out, I figured why not? If I'm going to do something, I might as well do it properly.

TEST Case

POP

1) ensure that popping a null object will throw an error?

PUSH

1) ensure that the object being pushed are all the same type. (Hence use generics)

THINGS I HAVE LEARNED:

Perhaps the Node Private clas should be created as a public class in which everyone can extend?

However, that would defy the OO basics in which a Stack is not a Node. It is a collection of nodes but it will not make sense to have the Stack class extend Nodes. So I guess, at the moment, I will just leave it as is and have a private Node class in each of the data structure I create.