Stack in Data Structure
Points for Stack:-
3. Primitive Operation.
4. Fundamental terms on stack.
5. Application on stack.
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
i. Static implementation
ii. Dynamic implementation
(Using Linked list)
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”);
top = top +1;
stack[top] = val;
When an item is removed, it is popped from the stack.
CODE EX. int pop ()
if(top == -1)
return stack[top – – ];
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.
Used to determines whether the stack is full or not.’
Used to returns the element at the given position.
Used to returns the total number of elements available in a stack.
Used to changes the element at the given position.
Used to prints all the elements available in the stack.
|Fundamental terms on stack|
Representation of array with max size.
During function execution variables are store in stack like argument values, local variable, all are stored in stack frame expect global variables.
Whenever function or procedure are called programs need same data structure to store all data such as argument values, local variables, return address.
It is fundamental terms to know the maximum size of stack.
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”);
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
7) Compile time memory management
8) Reverse a string
9) Expression Conversion
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.)