Cơ sở dữ liệu - Chapter 3: Stack

Nội dung text: Cơ sở dữ liệu - Chapter 3: Stack

1. Chapter 3 - STACK Definition of Stack Specifications for Stack Implementations of Stack Linked Stack Contiguous Stack Applications of Stack 1
2. Linear List Concepts LIFO (Stack) 2
3. Stack ADT DEFINITION: A Stack of elements of type T is a finite sequence of elements of T, in which all insertions and deletions are restricted to one end, called the top. Stack is a Last In - First Out (LIFO) data structure. Basic operations: • Construct a stack, leaving it empty. • Push an element. • Pop an element. • Top an element. 3
4. Basic operation of Stack (Push) Before After push data top top a) Successful operation: function returns success top top (Stack remains push data unchanged) b) Unsuccessful operation: function returns overflow 4
5. Basic operation of Stack (Pop) Before After top pop data top a) Successful operation: function returns success (Stack remains pop data unchanged) b) Unsuccessful operation: function returns underflow 5
6. Basic operation of Stack (Top) Before After Received data: X top X top X top data Stack remains unchanged a) Successful operation: function returns success (Stack remains top data unchanged) b) Unsuccessful operation: function returns underflow 6
7. Stack ADT (cont.) Extended operations: • Determine whether the stack is empty or not. • Determine whether the stack is full or not. • Find the size of the stack. • Clear the stack to make it empty. • Determine the total number of elements that have ever been placed in the stack. • Determine the average number of elements processed through the stack in a given period. • 7
8. Specifications for Stack ADT Create() Push (val DataIn ) Pop () Top (ref DataOut ) isEmpty () isFull () Size () // the current number of elements in the stack. Variants of similar methods: ErrorCode Pop (ref DataOut ) 8
9. Built a Stack ADT Stack may be fully inhirited from a List ADT, inside its operations calling List’s operations. Ex.: Push (val DataIn ) // Call List::InsertHead(DataIn) or // Call List::Insert(DataIn, 0) // 0: insert to the 1st position end Push Pop () // Call List::RemoveHead() end Pop Other operations of Stack are similar 9
10. Built a List ADT from Stack ADT If the Stack ADT has been built first, List ADT may be inhirited from the Stack. Some of its operations call Stack’s operations; the others will be added. 10
11. Implementations of Stack Contiguous Implementation: use an array. (May be Automatically or Dynamically Allocated Array) Linked Implementation: linked stack. 11
12. Linked Stack Node Data count 4 top link top end Node Stack top count end Stack a) Conceptual b) Physical 12
13. Create Linked Stack Create () Creates an empty linked stack. Pre none Post An empty linked stack has been created. 1. top = NULL 2. count = 0 top ? top 3. return top = NULL count = ? count = 0 end Create count = 0 13
14. Push data into a Linked Stack 1. Allocate memory for the new node and set up data. count n top pNew X 2. Update pointers and count: pNew->link = top (1) • Point the new node to the top node. top = pNew (2) • Point top to the new node. count = count + 1 count n+1 top X pNew (2) (1) X 14
15. Push data into a Linked Stack (cont.) • Push is successful when allocation memory for the new node is successful. • There is no difference between push data into a stack having elements and push data into an empty stack (top having NULL value is assigned to pNew->link: that’s corresponding to a list having only one element). count 0 count 1 pNew->link = top top top = pNew top count = count + 1 pNew pNew 15
16. Push Algorithm (cont.) Push (val DataIn ) Pushes new data into the stack. Pre DataIn contains data to be pushed. Post If stack is not full, DataIn has been pushed in; otherwise, stack remains unchanged. Return success or overflow. 16
17. Push Algorithm (cont.) Push (val DataIn ) // For Linked Stack 1. Allocate pNew count 1 2. If (allocation was successful) top 1. pNew->data = DataIn pNew 2. pNew->link = top 3. top = pNew 4. count = count + 1 count n+1 5. return success 3. Else top X 1. return overflow pNew end Push 17
18. Pop Linked Stack 1. pDel holds the element on the top of the stack. top pDel count n top = pDel->link 2. top points to the next element. recycle pDel top X pDel count = count -1 count n-1 3. Recycle pDel. Decrease count by 1. 18
19. Pop Linked Stack (cont.) • Pop is successful when the stack is not empty. • There is no difference between pop an element from a stack having elements and pop the only- remained element in the stack (pDel->link having NULL value is assigned to top: that’s corresponding to an empty stack). 0 count 1 top = pDel->link count recycle pDel top top count = count -1 pDel pDel 19
20. Pop Algorithm Pop() Pops an element from the top of the stack Pre none Post If the stack is not empty, the element on the top has been removed; otherwise, the stack remains unchanged. Return success or underflow. 20
21. Pop Algorithm (cont.) Pop() Pops an element from the top of the stack 0 // For Linked Stack count 1. If (count > 0) top 1. pDel = top pDel 2. top = pDel->link 3. recycle pDel 4. count = count - 1 top 5. return success X pDel 2. else count n-1 1. return underflow 3. end Pop 21
22. Top Algorithm (cont.) Top (ref DataOut ) Retrieves data on the top of the stack without changing the stack. Pre none. Post if the stack is not empty, DataOut receives data on its top. The stack remains unchanged. Return success or underflow. // For Linked Stack 1. If (count > 0) 1. DataOut = top->data 2. Return success 2. Else 1. Return underflow 3. End Top 22
23. isEmpty Linked Stack isEmpty() Determines if the stack is empty. Pre none Post return stack status Return TRUE if the stack is empty, FALSE otherwise 1. if (count = 0) 1. Return TRUE 2. else 1. Return FALSE end isEmpty 23
24. isFull Linked Stack isFull() Determines if the stack is full. Pre none Post return stack status Return TRUE if the stack is full, FALSE otherwise // For Linked Stack 1. Allocate pNew // pNew is NULL if unsuccessful. 2. if (pNew is not NULL) 1. recycle pNew 2. return TRUE 3. else 1. return FALSE end isFull 24
25. Contiguous Implementation of push pop Stack (Automatically Allocated Array) Physical top n -1 push pop count n 0 1 2 3 n-2 n-1 max-2 max-1 top data x x x x x x Stack with pre-defined maxsize and has n elements. Stack top Conceptual count data > End Stack 25
26. Contiguous Implementation of Stack (cont.) top Stack is empty -1 top Push the 1st element 0 top Stack having n elements n-1 26
27. Create Stack Create() // Specifications here are similar to specifications for Linked Stack 1. count = 0 2. top = -1 end Create 27
28. Push Stack Push(val DataIn ) // Specifications here are similar to specifications for Linked Stack 1. if (count = maxsize) 1. return overflow 2. else 1. top = top + 1 2. data[top] = DataIn 3. count = count + 1 4. return success end Push 28
29. Pop Stack Pop() // Specifications here are similar to specifications for Linked Stack 1. if (stack is empty) 1. return underflow 2. else 1. top = top – 1 2. count = count - 1 3. return success end Pop 29
30. Top Stack Top(ref DataOut ) // Specifications here are similar to specifications for Linked Stack 1. if (count = 0) 1. return underflow 2. else 1. DataOut = data[top] 2. return success end Top 30
31. Stack status isEmpty() isFull() 1. if (count = 0) 1. if (count = maxsize) 1. return TRUE 1. return TRUE 2. Else 2. Else 1. return FALSE 1. return FALSE end isEmpty end isFull size() 1. return count end size 31