### *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