Stack & Queue Data Structures PDF

Unit-2 Stack & Queue  Stack  Stack is an important data structure which stores its elements in an ordered manner.  Take an analogy of a pile of plates where one plate is placed on top of the other as shown in the following figure.  A plate can be removed...

Unit-2 Stack & Queue  Stack  Stack is an important data structure which stores its elements in an ordered manner.  Take an analogy of a pile of plates where one plate is placed on top of the other as shown in the following figure.  A plate can be removed from the topmost position. Hence, you can add and remove the plate only at/from one position that is, the topmost position  Stack  “A stack is a linear data structure which can be implemented either using an array or a linked list”.  The elements in a stack are added and removed only from one end, which is called top.  Hence, a stack is called a LIFO (Last In First Out) data structure as the element that was inserted last is the first one to be taken out.  Array representation of Stack  In computer memory, stacks can be represented as a linear array.  Every stack has a variable TOP associated with it.  TOP is used to store the address of topmost element of the stack.  There is another variable named MAX which will be used to store the maximum number of elements that the stack can hold.  If TOP=NULL means that the stack is Empty.  If TOP=MAX-1 means that the stack is Full.  Array representation of Stack  An example stack :  The stack in above figure shows that TOP=4, so insertions and deletions will be done at this position.  In this stack, five more elements can still be stored.  Operations on a Stack  A stack has four basic operations: 1. Push: adds an element to the top of the stack. 2. Pop: removes the element from the top of the stack. 3. Peek: returns the value of the topmost element of the stack of specified index. 4. Update: changes the value of element given by user of the stack.  1. Push Operation  The PUSH operation is used to insert an element into the stack.  The new element is added at the topmost position of the stack.  However before inserting the value, we must first check if TOP=MAX-1, as it would mean that the stack is full and no further insertions can be done on it.  If an attempt is made to insert an element in a stack that is already full, an OVERFLOW message is printed.  1. Push Operation  An example of stack:  Stack after insertion:  1. Push Operation  Algorithm to insert an element in a stack:  2. Pop Operation  The POP operation is used to delete an element from the stack.  However before deleting the value, we must check if TOP=NULL, as it would mean that the stack is empty and therefore no further deletions can be done on it.  If an attempt to delete a value from a stack that is already empty is made, an UNDERFLOW message is printed.  2. Pop Operation  Stack after deletion:  Algorithm to delete an element from the stack:  3. Peek Operation  PEEK is an operation that returns the value of the element of the stack of specified index without deleting it from the stack.  3. Peek Operation  Given a vector S (consisting of N elements) representing a sequentially allocated stack, and a pointer TOP denoting the top element of the stack, this function returns the value of the Ith element from the top of the stack. The element is not deleted by this function.  4. Update Operation  UPDATE is an operation that updates or changes the value of specified element with specific index.  However, the update operation first checks if the stack is empty or contains some element.  Applications of Stack  Recursion  Balancing Symbol  Polish Notations  Recursion  A function calls itself is called Recursion.  Recursion is a repetitive process in which function calls itself repeatedly until some predefined condition is met.  The recursive function must have a stopping condition (Termination/ Anchor Condition) or else the function would never terminate. So ultimately program goes into infinite loop.  Examples where recursion has been used are: Factorial, Fibonacci sequence (number) and Tower of Hanoi, etc.. Programming (factorial with iteration) Programming (factorial with recursion) By : Prof. Nootan Padia, Marwadi University  Recursion #include #include int factorial(int n); void main() { int n,z; clrscr(); printf("\n Enter Value : "); scanf("%d",&n); z=factorial(n); printf("\n Factorial is : %d",z); }  Recursion int factorial(int n) { int f; if(n