Stack Data Structure PDF

Stack Prepared By: Dr. Asmaa Awad  Stack A Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out). LIFO implies that the element that is inserted last, comes out first In...

Stack Prepared By: Dr. Asmaa Awad  Stack A Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out). LIFO implies that the element that is inserted last, comes out first In a stack, addition of a new element and deletion of an element occurs at the same end which implies that the element which is added last in the stack will be the first to be removed from the stack. 2  Stack It behaves like a stack of plates, where the last plate added is the first one to be removed. Think of it this way: Pushing an element onto the stack is like adding a new plate on top. Popping an element removes the top plate from the stack. 3  Stack Types Fixed Size Stack : As the name suggests, a fixed size stack has a fixed size and cannot grow or shrink dynamically. If the stack is full and an attempt is made to add an element to it, an overflow error occurs. If the stack is empty and an attempt is made to remove an element from it, an underflow error occurs. Dynamic Size Stack : A dynamic size stack can grow or shrink dynamically. When the stack is full, it automatically increases its size to accommodate the new element, and when the stack is empty, it decreases its size. This type of stack is implemented using a linked list, as it allows for easy resizing of the stack. 4  Create Stack Representation of Stack Data Structure: 5  Operation on Stack push() to insert an element into the stack pop() to remove an element from the stack top() Returns the top element of the stack. isEmpty() returns true if stack is empty else false. isFull() returns true if the stack is full else false 6  Push Operation in Stack Adds an item at top of the stack. If the stack is full, then it is said to be an Overflow condition in fixed size. 7  POP Operation in Stack Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition. 8  POP Operation in Stack Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition. 9  Top or Peek in Stack Returns the top element of the stack. 10  Top or Peek in Stack Returns the top element of the stack. 11  isEmpty Operation in Stack Returns true if the stack is empty, else false. 12  isEmpty Operation in Stack Returns true if the stack is empty, else false. 13  Size Operation Return number of element in stack 14 15  Advantages of Stack Simplicity: Stacks are a simple and easy-to-understand data structure, making them suitable for a wide range of applications. Efficiency: Push and pop operations on a stack can be performed in constant time (O(1)) , providing efficient access to data. Last-in, First-out (LIFO): Stacks follow the LIFO principle, ensuring that the last element added to the stack is the first one removed. This behavior is useful in many scenarios, such as function calls and expression evaluation. Limited memory usage: Stacks only need to store the elements that have been pushed onto them, making them memory-efficient compared to other data structures. 16  Disadvantages of Stack Limited access: Elements in a stack can only be accessed from the top, making it difficult to retrieve or modify elements in the middle of the stack. Potential for overflow: If more elements are pushed onto a stack than it can hold, an overflow error will occur, resulting in a loss of data. Not suitable for random access: Stack s do not allow for random access to elements, making them unsuitable for applications where elements need to be accessed in a specific order. Limited capacity: Stacks have a fixed capacity, which can be a limitation if the number of elements that need to be stored is unknown or highly variable. 17  Applications of Stack Infix to Postfix /Prefix conversion Redo-undo features at many places like editors, photoshop. Forward and backward features in web browsers In Memory management, any modern computer uses a stack as the primary management for a running purpose. Each program that is running in a computer system has its own memory allocations. Stack also helps in implementing function call in computers. The last called function is always completed first. 18  Infix to postfix Consider the infix expression exp = “a+b*c+d” 1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the postfix expression. Therefore, postfix = “a”. 19  Infix to postfix Consider the infix expression exp = “a+b*c+d” 2nd Step: Here i = 1 and exp[i] = ‘+’ i.e., an operator. Push this into the stack. postfix = “a” and stack = {+}. 20  Infix to postfix Consider the infix expression exp = “a+b*c+d” 3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the postfix expression. postfix = “ab” and stack = {+}. 21  Infix to postfix Consider the infix expression exp = “a+b*c+d” 4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the stack. postfix = “ab” and stack = {+, *}. 22  Infix to postfix Consider the infix expression exp = “a+b*c+d” 5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the postfix expression. postfix = “abc” and stack = {+, *}. 23  Infix to postfix Consider the infix expression exp = “a+b*c+d” 6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost element of the stack has higher precedence. So pop until the stack becomes empty or the top element has less precedence. ‘*’ is popped and added in postfix. So postfix = “abc*” and stack = {+}. 24  Infix to postfix Consider the infix expression exp = “a+b*c+d” Now top element is ‘+‘ that also doesn’t have less precedence. Pop it. postfix = “abc*+”. 25  Infix to postfix Consider the infix expression exp = “a+b*c+d” Now stack is empty. So push ‘+’ in the stack. stack = {+}. 26  Infix to postfix Consider the infix expression exp = “a+b*c+d” 7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the postfix expression. postfix = “abc*+d”. 27  Infix to postfix Consider the infix expression exp = “a+b*c+d” Final Step: Now no element is left. So empty the stack and add it in the postfix expression. postfix = “abc*+d+”. 28 Infix to postfix 29 Infix to postfix 30  Infix to postfix Simulate the conversion of infix to postfix expression using stack for the following expression : 3-(4/2)+(1*5)+6. 31  Infix to postfix Simulate the conversion of infix to postfix expression using stack for the following expression : 3-(4/2)+(1*5)+6. 32  Infix to postfix Show the simulation using stack for the following expression to convert infix to postfix: p*q+ (r-s/t) 33  Infix to postfix Show the simulation using stack for the following expression to convert infix to postfix: p*q+ (r-s/t) 34