Data Structure
UNIT: - 4.1
STACKS AND QUEUES: -
Representation of Stack using arrays and linked list
Stack: -
1. Stack is an abstract data type with a bounded capacity and it is a simple data structure that allows adding and removing elements in a particular order.
2. A stack is a linear and non-primitive data structure in which element is added or removed from the “TOP” of the stack.
3. Stack is an order list in which addition of data items and deletion of existing data items is done from only one end known as top of stack (TOS) that’s why stack is also called Last In First Out (LIFO) and follow LIFO principle.
4. Stack contains only one pointer “top pointer” pointing to the topmost element of the stack.
Stack basic features: -
1. Stack is an ordered list of similar data type.
2. Stack follows LIFO (Last in First out) and we can also say that FILO (First in Last out) principle.
3. Push() is used to insert new element into the stack and Pop() is used to remove or delete an element from the stack.
4. When the stack is completely full then it will said Overflow condition and when it is empty then it will said Underflow condition.
Applications of stack: -
1. A stack is useful to convert infix expression into postfix expression.
2. A stack is useful in writing recursive calls and function call.
3. Redo-undo features at many places like editors, Photoshop etc.
4. A stack is useful to evaluate the value of postfix expression.
5. Compiler uses stack to check parenthesis matching.
6. A stack is also used in string processing to evaluate reverse of a string.
7. Stack is used in many algorithms like tower of Hanoi, tree traversal, histogram program, etc.
Stack data structure can be represented in two different ways:-
1. Static Implementation
Static implementation is done by using array.
2. Dynamic Implementation
Dynamic implementation is done by using linked list.
The basic operations associated with stacks are: -
1. PUSH(): - PUSH() is the term used to insert an element into the top of stack.
2. POP():- POP() is a term used to delete an element from a the top of stack.
3. PEEK(): -PEEK() is used to get the top most element of the stack without deleting them.
Array implementation of stack:-
1. Stack can be implementing by using array usually be means of 1-D array.
2. Top is a variable pointer which points the top most element of the stack whose initial value is -1 and when we add any element into stack its value increased by one and decrease by one when we delete an element.
3. When insertion (PUSH()) operation is performed the Top incremented by 1 before element is placed in the stack [Top = Top + 1].
4. When deletion (POP()) operation is performed the Top decremented by 1 [Top = Top - 1].
5. Max_size is a variable which gives maximum number of element hold by the stack.
6. Two condition of stack: -
a. Overflow (Stack is full):(Top = = Max_size - 1).
b. Underflow (Stack is empty): (Top = = -1)
Algorithm of basic operation of the array implementation: -
PUSH(): -
Step 1: - Check whether the stack is full.
if(Top == Max_size -1)
printf(“Stack is overflow”);
return;
Step 2: - Increment the pointer Top
Top = Top + 1;
Step 3: - Insert item at the Top
Stack[Top]=Element;
Step 4: - return;
POP(): -
Step 1: - Check whether the stack is empty.
if(Top == -1)
printf(“Stack is underflow”);
return;
Step 2: - Retrieving the top most element from stack into a temporary variable k.
k = Stack [Top];
Step 3: - Decrement the pointer Top
Top = Top - 1;
Step 4: - return (k);
Implementation of stack using Linked List:-
1. A stack can be represented using linked list in which it uses nodes of the liked list and liked list allocate the memory dynamically.
2. Each node contains two field data field and next field.
3. The data field of each node contains an item in the stack and the corresponding next field points to the node containing the next item in the stack.
4. The next field of the last node is NULL i.e. the bottom of the stack and the Top refers to the top most node (the last item inserted) in the stack.
5. The empty stack is represented by setting Top to NULL.
Infix, Postfix and Prefix Expression and its conversion: -
In general, simple arithmetic expression can be represented in three ways
1. Infix expression
2. Postfix expression
3. Prefix expression
Infix Expression: -
1. In the infix expression the binary operator symbol is lie between the two operands.
2. Infix expression can be determined as <operand> <operator> <operand>.
3. Example: - A + B * C in an infix expression.
Postfix Expression:
1. In postfix expression the binary operator symbol is placed after both operands, i.e. the operator follows the operands.
2. Postfix expression can be determined as <operand> <operand> <operator>.
3. Example: -A B C * + in a postfix expression.
Prefix Expression:
1. In prefix expression the operator symbol is placed before both operands, i.e. the operator precedes both operands.
2. Prefix expression can be determined as <operator> <operand> <operand>.
3. Example: - + A * B C is a prefix expression.
Some example of Infix to prefix and postfix: -
Infix Prefix Postfix
1. A+B*C +A*BC ABC*+
2. (A+B)*C *+ABC AB+C*
3. A+(B*C)/D +/A*BCD ABC*D/+
4. C/D*E */CDE CD/E*
***************THE END**************
End of part-1 (Stack), part-2 (Queue) will uploaded soon.
Comment if you like my notes and please share it with your friends.
For more information whats_app:- 8873466244
Follow on Instagram:- mohit13kumar1
For more information contact us: - Click me
Or follow our FACEBOOK page @diploma.1234
Thank you sir
ReplyDeleteNice notes
Very useful and understanding language notes
ReplyDeleteThank you sir
Very helpful and useful for us sir...🙏
ReplyDeleteThanq so much sir🙂🙃
Thank you❤ sir very useful
ReplyDeleteThanks❤ sir
ReplyDelete