Stack in Data Structure
Points for Stack:-
1. Introduction.
2. Implementations.
3. Primitive Operation.
4. Fundamental terms on stack.
5. Application on stack.
| Introduction A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. a stack is sometimes called a last-in, first-out (or LIFO) list. |
| Real life examples Pile of papers, plates, books, and cloths. |
 Way of Stack |
| Implementations i. Static implementation (Using array) ii. Dynamic implementation (Using Linked list) |
| Primitive Operation. Push: When, an item is added to a stack, it is pushed onto the stack. CODE EX. void push (int val,int n) //n is size of the stack { if (top == n ) printf(“\n Stack Overflow”); else { top = top +1; stack[top] = val; } } Pop: When an item is removed, it is popped from the stack. CODE EX. int pop () { if(top == -1) { printf(“Stack Underflow”); return 0; } else { return stack[top – – ]; } } isEmpty (): Why we need to apply this function. Before pop operation, we should have to check whether stack is empty or not. The operation isempty(s) determines whether a stack is empty or not. If the stack is Empty, isempty(s) returns the value TRUE. Otherwise it returns the value FALSE. Stack Top (): This operation Stack_Top(s) returns the top element of stacks without removing it. isFull(): Used to determines whether the stack is full or not.’ peek(): Used to returns the element at the given position. count(): Used to returns the total number of elements available in a stack. change(): Used to changes the element at the given position. display(): Used to prints all the elements available in the stack. |
| Fundamental terms on stack Stack Representation of array with max size. Context During function execution variables are store in stack like argument values, local variable, all are stored in stack frame expect global variables. Stack Frames Whenever function or procedure are called programs need same data structure to store all data such as argument values, local variables, return address. MAXSIZE It is fundamental terms to know the maximum size of stack. Stack underflow When we are going to perform POP operation on empty stack that is Stack Underflow condition. At this time top of the stack is present at the bottom of the stack. CODE EX. if top == -1\ printf(” \n Stack Underflow”); Stack overflow When we are going to perform PUSH operation on Full stack that is Stack Overflow condition. At this time top of the stack is present at the highest level of the stack. CODE EX. if (top == n ) printf(“\n Stack Overflow”); |
| Application on stack 1) Evaluating postfix expressions & infix to postfix conversion 2) Implementing function calls 3) Implementation depth first search & Breadth First search 4) Implementation of recursion 5) Expression evaluation and syntax parsing 6) Backtracking 7) Compile time memory management 8) Reverse a string 9) Expression Conversion 10) Browsing 11) Parenthesis Checking 12) Text editor/MS word (Undo sequence) 13) HTML and XML (Matching Tags) 14) Tree traversing & Graph traversing 15) Implementation of priority queues 16) CPU scheduling & Disk Scheduling 17) Synchronization (IO Buffers, pipes, file IO, etc.) |