STACKS in the Coding Interview Perspective.

Stack is a Abstract Data Structure , and is a basically a specification of what the instances and are set of axioms(pre-conditions and post conditions) that define the semantics(rules ) of the operations on those instances.

Types of operations we can perform on instances

i) constructor — creating the instance.

ii) access functions — accessing the data.

iii)manipulation functions — used for modifying the data.

Consider the an instance of INTEGER , and the axioms would perform the integer are as follows:

1. add(a,b) : x — this adds two integers a and b and gives result stored in integer x.
2. sub(a,b) : x — this subtracts two integers a and b and gives result stored in integer x.
3. multiply(a,b) : x — this multiply two integers a and b and gives result stored in integer x.

Stack Working Principle LIFO

If you look at the above image, we can easily understand the working strategy of the STACKS. i.e. LIFO — Last In First Out.

Initially , the stack is empty . i.e. we can say the top of the stack is pointing to -1. Now the element 1 is inserted into the stack. here in the insertion process we call it as a push operation. it is better to check if the stack is full before inserting the any element so that our system will not throw the stack overflow exception. Then the other element 2,3,4,5 followed by 1 are inserted into the stack.

All the push operation are showed in the above picture with IN notation.

Now if , we want to remove the element 1, it is not possible to remove it, because there are some other elements say 2 3 4 5 are top of the our element 1. Assume it like the stack of books or coins. Coin 1 is insert first and later on the other coins 2, 3, 4, and 5 are inserted in to a box with having only one way open. if we want to remove the coin 1, then we need to remove all other coins on top it, so that we can easily remove the other coins.

So, at any point of time , we can remove only top element from the stack.

the axioms of the stacks would be as follows

1. new() : ADT — Creates a new stack
2. push(S:ADT,o:element):ADT — Inserts the object o onto top of the stack S. it will also throw stack full exception , if the stack is full.
3. pop(S:ADT) : ADT — removes the top element in stacks , and if the stack is empty, throws the stack empty error.
4. top(S:ADT):ADT — returns the top element in stacks with out removing from it, and if the stack is empty, throws the stack empty error.

support methods

i) size(S:ADT):integer — returns the no of elements in the stack.

ii)isEmpty(S:ADT):boolean — indicates if the stack is empty.

Stack Implementation using Arrays

With help of above mentioned axioms , stacks can be implement interface in the java.

Stack Interface Implementation in JAVA

Now we need to have the StackEmptyException and StackFullException Java Class to support the STACK

StackEmptyException and StackFullException Classes

Now we should be implement the stack using array data structure.

Stack Implementation using Array — 1

Stack Implementation using Array — 2

Stack Implementation using Array — 3

output of the Stack Implementation using Array.

Problem with this approach is that we don’t know the size of the stack.

to overcome this , we will follow two strategeis,

tight strategy — takes O(n2/c) time.

growth strategy — take O(4n-1) time. (logarithmic concept wise). it wins.