Algorithms‎ > ‎Data Structures‎ > ‎

Stacks

 Stacks- A stack is an ordered list in which insertions and deletions are made at one end called top- Let stack S = (a0; a1 : : : ; an -1)- a0 is known as bottom element- an -1 is called top element- Stack is also known Last-In-First-Out(LIFO) list   System Stack- Program uses system stack when it calls a function- Activation record or Stack frame is created by the program and is placed on top of the system stack- Initially it contains a pointer to previous stack frame and return address- Function to be executed is the one whose stack frame is on the top of the stack- Local variables and parameters of the function is stored in the frame if the function calls another function- Stack frame is removed on termination of the execution of the function   Stack Implementation- One dimensional array: stack[MAX STACK SIZE]- Bottom is at stack- Initially, top is set to -1 to denote empty stack  ``` Stack CreateS(max_stack_size)::= #define MAX_STACK_SIZE 100typedef struct {  int key;  /* Other fields */} element; element stack[MAX_STACK_SIZE];int top = -1;Boolean IsEmpty(Stack) ::= top < 0 ;Boolean IsFull(Stack) ::= top >= MAX_STACK_SIZE - 1 Stack Add(stack,item) ::=void add(int *top, lement item){  if(*top >= MAX_STACK_SIZEe - 1)   {    stack_full();    return;  }  stack[++*top] = item;} Element Delete(stack) ::=element delete(int *top){  if(*top == -1)    return stack_empty();    return stack[(*top)--];}```     Evaluation of Expressions- An expression: x = a / b - c + d * e - a * c- Precedence rules and Associativity- Operator with highest precedence is evaluated first- Parentheses overrides the precedence- Innermost parentheses evaluated first- Notations: Infix, Prefix, and Postfix   Postfix Notation- Evaluation of expression in postfix notation is easier compared to infix notation- Postfix notation is parentheses free- Only one left to right scan is required- Compiler generates postfix expression- Each operator appears after its operands   Postfix Expression Evaluation- Scan the posfix expression from left to right- Place the operands on the stack till you find an operator- Remove the required number of operands from the stack for the operator- Evaluate the operator and put the result on the stack- Continue this till you reach at the end of the expression- Remove the answer from top of the stack     Infix to Postfix- Fully parenthesize the expression- Move all binary operators so that they replace their corresponding right parenthese- Delete all parentheses- Example:a/b - c + d * e - a * c- ((((a/b) - c) + (d * e)) - a * c))- ab/c - de * + ac * -- Two pass required over expression   One Pass Infix to Postfix- Order of operands are same both in infix and postfix- Scan infix from left to right and pass the operands to the output expression as they are encountered- The order in which operators are passed to the output depends on their precedence- Higher precedence operator must be passed first- Save the operators until their correct placement     Precedence of Left Parentheses- Left parentheses has low precedence when it is on the stack and high precedence when it is unstacked- Left parentheses are placed on the stack whenever it is found in the expresion- It is unstacked only when its matching right parentheses is found- Two types of precedence:   in-stack-precedence(isp) and   incoming-precedence(icp)