Data Structures - Stack and Queue - Unit 2 PDF

Data Structures Stack and Queue Unit-2 Stack and Queue Q.1 Explain stack data structure in detail. Stack Stack is a linear list in which insertion and deletion operations are performed at only one end of the...

Data Structures Stack and Queue Unit-2 Stack and Queue Q.1 Explain stack data structure in detail. Stack Stack is a linear list in which insertion and deletion operations are performed at only one end of the list. A stack is generally implemented with only two operations: PUSH and POP. The insertion operation is referred to as a PUSH operation. The deletion operation is referred to as a POP operation. A pointer TOP keeps track of the top element in stack. Initially when the stack is empty, TOP has a value of zero and when the stack contains a single element: TOP has a value of one and so on. Each time a new element is inserted in the stack the TOP pointer is incremented by one and the pointer is decremented by one when element is deleted. Example – pile of tray in cafeteria. Q.2 Explain Push and Pop operation of stack with algorithm. PUSH Operation To insert an element on the TOP of the stack is called PUSH operation. Algorithm for PUSH Operation PUSH(S, TOP, X) This algorithm inserts an element on top of the stack. S represents stack. TOP is a pointer which points to the top of the stack. Step 1: [check for stack overflow] if (TOP>=N) then write (“Stack is Overflow”) return () Step 2: [Increment TOP] TOP ← TOP +1 Step 3: [Insert element] S[TOP] ← X Step 4: [finished] return ()  Data Structures Stack and Queue Unit-2 POP Operation To remove an element from the TOP of the stack is called POP operation. Algorithm for POP Operation POP (S, TOP) This algorithm removes an element from the top of the stack. S represents stack. TOP is a pointer which points to the top of the stack. Step 1: [Check for stack underflow] If (TOP = 0) then write(“Stack is underflow”) return (0) Step 2: [Delete an element] Y ← S[TOP] Step 3: [Decrement pointer] TOP ← TOP - 1 Step 4: [return deleted element] return(Y) Q.3 Explain applications of stack. Applications of Stack Three main applications of stack are: (1) Recursion (2) Stack machines (3) Polish notation. The recursive function is called function call to itself. Stack machine provides faster execution of polish notation. Better used for stacking local machines. It is used for representation of arithmetic expression. The process of writing the operators of an expression either before those operands or after operands are called the Polish Notation. There are basically three types of polish notation: Infix, Prefix, Postfix Recursion Recursion is a problem solving approach in which a problem is solved using repeatedly applying the same solution to smaller instances. Recursive function is a programming technique that allows the programmer to express operations in terms of themselves. The recursive function is called function call to itself. Stack machines Stack machine provides faster execution of polish notation. Better used for stacking local machines. Polish notation It is used for representation of arithmetic expression. The process of writing the operators of an expression either before those operands or after operands are called the Polish Notation. There are basically three types of polish notation: Infix, Prefix, Postfix  Data Structures Stack and Queue Unit-2 Q.4 Explain recursive functions with example. Recursive Functions Recursion is a problem-solving approach in which a problem is solved using repeatedly applying the same solution to smaller instances. Recursive function is a programming technique that allows the programmer to express operations in terms of themselves. The recursive function is called function call to itself. Factorial of Number The factorial function can be recursively defined as, Factorial(n) = 1 if n = 0 = n * factorial(n-1) if n > 0 Fibonacci series The function of Fibonacci series can be recursively defined as, Take n as input if n=0 or n=1 then, fibo(n) = 0 else if n=2 then, fibo(n) = 1 else fibo(n) = fibo(n-1) + fibo(n-2) Greatest Common Divisor The function of GCD can be recursively defined as, Take two inputs a and b In case of a ≠ b if a > b then, gcd(a,b) = gcd(a-b, b) else if a < b then, gcd(a,b) = gcd(a, b-a) In case of a = b, gcd(a,b) = a or b Q.5 Explain steps to convert infix expression to postfix expression using stack. 1) Print operands as they arrive. 2) If stack is empty or contains a left parenthesis on TOP, push the incoming operator onto the stack. 3) If incoming symbol is ‘(‘, push it onto stack. 4) If incoming symbol is ‘)’, pop the stack and print operators until left parenthesis is found. 5) If incoming symbol has higher precedence then the TOP of the stack. 6) If incoming symbol has lower precedence then the TOP of the stack, pop and print the TOP. Then test the incoming operator against the new TOP of the stack. 7) If incoming operator has equal precedence with the TOP of the stack, use associativity rule. 8) If expression ends then pop and print all operators of stack.  Data Structures Stack and Queue Unit-2 Q.6 Explain conversion from Infix to Postfix Expression for (a + b) * c – (d - e) Conversion from Infix to Postfix Expression Q.7 Explain Queue data structure in detail. Queue A queue is a linear list of elements in which deletion can take place only at one end, called the FRONT, and insertions can take place only at the other end, called the REAR. Queue is also called First-in-First-out (FIFO) lists. The term “front” and “rear” are used in describing a linear list only when it is implemented as a queue. Since the first element in a queue will be the first element out of the queue. In other words, the order in which elements enters a queue is the order in which they leave. Real life examples of Queue are a row of students at a registration center, a movie ticket window example, line of cars waiting to proceed at traffic signal etc. There are main two ways to implement a queue: 1. Circular queue using array 2. Linked Structures (Pointers)  Data Structures Stack and Queue Unit-2 Primary queue operations: Enqueue: insert an element at the rear of the queue Dequeue: remove an element from the front of the queue. Figure of Queue: Q.8 Define Circular Queue data structure. Circular Queue data structure A Circular queue is a queue in which data are arranged such that the first element in the queue follows the last element in the queue. When we are deleting an element from simple queue, front pointer is incremented by one and the previous place of front pointer becomes useless. If rear pointer reaches to last element, we cannot insert any more elements. So, wasting of memory is there, this problem is solved by Circular queue. Q.9 Explain operations of Simple Queue data structure. Operations on Simple Queue Insertion in Queue To insert an element at the REAR end is called INSERTION operation. Algorithm for INSERT operation Q_INSERT (Q, F, R, N, Y) This algorithm inserts an element into the queue. Q represents queue vector containing N elements. F and R are pointers pointing to the FRONT and REAR end. Initially F and R are set to 0. Step 1: [check for Queue overflow] if R ≥ N then write(“Queue is Overflow”) return (0) Step 2: [Increment REAR pointer] R ← R +1 Step 3: [Insert element] Q[R] ← X Step 4: [Set FRONT pointer] if F=0 then F ←1 return ()  Data Structures Stack and Queue Unit-2 Deletion in Queue To remove an element at the FRONT end is called DELETION operation. Algorithm for DELETE operation Q_DELETE (Q, F, R, N) Q represents queue vector containing N elements. F and R are pointers pointing to the FRONT and REAR end. Step 1: [Check for Queue underflow] if F = 0 then write(“Queue is underflow”) return (0) Step 2: [Delete element] Y ← Q[F] Step 3: [Check for Queue empty] If F = R then F ← 0 R←0 Else F←F+1 Step 4: [return element] return(Y) Q.10 Explain operations of Circular Queue data structure. Operations on Circular Queue Insertion in Circular Queue To insert an element at the REAR end is called INSERTION operation. Algorithm for INSERT operation CQ_INSERT (Q, F, R, N, Y) This operation inserts an element in the circular queue. Q represents Queue vector containing N elements. F and R are pointers pointing to the FRONT and REAR end. Y is the element to be inserted. Initially F and R are set to 0. Step 1: [Reset rear pointer] if R >= N then R ← 1 Else R ← R + 1 Step 2: [Overflow?] if F = R then write(“QUEUE OVERFLOW”)  Data Structures Stack and Queue Unit-2 return () Step 3: [Insert element] Q[R] ← Y Step 4: [Is front pointer properly set?] if F=0 then F ← 1 return () Deletion in Circular Queue To remove an element at the FRONT end is called DELETION operation. Algorithm for DELETE operation CQ_ DELETE (Q, F, R, N, Y) This operation deletes an element ad returns it from circular queue. Q represents Queue vector containing N elements. F and R are pointers pointing to the FRONT and REAR end. Y is temporary variable. Initially F and R are set to 0. Step 1: [Check for Queue underflow] if F = 0 then write(“Queue is underflow”) return (0) Step 2: [Delete element] Y ← Q[F] Step 3: [Check for Queue empty] if F = R then F ← 0 R←0 return(Y) Step 4: [Increment front pointer] if F = N then F ← 1 else F ← F + 1 return(Y) Q.11 Explain applications of Simple Queue data structure. Applications of Queue A queue is the natural data structure for a system to serve its incoming requests. Most of the process scheduling algorithm in operating system uses queues. Queues are used to schedule various jobs, tasks and processes for their execution by the CPU. Simulation is an application of Queue which allows experimenting without modifying the original situation.  Data Structures Stack and Queue Unit-2 Q.12 State the limitations of a Simple Queue and explain Circular Queue data structure. 1) The limitation of simple Queue is that even if we have free spaces, we cannot use these memory spaces. So, simple queue results in wastage of memory. This problem can be solved by using Circular Queue. 2) A Circular queue is a queue in which data are arranged such that the first element in the queue follows the last element in the queue. 3) When we are deleting an element from simple queue, front pointer is incremented by one and the previous place of front pointer becomes useless. 4) If rear pointer reaches to last element, we cannot insert any more elements. So wasting of memory is there, this problem solved by Circular queue. 5) As by moving ahead, when front pointer or rear pointer reaches at last in the next move it moves to the first position.