# ds

Published on April 17, 2009

Author: aSGuest16945

Source: authorstream.com

A stack is a list of elements in which an element may be inserted or deleted only at one end , called the top of the stack. Special terminology is used for two basic operations associated with stacks:1.”PUSH” is the term used to insert an element into a stack.2.”pop” is the term used to delete an element from a stack. : A stack is a list of elements in which an element may be inserted or deleted only at one end , called the top of the stack. Special terminology is used for two basic operations associated with stacks:1.”PUSH” is the term used to insert an element into a stack.2.”pop” is the term used to delete an element from a stack. Slide 2: A linear array is used to represent the stack. A pointer variable TOP , which contains this location of the top element of stack, and a variable MAX which gives the maximum number of elements that can be held by stack. The condition TOP=0 or TOP=NULL will indicate that THE STACK IS EMPTY KNOWN AS underflow. THE condition TOP=MAX will indicate that the stack is full known as OVERFLOW. Slide 3: PUSH(stack,max, ITEM,top): this procedure pushes an item onto a stack. Step1: Begin Step2: if TOP=MAX, then Write: OVERFLOW , and return. Step3: Set TOP=TOP+1. Step4: Set STACK[TOP]=ITEM. Step5: Return. Slide 4: POP(stack,TOP, ITEM): this procedure deletes the top element of stack and assigns it to the variable ITEM.. Step1: Begin Step2: if TOP=NULL, then Write: UNDERLOW , and return. Step3: Set ITEM=STACK[TOP]. Step4: Set TOP=TOP-1 Step5: Return. Slide 5: A queue is a linear list of elements in which deletions can take place only at one end., called FRONT, and insertions can take place only at the other end called REAR. The terms front and rear are used in describing a linear list only when it is implemented as a queue. Queues are also called first in first out FIFO) lists i.e.., the order in which elements enter a queue is the order in which they leave. Considering everyday life example, the people waiting in line at a bank form a queue, where the first person in line is the first person to be waited on. Slide 6: Algorithm for insertion of element into a queue: Qinsert(queue,front,rear,item,maxqueue) Step1: begin Step2: if rear =maxqueue then write ‘queue is full’,return Step3:If front =0 and rear = 0 then front=1,rear=1 else rear=rear+1 end if Step4: Set queue[rear]= item [this inserts a new element] Step4:return Slide 7: Algorithm for deletion of element from a queue: qdelete(queue,front,rear,item) Step1: begin Step2: if front =NULL then Write UNDERFLOW and return Step3:Set ITEM = queue [front ] Step 4: [find the new value of front] If front=rear, then Set front=NULL and rear=NULL Else Set front= front+ 1 Step5:return Applications of stack : Applications of stack Conversion of infix expression to postfix Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression P. Step1: Begin Step2:Push ‘( ‘onto STACK , and add”)” to the end of the Q. Step3:Scan Q from left to right and repeat steps4 to 7 for each element of Q until the STACK is empty. Step4: If an operand is encountered , add it to P. Step5: If a left paranthesis is encountered, push it onto STACK. Slide 9: Step6: If an operator x is encountered, then (a) Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has the same precedence as or higher precedence than x. (b) Add x to STACK. [end of IF structure ] step7: If a right paranthesis is encountered, then (a) )Repeatedly pop from STACK and add to P each operator (on the top of STACK) until a left paranthesis is encountered. (b) Remove the left paranthesis. [do not add left paranthesis to P ] [end of if structure ] [end of step3 loop] step8: End. Ex: A+(B*C-(D/E\$F)*G)*H : Ex: A+(B*C-(D/E\$F)*G)*H

17. 04. 2009
0 views

17. 04. 2009
0 views