24/10/20181DataStructure:StackLECTURE 2Stack Overview? Stack ADT? Basic operations of stack? Pushing, popping etc.? Implementations of stacks using? array? linked list24/10/20182The Stack ADT? Stack is a linear data structure which follows aparticular order in which the operations areperformed. The order may be LIFO(Last In FirstOut) or FILO(First In Last Out).? Fundamental operations:? Push: Equivalent to an insert? Pop: Deletes the most recently inserted element? Top: Examines the most recently inserted element? Size: Number of elements a stack contains at present? Capacity: Number of elements it is capable of holdingStack ADT? Stacks are less flexible? but are more efficient and easy to implement? Stacks are known as LIFO (Last In, First Out) lists or orFILO(First In Last Out)?The last element inserted will be thefirst to be retrieved.Implementation:There are two ways to implementa stack: Using array Using linked list.24/10/20183Applications of Stack? Balancing of symbols? Infix to Postfix /Prefix conversion? Redo-undo features at many places like MicrosoftUNDO button or in photoshop.? Forward and backward feature in web browsers? Used in many algorithms like Tower of Hanoi, treetraversals, stock span problem, histogram problem.? Other applications can be Backtracking, Knight tourproblem, rat in a maze, N queen problem and sudokusolver? In Graph Algorithms like Topological Sorting andStrongly Connected Components.Push and Pop? Primary operations: Push and Pop? Push? Add an element to the top of the stack? Pop? Remove the element at the top of the stack Atop topempty stacktoptoppush an element push another B A pop A 24/10/20184Array Implementation? Need to declare an array size ahead of time? Associated with each stack is TopOfStack? for an empty stack, set TopOfStack to -1? Push? (1) Increment TopOfStack by 1.? (2) Set Stack[TopOfStack] = X? Pop? (1) Set return value to Stack[TopOfStack]? (2) Decrement TopOfStack by 1? These operati
ons are performed in very fast constant timeStack class? class Stack? {? private int[] ele; // name of the array for stack? private int top; // storage index? private int max; // total capacity? public Stack(int size)? {? ele = new int[size];//Maximum size of Stack? top = -1;? max = size;? }24/10/20185Stack class? Attributes of Stack? maxTop: the max size of stack? top: the index of the top element of stack? values: point to an array which stores elements of stack? Operations of Stack? IsEmpty: return true if stack is empty, return false otherwise? IsFull: return true if stack is full, return false otherwise? Top: return the element at the top of stack? Push: add an element to the top of stack? Pop: delete the element at the top of stack? DisplayStack: print all the data in the stackPush Stack? void Push(const double x);? Push an element onto the stack? If the stack is full, print the error information.? Note top always represents the index of the top element.After pushing an element, increment top.?public void push(int item)? { if (top == max 1)? { Console.WriteLine(Stack Overflow);? return; }? else? { ele[++top] = item; }? }24/10/20186Pop Stack? double Pop()? Pop and return the element at the top of the stack? If the stack is empty, print the error information. (In this case,the return value is useless.)? Dont forgot to decrement top?public int pop()? { if (top == -1)? { Console.WriteLine(Stack is Empty);? return -1; }? else? {Console.WriteLine({0} popped from stack , ele[top]);? return ele[top]; }? }Stack Top? double Size()? Return the size of the elements in stack? public int size()? {? if (top == -1)? {? Console.WriteLine(Stack is Empty);? }? else? { Console.WriteLine(Number of elements on the stack is , top);? }? return -1;? }24/10/20187Printing all the elements? void printstack()? Print all the elements?public void printStack()? {? if (top == -1)? { Console.WriteLine(Stack is Empty);? return; }? else? {for (int i = 0; i