TMF1434 LEC06_Stack (1).pdf

TMF1434 DATA STRUCTURE AND ALGORITHMS Semester 2, 2023/2024 Instructor: Azman Bujang Masli [email protected] +6082-583652 2 LEC06 Stack 3 Acknowledgement  The following slides were drawn or copied from your textbook “Data Structures Using C++” by D. S. Malik...

TMF1434 DATA STRUCTURE AND ALGORITHMS Semester 2, 2023/2024 Instructor: Azman Bujang Masli [email protected] +6082-583652 2 LEC06 Stack 3 Acknowledgement  The following slides were drawn or copied from your textbook “Data Structures Using C++” by D. S. Malik 4 Learning Objectives Learn about stacks Examine various stack operations Learn how to implement a stack as an array Learn how to implement a stack as a linked list Discover stack applications Learn how to use a stack to remove recursion 5 Real Life Examples of Stacks World History  How would you remove the book World History?  You need to remove the first book, i.e., Applied Math, before being able to remove it. 6 Stack Concept A stack is a data structure Like arrays and linked lists Stacks, arrays, and linked lists hold a sequence of elements Stacks are last-in, first-out (LIFO) structures Arrays and lists are not LIFO structures Addition and deletion of elements occur only at one end, called the top 7 Some Examples of Stack Applications in Computer Science  Evaluating balanced symbols Compilers check a program for syntax errors.  A missing symbol from a pair of symbols (e.g., missing the right bracket { }, ( ), [ ]) will cause error in compilation.  Undo operation in text editors  Undo operation is accomplished by keeping all text changes in a stack.  Parsing arithmetic expressions  ((2*4-6/3)*(3*5+8/4))-(2+3) 8 Stack Abstract Data Type (ADT)  The class stackADT defines the stack operations as an ADT  UML class diagram of the class stackADT 9 Stack Operations push operation  Add a new element onto the stack  PRECONDITION: the stack must exist and must not be full top operation  Retrieve the top element of the stack (without removing it from the stack)  PRECONDITION: the stack must exist and must not be empty pop operation  Remove the top element from the stack  PRECONDITION: the stack must exist and must not be empty 10 Stack Operations (cont’d)  isFullStack operation  If the stack is full, return the value true  Otherwise, return the value false  isEmptyStack operation  If the stack is empty, return the value true  Otherwise, return the value false  initializeStack operation  Initialises stack to an empty state 11 Implementing Stack ADT  Functions such as push and pop are not available in C++  You must write these functions to implement the stack operations  Because all the elements of a stack are of the same type, a stack can be implemented as either an array or a linked list structure  Stacks implemented as arrays are static stacks: they have a fixed size  Stacks implemented as linked lists are dynamic stacks: they grow in size as needed 12 Implementing Stack using Array 13 Implementation of Stacks using Arrays  First stack element  Put in first array slot  Second stack element  Put in second array slot, and so on  Top of stack  Index of last element added to stack  Stack element accessed only through the top  PROBLEM: array is a random access data structure  SOLUTION: use another variable (stackTop)  Keeps track of the top position of the array 14 Basic Operations on Stack using Array  The class stackType implements the functions of the abstract class stackADT  UML class diagram of the class stackType 15 Example of a Stack  stack  An object of type stackType  list  A pointer to the array that holds the stack elements  maxStackSize  Variable to store the maximum stack size  stackTop  Variable to point to the top of the stack  Can range from 0 to maxStackSize  If stackTop is nonzero, then stackTop – 1 is the index of the top element 16 Initialise Stack Because the value of stackTop indicates whether the stack is empty, we can simply set stackTop to 0 to initialise the stack. Definition of the function initializeStack 17 Empty Stack Since the value of stackTop indicates the status of the stack If stackTop is 0, the stack is empty Otherwise, the stack is not empty Definition of the function isEmptyStack 18 Full Stack  Stack full If stackTop is equal to maxStackSize  Definition of function isFullStack 19 Push Pushing an element onto the stack is a two-step process 1. Store newItem in the array component indicated by stackTop 2. Increment stackTop  Value of stackTop indicates the number of elements in the stack  Value of stackTop-1 gives the position of the top element of the stack 20 Push (cont’d) 21 Push (cont’d)  Definition of the function push 22 Push (cont’d) Overflow If the stack is full and you try to push another element, you’ll get the message “Cannot add to a full stack.” You can also check for an overflow before calling the function push 23 Pop To pop an element from the stack, we simply decrement stackTop by 1 24 Pop (cont’d)  The definition of the function pop 25 Pop (cont’d)  Underflow  If the stack is empty and you try to pop an element from it, you’ll get the message “Cannot remove from an empty stack.”  You can also check for an underflow before calling the function pop 26 Return the Top Element  The definition of the function top 27 Other Functions Review code in your Textbook CopyStack Constructor Destructor Copy constructor Overloading the assignment operator (=) 28 Stack Operations Analysis Time complexity of the operations of the class stackType on a stack with n elements  Implementing a Stack using Linked List 29 As a singly linked list 30 Why Linked List is better for Stack Representation? Problem with an array as a stack representation An array size is fixed, i.e., only a fixed number of elements can be pushed onto the stack If you exceed the number, the program might terminate in an error SOLUTION By using pointer variables we can dynamically allocate and deallocate memory By using linked lists we can dynamically organize data 31 Design Decision Which linked list?  As we do not need to move back and forth within the list, there is no requirement for doubly or circular linked list Singly linked list can serve the purpose. 32 Differences with the Value of stackTop In array representation of In a linked list a stack representation of a stack  stackTop  stackTop Indicates number of Locates top element in elements in the stack the stack Gives the index of the array Gives the address (memory location) of the top element of the stack  stackTop – 1 Points to top item in the stack 33 Design Decision Where will we push the element inside the list and from where will we pop the element?  For a singly-linked list  Insert at head or end takes constant time using the head and current pointers respectively Push at the head or end of the list is equally efficient  Removing an element at the head is constant time  Removing at the end requires traversing the list to the node one before the last one Pop from the head is better approach rather than from the end 34 Linked List Implementation of Stacks  Suppose that stack is an object of type linkedStackType In (b) the top element of the stack is C i.e., the last element pushed onto the stack is C 35 Default Constructor  The default constructor initialises the stack to an empty state when a stack object is declared  Thus, this function sets stackTop to NULL 36 Empty Stack and Full Stack  Stack empty if stackTop is NULL  Stack never full Element memory allocated/deallocated dynamically Function isFullStack always returns false value //Stack ADT 37 Initialise Stack Re-initialises stack to an empty state Because stack might contain elements and you are using a linked implementation of a stack Must deallocate memory occupied by the stack elements, set stackTop to NULL 38 Initialise Stack (cont’d) Definition of the initializeStack function 39 Push newElement added at the beginning of the linked list pointed to by stackTop Value of pointer stackTop updated 40 Push (cont’d) Stack before push operation 41 Push (cont’d)  The definition of the function push  No need to check whether the stack is full before pushing an element onto the stack  Because in this implementation, logically, the stack is never full 42 Return the Top Element  Returns information of the node to which stackTop is pointing  Definition of the function top 43 Pop Removes top element of the stack Node pointed to by stackTop removed Value of pointer stackTop updated 44 Pop (cont’d) Stack before the pop operation 45 Pop (cont’d) Definition of the function pop 46 Other Functions Review code in your Textbook Copy stack Constructor Destructor Overloading assignment operator (=) 47 Stack Operations Analysis Time complexity of the operations of the class linkedStackType on a stack with n elements 48 Removing Recursion A non-recursive algorithm to print a linked list backward 49 Non-recursive Algorithm to Print a Linked List Backward  Stack  Used to design non-recursive algorithm  Print a linked list backward  Use linked list implementation of stack A linked list 50 List after the statement current = first; executes List and stack after the statements stack.push(current); and current = current->link; execute  List and stack after the while statement executes 51 List and stack after the statements current = stack.top(); and stack.pop(); execute  Standard Template Library class 52 stack 53 STL class stack  STL provides a class to implement a stack in a program  It is similar to the implementation described in the Textbook  stack  The name of the class  stack  The name of the header file containing the class stack 54 Quick Review 1. What does LIFO mean? 2. What element is retrieved from a stack by the pop operation? 3. Describe two operations that all stacks perform. 55 Any Question?