The presentation on stack data structure

These power point presentation explain the linear data structure stack

1. Unit II - Stack Data Structures BCS301

2. Stack What is a Stack? A stack is a data structure of ordered items such that items can be inserted and removed only at one end. A stack is a LIFO (Last-In/First-Out) data structure 2 What are some applications of stacks? Program execution Parsing Evaluating postfix expressions

3. Stack Representation & Basic Operations Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations − push()  − Pushing (storing) an element on the stack. pop()  − Removing (accessing) an element from the stack. To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks − peek()  − get the top data element of the stack, without removing it. isFull()  − check if stack is full. isEmpty()  − check if stack is empty.

4. 4 STACK push create pop isfull isempty

5. Stack- Abstract Data Types (ADTs) An abstract data type (ADT) is an abstraction of a data structure. It is a specification of a collection of data and the operations that can be performed on it. An ADT specifies: Data stored - A finite sequence of elements. Operations on the data Create Push : Insert element at top Top : Return top element Pop : Remove and return top element IsEmpty: test for emptyness Error conditions associated with operations 5

6. Stack implementation using Array In the array implementation, we would: Declare an array of fixed size (which determines the maximum size of the stack). Keep a variable which always points to the “top” of the stack. Contains the array index of the “top” element.

7. Implementing a Stack There are two ways we can implement a stack: Using an array Using a linked list 7

8. Push Operation The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps − Step 1  − Checks if the stack is full. Step 2  − If the stack is full, produces an error and exit. Step 3  − If the stack is not full, increments  top  to point next empty space. Step 4  − Adds data element to the stack location, where top is pointing. Step 5  − Returns success. Stack[1:n]; // Array of size n. top = 0; // initial value of top is 0. Push(data, top) { if (top = = n){ Print: “stack is full”; } top = top + 1; stack[top] = data }

9. Pop Operation Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead  top  is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space. A Pop operation may involve the following steps − Step 1  − Checks if the stack is empty. Step 2  − If the stack is empty, produces an error and exit. Step 3  − If the stack is not empty, accesses the data element at which  top  is pointing. Step 4  − Decreases the value of top by 1. Step 5  − Returns success. Stack[1:n]; // Array of size n. Pop(top) { if (top = = 0){ Print: “stack is Empty”; } data=stack[top]; top = top - 1; return data; }

10. Implementation by Linked Lists Can use a Linked List as implementation of stack 9/23/2020 CS 201 Top of Stack = Front of Linked-List StackLL lst a 1 a 2 a 3 a 4 head LinkedListItr

11. Push Operation: Struct node { int data; struct node * next; }; Struct node *top = NULL; // top is initially null Push(top, data) { struct node * temp = Getnode(); // allocate memory if (temp = = NULL){ Print: “Overflow”; } temp - > data = data; temp -> next = top; top = temp; }

12. Pop Operation: Struct node { int data; struct node * next; }; Struct node *top = NULL; // top is initially null Pop(top) { int item; if (top = = NULL){ Print: “Underflow”; } item = top -> data; top = top -> next; return item; }

13. Stack Summary Stack Operation Complexity for Different Implementations Vectors 14 Array Fixed-Size Array Expandable (doubling strategy) List Singly-Linked Pop() O(1) O(1) O(1) Push(o) O(1) O(n) Worst Case O(1) Best Case O(1) Average Case O(1) Top() O(1) O(1) O(1) Size(), isEmpty() O(1) O(1) O(1)