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 … Continue reading “Stack Overview | My Assignment Tutor”
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 operations 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.) Don’t forgot to decrement toppublic 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 elementspublic void printStack() { if (top == -1) { Console.WriteLine(“Stack is Empty”); return; } else {for (int i = 0; i
