stack_operationss_documentation_file.ppt

A linked list is a data structure consisting of nodes where each node contains data and a reference (or pointer) to the next node in the sequence. The key features are:

1. **Node Structure**: Each node has two parts: data and a next pointer.
2. **Head**: The first node in the list is called the head.
3. **Traversal**: To access elements, start at the head and follow the next pointers.
4. **Insertion**: Can be done at the beginning, end, or any position by updating pointers.
5. **Deletion**: Remove a node by changing the pointer of the previous node to skip the deleted node.
6. **Types**: Singly linked list (one next pointer per node) and doubly linked list (nodes also have a previous pointer).
7. **Dynamic Size**: Linked lists can grow or shrink in size dynamically.
8. **Memory Use**: More memory per element due to storage of pointers.
9. **Efficiency**: Efficient insertion/deletion but slower access compared to arrays.
10. **Applications**: Useful in implementing other data structures like stacks, queues, and graphs.

1. Stack Data Structure

2. What is a Data Structure Data Structure is a way to store and organize data so that it can be used efficiently. It is a special format for organizing and storing data. Data Structures Linear Structure Linked List Stack Queue Non Linear Structure Graph Tree

3. Abstract Data Types To simplify process of problem solving, we combine data structure with their operations and call this Abstract Data Types (ADT) It consists of 2 parts Declaration of Data Declaration of Operations

4. What is Stack A stack is an ordered list in which insertion and deletion are done at one end, called top . The last element inserted is the first one to be deleted. Hence it is called Last In First Out(LIFO) or First In Last Out(FILO).

5. Stack ADT

6. Stack Operations Operation Description push(int data) inserts data into stack int pop() removes and returns last inserted element int top() returns last inserted element int size() returns number of elements in stack int isEmpty() indicate if any element is stored or not int isFull() indicates if stack is full or not

7. Stack Applications Balancing of Symbols Infix to Postfix conversion Evaluation of postfix expression Implementing function calls History of a web browser Undo Sequence Tree Traversal

8. Working TOP = 0 MAX = 5 10 TOP = 1 MAX = 5 CREATE STACK SIZE 5 PUSH(10)

9. Working 10 20 TOP = 2 MAX = 5 10 20 30 TOP = 3 MAX = 5 PUSH(30) PUSH(20)

10. Working 10 20 30 40 TOP = 4 MAX = 5 10 20 30 TOP = 3 MAX = 5 POP() PUSH(40)

11. Working 10 20 TOP = 2 MAX = 5 10 TOP = 1 MAX = 5 POP() POP()

12. Working TOP = 0 MAX = 5 FULLSTACK() EMPTYSTACK() 10 20 30 40 50 TOP = 4 MAX = 5

13. Implementation by Array Advantages Best Performance Disadvantages Fixed Size Basic Implementation Initially Empty Array Field to record where next data is placed if array is full, push(item) else return false if array is empty, pop() return item on top else NULL

14. Implementation by Array CREATING STRUCTURE struct ArrayStruct{ int top; //Keep track of top Element int capacity; //capacity of the stack int *array; //pointer to address of first index } Space Complexity (for n operations)– O (n)

15. Implementation by Array isEmpty() { return (S->top == -1); } Time Complexity O(1) isFull(){ return(S->top==S->capacity-1); } Time Complexity O(1)

16. Implementation by Array void push(struct Array *S,int data){ if(isFull(S)) cout<<“FULL”; else S->array[++S->top]=data; } 
 Time Complexity O(1) int pop(struct Array *S){ if(isEmpty(S)){ cout<<“EMPTY”; return;} else return (S->array[S->top]); } Time Complexity O(1)

17. Linked List Implementation Advantages Always constant time to push and pop can grow to an infinite size Disadvantages can grow to infinite size common case is slowest of all Basic Implementation Initially Empty List push() add item on top pop() removes item on top

18. Linked List Implementation void push(struct node **top,int d){ struct node *temp; temp->data=d; temp->link=(*top); *temp = temp; } 
 Time Complexity O(1) void pop(struct node **top){ struct node *temp; int i; temp=(*top); i=temp->data; *top = (*top)->link; return i; } Time Complexity O(1)

19. Use of stack EVALUATING POSTFIX = 123*+5- Stack Expression STEP 1 2 3 1 Stack Expression STEP 2

20. Use of stack EVALUATING POSTFIX = 123*+5- 1 Stack Expression 2*3=6 STEP 3 6 1 Stack Expression STEP 4

21. Use of stack EVALUATING POSTFIX = 123*+5- Stack Expression 1+6=7 STEP 5 7 Stack Expression STEP 6

22. Use of stack EVALUATING POSTFIX = 123*+5- 5 7 Stack Expression STEP 7 Stack Expression 7-5=2 STEP 8

23. Use of stack EVALUATING POSTFIX = 123*+5- 2 Stack Expression STEP 9 123*+5- RESULT POSTFIX STRING 2

24. References Data Structures and Algorithms, Narsimha Karumanchi https://www.geeksforgeeks.org/stack-data-structure/ https://www.geeksforgeeks.org/tag/data-structures-stack/