Stack in C.pptx

Description of Stack in C language.

1. BRAINWARE UNIVERSITY stack NAME : RITU SARKAR STUDENT CODE : BWU/BTD/21/010 STREAM : B.TECH CSE(DS) COURSE : data structure & algorithms COURSE CODE : ESCD302

2. CONTENT Introduction What is Stack Properties of Stack Example Representation of Stack Operations of Stack Conditions of Stack Stack Implementation Using Array Stack Implementation Using Linked List Applications of Stack References 2 BWU/BTD/21/010

3. INTRODUCTION Data Structure is the representation of the logical relationship between individual elements of data. In Computer Science, Data Structure is defined as a mathematical or logical model of organizing the data items into computer memory in such a way that they can be used efficiently. The purpose of studying data structure is to learn how to organize data into memory so that it can be accessed quickly and conveniently. 3 BWU/BTD/21/010

4. WHAT IS STACK A stack is one of the most important and useful non-primitive linear data structure in computer science. Real-life examples of the stack are a stack of books, a stack of plates, a stack of cards, a stack of coins, etc. Definition : A stack is a sequential collection of elements into which new elements are inserted and from which, elements are deleted only at one end. PROPERTIES OF STACK It is an abstract data type. It is a First-In-First-Out (FIFO) data structure. It can be implemented using array as well as linked list. It has two main operations – Push ( insertion ) & Pop ( deletion ). In stack insertion and deletion is done at a single end that is a specific position, and the position is called top. A stack is declared as –   4 BWU/BTD/21/010

5. EXAMPLE OPERATIONS OF STACK There are two main operations in stack data structure – Creation Operation Isempty Operation Isfull Operation Push Operations Pop Operations Peek Operation The stack can be represented using the following structure:   REPRESENTATION OF STACK 5 BWU/BTD/21/010

6. Operation Description Creation This operation creates a stack and initializes the stack. Isempty This operation checks whether the stack empty or not. Isfull This operation checks whether the stack full or not. Insertion ( Push ) This operation inserts an item only at the top of the stack when the stack is not full. Deletion ( Pop ) This operation deletes an item only at the top of the stack when the stack is not empty. Peek This operation returns the value of the top of the stack without removing the element from the stack. Top = integer variable that points to the top location of the stack. Top = -1 ( If there is no data in the stack ) 6 BWU/BTD/21/010

7. Ex : int stack, push 10 p ush 20 p op push 55 push 50 pop ; What is the top & the top value ?   10 20 10 10 55 10 50 55 10 55 10 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 push 10             push 20 pop push 55 push 50 pop So, the top is 1 and the top value is 55. 7 BWU/BTD/21/010

8. CONDITIONS OF STACK There are two conditions in stack – Overflow Condition : When we can not insert any data as the stack is filled, the state is called overflow condition.   11 66 55 43 33 22 Underflow Condition : When we can not delete any data as the stack is empty, the state is called underflow condition.   5 4 3 2 1 5 4 3 2 1 push 10 pop Ex : Ex : 8 BWU/BTD/21/010

9. STACK IMPLEMENTATION USING ARRAY The array can be used to implement a stack of fixed size. Algorithm to insert (push) onto the stack : Algorithm : PUSH (STACK, ITEM) [STACK is an array of MAXSIZE and ITEM is an item to be pushed onto stack] [Check for stack overflow] If TOP = MAXSIZE - 1 then a) Print: Overflow b) Return 2. ELSE [Increase top by 1] Set TOP = TOP + 1 3. [Insert item in new top position] Set STACK[TOP] = ITEM 4. Return Algorithm to deletes (pop) the top element from the stack Algorithm : POP (STACK, ITEM) [STACK is an array and ITEM is an item to be popped from stack] [Check for stack underflow] If TOP = -1 then a) Print: Underflow b) Return ELSE[Assign top element to item] Set ITEM = STACK[TOP] [Decrease top by 1] Set TOP = TOP - 1 4. Return 9 BWU/BTD/21/010

10. STACK IMPLEMENTATION USING ARRAY The array can be used to implement a stack of fixed size. Algorithm of the push operation using linked list : Algorithm : PUSH (HEAD, ITEM) [HEAD is a pointer to the first node and ITEM is an item to be pushed onto stack] [Create the new node] Allocate memory for NEW node 2. If NEW = NULL then i ) Print: Out of memory ii) Return 3. Set NEW→DATA = ITEM 4. Set NEW→LINK = HEAD 5. Set HEAD = NEW 6. Return Algorithm of pop operation using linked list : Algorithm : POP (HEAD, ITEM) [HEAD is a pointer to the first node and ITEM is an item to be popped from stack] 1. [Whether List is empty] If HEAD = NULL then i ) Print: Stack is underflow ii) Return ITEM = HEAD→DATA Set P = HEAD HEAD = HEAD→LINK Set P→LINK = NULL De-allocate memory for node P Return 10 BWU/BTD/21/010

11. APPLICATIONS OF STACK The stack is a very useful data structure. Most of the modern computers and microprocessor provide an inbuilt hardware stack. Even there are stack-oriented computer architectures. Stacks are used - To implement recursive function call and processing of function calls such as passing arguments. Evaluation of Arithmetic expressions. To simulate recursion. To implement scope rule and block structure. To develop Compilers, System programs, Operating Systems and in many elegant application algorithms. To implement different algorithms, Depth first search, Quicksort, Mergesort etc. 11 BWU/BTD/21/010

12. REFERENCES Class notes A Text Book – Data Structure & Algorithm with C – By Debdutta Pal, Suman Halder 12 BWU/BTD/21/010

13. Thank you Have A Great Day ! 13 BWU/BTD/21/010 Ritu Sarkar [email protected]