Stacks

Stack is data structure in which all the operations will be done on the top element. It is also called as LIFO(Last In, First Out) model, in which the element which is inserted last will be removed first. It's a kind of Linear Data Structure. At any point of time, Only top element is visible outside.

List of Operations allowed on a Stack
Create(S) - creates the stack S
Push(S, x) - for inserting elements in to Stack
Pop (S) - for deleting elements from stack
Top(S) - returns the top element of the stack
isEmpty(S) - used to check whether the stack is empty or not
isFull(S) - used to check whether the stack is full or not.

Note : isFull is a special method, used in array based implementations only.

We can implement Stack with Arrays as well as with Lists also. Before we look into Algorithms and implementation details, first we will see the advantages and disadvantages with Stacks.

+ Stacks are used to manage methods at run time (when a method is called, its parameters and local variables are pushed onto a stack; when the method returns, the values are popped from the stack).

+ Many parsing algorithms (used by compilers to determine whether a program is syntactically correct) involve the use of stacks.

+ stacks can be used to evaluate arithmetic expressions (e.g., by a simple calculator program)

+ Stacks also useful for some operations on graphs

+ Stacks are also used for reversing things. If you push something, say a String onto a Stack one character at a time, and then construct a String from the members popped off the Stack, then the String is reversed.

+ The advantage of an array implementation of stack is simplicity. The disadvantage is lack of expansion, i.e. the size of the stack is preset.

+ The advantage of a linked list implementation of stack is automatic expandability. The disadvantage is complexity, but the linked list is probably a better idea.

Now lets see how we can implement Stacks. As we know, there 2 ways of implementing Stacks. One is using Arrays and another one is using Lists. Both ways follows the same algorithm.

Stack Algorithms (These are my steps, what i have understood from the book)





These are 4 basic operations. Other operations are just for facilitating Stack to perform these operations. Just like CreateStack, DisplayStack etc.. methods. Whatever the implementation type the basic algorithms are same. We know that each algorithm will have Time Complexity. From the above algorithms, we can say that the time complexity of Stack is O(1).