Data Structures and Agorithm: DS 06 Stack.pptx

Data Structures and Agorithm: DS 06 Stack.pptx

1. Data Structure Lecture No. 6 Stack Engr . Rashid Farid Chishti http://youtube.com/rfchishti http://sites.google.com/site/chishti International Islamic University H-10, Islamabad, Pakistan Video Lecture

2. Stacks in real life: stack of books, stack of plates Add new items at the top Remove an item at the top Stack data structure similar to real life: collection of elements arranged in a linear order. Can only access element at the top Stack Operations Push(X) – insert X as the top element of the stack Pop() – remove the top element of the stack and return it. Top() – return the top element without removing it from the stack. Stacks

3. Stacks Operations push(2) top 2 push(5) 2 5 push(7) top 2 5 7 push(1) top 2 5 7 1 1 pop() top 2 5 7 push(21) top 2 5 7 21 21 pop() top 2 5 7 7 pop() 2 5 top 5 pop() 2 top top top

4. The last element to go into the stack is the first to come out: LIFO – Last In First Out. Implement push() to push data on stack and pop() to get data from stack. What happens if we call pop() and there is no element? Have bool IsEmpty () function that returns true if stack is empty , false otherwise. What happens if we stack is full and we call push() function. Have a bool IsFull () f unction, which returns true is stack (or array) is full, false otherwise. Stacks Operations

5. #include < iostream > using namespace std ; class Stack{ private : enum { MAX = 3 }; int arr [MAX]; int top; public : Stack() { top = - 1; } int Top () { return arr [top ]; } bool IsEmpty (){ return top == -1 ;} bool IsFull () { return top == MAX-1 ;} int Pop(){ if ( IsEmpty ()){ cout << "Error: Stack is Empty\n " ; return -1; } else 5 Example 1 : Stack Using Array return arr [top--]; } void Push( int x){ if ( IsFull () ) cout << "Error: Stack is Full\n " ; else { arr [++top] = x; } } }; int main( ){ Stack S; S.Push (11); S.Push (22); S.Push (33); S.Push (44 ); cout << S.Pop () << endl ; cout << S.Pop () << endl ; cout << S.Pop () << endl ; cout << S.Pop () << endl ; system ( "PAUSE " ); return ; } 1 2

6. We can avoid the size limitation of a stack implemented with an array by using a linked list to hold the stack elements. As with array, however, we need to decide where to insert elements in the list and where to delete them so that push() and pop() will run the fastest . For a singly-linked list, inserting data at start using head pointer takes constant time and inserting data at end using the current pointer also takes a constant time. Removing an element at the start is constant time but removal at the end required traversing the list to the node one before the last. So it make sense to place stack elements at the start of the list because insert and removal are constant time. Stack Using Linked List

7. Stack using an array. Stack using a Linked List. Stack Using Linked List top 2 5 7 1 1 7 5 2 head

8. int pop (){ current = head ; Data = current -> data ; head = head -> next ; delete current ; return Data ; } void Push ( int Data ) { node *newNode = new node ; newNode -> data = Data ; newNode -> next = head ; head = newNode ; } Stack Operations 1 7 5 2 head 9 5 2 head push(9) newNode 7 current Data = 1

9. #include < iostream > using namespace std ; typedef int Type ; struct Node{ Type data ; Node * next ; }; class Stack{ private : Node * head; public : Stack ( ); bool Is_Empty (); Type Top(); void Push ( Type Data ); Type Pop ( ); ~ Stack( ) ; }; 9 Example 2 : Stack Using Linked List Stack ::Stack( ){ head = NULL; } bool Stack:: Is_Empty () { return head == NULL; } Type Stack::Top() { if ( ! Is_Empty () ) return head->data; return -1; } void Stack :: Push ( Type Data ) { Node *newNode ; newNode = new Node ; if ( newNode == NULL ){ cout << endl << "Stack is full" ; return ; } 1 2

10. newNode -> data = Data ; newNode -> next = head ; head = newNode ; } Type Stack :: Pop( ) { if ( Is_Empty () ){ cout << "Stack is empty " ; return -1 ; } Node *current ; Type Data ; current = head ; Data = current -> data ; head = head -> next ; delete current ; return Data ; } 10 Example 2 : Stack Using Linked List Stack :: ~Stack( ){ Node *current ; while ( head != NULL ){ current = head ; head = head -> next ; delete current ; } } int main( ){ Stack s ; s.Push (11); s.Push (22); s.Push (33); cout << s.Pop () << endl ; cout << s.Pop () << endl ; cout << s.Pop () << endl ; cout << s.Pop () << endl ; system ( "PAUSE " ); return 0; } 3 4

11. Since both implementations support stack operations in constant time, any reason to choose one over the other? Allocating and deallocating memory for list nodes does take more time than pre-allocated array. Linked List uses only as much memory as required by the nodes; array requires allocation ahead of time. Linked List Pointers (head, next) require extra memory. Array has an upper limit; List is limited by dynamic memory allocation . Stack : Array or List Linked List

12. Infix expression into its postfix equivalent, or prefix equivalent so that We do not need to maintain operator ordering, and parenthesis. After converting into prefix or postfix notations, we have to evaluate the expression using stack to get the result. When we make a call from one function to the another function. The address of the calling function gets stored in the Stack. Stack can be used for parenthesis checking in our code. Stack can be used to reverse a string by pushing all letters on stack and then popping them out. We need stack in Backtracking algorithms so that we come back to the previous state and go into some other paths . Page-visited history in a Web browser Undo sequence in a text editor Applications of Stack