Algorithm and Data structure: Stack and queues

STACK
A stack is a constrain version of list, with the restriction that insertion and deletions can be performed in only one position that is at the end of the list. This position is call top.
For this reason, stack is referred to as Last-In, First-Out (LIFO) ADT


Array Implementation
For array implementation, we only need to declare an array for stack data and an integer variable to mark the top of stack index
Array implementation of stack is much simpler, however it possesses the limitation to be fixed sized



Application of Stack
•Applications that use stack ADT:
–Balancing Symbol
–Converting Infix to Postfix Expression
–Evaluating Postfix Expression
–Function Call


•Balancing Symbol
–Check a mathematics expression to ensure that the parentheses are balance

•Evaluating Postfix Expression
–A stack is also being used to evaluates postfix expression, i.e. to calculate the value produces by the postfix expression
–When a number is seen, we push onto the stack;
–When an operator is seen, the operator is applied to the two numbers that are popped from the stack.
–The result is then pushed onto the stack


Queues

•Queue are list •With queue, insertion is done at one end whereas deletion is performed at the other end. •Queue is referred as First-In, First-Out (FIFO) ADT •Queue can be implemented using array or linked list •Pointers in the queue implementation: –Head –Tail •Node process: –Enqueue: is done through the tail pointer –Dequeue: is done through the head pointer