Chapter 5 Stacks and Queues Data Structures and Algorithms Luong The Nhan, Tran Giang Son Faculty of Computer Science and Engineering University of Technology, VNU-HCM Stacks and Queues Luong The Nhan, Tran Giang Son a 3 Basic operations of Stacks Implementation of Stacks Linked implementation Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Outcomes L.1 - Depict the following concepts: (a) array list and linked list, including single link and double links, and multiple links; (b) stack; and (c) queue and circular queue.2 - Describe storage structures by using pseudocode for: (a) array list and linked list, including single link and double links, and multiple links; (b) stack; and (c) queue and circular queue.3 - List necessary methods supplied for list, stack, and queue, and describe them using pseudocode.4 - Implement list, stack, and queue using C/C++. Stacks and Queues Luong The Nhan, Tran Giang Son a 3 Basic operations of Stacks Implementation of Stacks Linked implementation Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Outcomes L.5 - Use list, stack, and queue for problems in real-life, and choose an appropriate implementation type (array vs.6 - Analyze the complexity and develop experiment (program) to evaluate the efficiency of methods supplied for list, stack, and queue.4 - Develop recursive implementations for methods supplied for the following structures: list, tree, heap, searching, and graphs.2 - Analyze algorithms and use Big-O notation to characterize the computational complexity of algorithms composed by using the following control structures: sequence, branching, and iteration (not recursion). Stacks and Queues Luong The Nhan, Tran Giang Son a 3 Basic operations of Stacks Implementation of Stacks Linked implementation Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Contents @ Basic operations of Stacks @ Implementation of Stacks Linked-list implementation Array implementation © Applications of Stack @ Basic operations of Queues © Implementation of Queue Linked-list implementation Array implementation @ Applications of Queue Stacks and Queues Luong The Nhan, Tran Giang Son a 3 Basic operations of Stacks Implementation of Stacks Linked implementation Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Stacks and Queues Luong The Nhan, Tran Giang Son BK TP. Basic operations of Ma Implementation of Stacks S t a C k Ss LIne St implementation an Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Linear List Concepts General list: « No restrictions on which operation can be used on the list.
e No restrictions on where data can be inserted /deleted. Restricted list: e Only some operations can be used on the list. e Data can be inserted/deleted only at the ends of the list. Stacks and Queues Luong The Nhan, Tran Giang Son Implementation of Stacks Linked-liet implementation Array impl Applications of Stack Basic operations of Queues Implementation of Queue Applications of Queue Stacks and Queues Linear list concepts Luong The Nhan, Tran Giang Son a <3 sent Implementation of Stacks Linked Am Restricted Applications of Stack Bae operations of | | FIFO LIFO me Unordered§ | Ordered (queue) (stack) Implementation o Applications of Queue Stack Stacks and Queue: Luong The Nhan, Definition Tran Giang Son 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.
sa mg Stack is a Last In - First Out (LIFO) data structure. Implementation of LIFO: The last item put on the stack is the first item that Stacks can be taken off. aa Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Stacks and Queues Basic operations of Stacks Luong The Nhan, Tran Giang Son Basic operations: sa e Construct a stack, leaving it empty. Sega e Push an element: put a new element ON tO nlementation of the top of the stack.
‘tnt s Pop an element: remove the top element Applications of from the top of the stack. Basic operation of s Top an element: retrieve the top element. LG Gg Applications of Queue Stacks and Queues Basic operations of Stacks Luong The Nhan, Tran Giang Son Extended operations: sa e Determine whether the stack is empty or Sega not. Stacks e Determine whether the stack is full or Unk igen aaa not.
Applications of Stack e Find the size of the stack. Basic operation of e Clear the stack to make it empty. raed Linked-liet implementation Array implementation Applications of Queue Basic operations of Stacks: Push Stacks and Queues Luong The Nhan, Tran Giang Son Push f ata ome | Top Implementation of Stacks | L___] m== Top E——> eee Stack Stack Stack Basic operations of Implementation of Hinh: Successful Push operation Queue Unc St implementation Array implementation Applications of Queue Basic operations of Stacks: Push Overflow Data Top Ld Ld [ Stack Hinh: Unsuccessful Push operation. Stack remains unchanged.
Stacks and Queues Luong The Nhan, Tran Giang Son a <3 sent Implementation of Stacks Linked implementation Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Basic operations of Stacks: Pop Top | = E— => LÍ Top E—] E—] Stack Stack Hinh: Successful Pop operation Stacks and Queues Luong The Nhan, Tran Giang Son a <3 sent Implementation of Stacks Linked implementation Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Stacks and Queues Basic operations of Stacks: Pop Luong The Nhan, Tran Giang Son Underflow đ > nto — Implementation of Stacks Linked-liet implementation Array implementation Applications of Stack Basic operations of Queues To P Stack Cụ NI of Array implementation Hinh: Unsuccessful Pop operation. Stack remains unchanged. cọ Applications of Queue Stacks and Queues Basic operations of Stacks: Top Luong The Nhan, Tran Giang Son Stack To mn ° „ mm c2 | Data — Implementation of Too | [| Top *%*“= Linked-liet implementation Applications of Basic operations of Queues Stack Stack Queue -. Hình: Successful Top operation.
Stack remains unchanged. Array it Applications of Queue Stacks and Queues Basic operations of Stacks: Top Luong The Nhan, Tran Giang Son Underflow đ > nto — Implementation of Stacks Linked-liet implementation Array implementation Applications of Stack Basic operations of Queues To P Stack Cụ NI of Array implementation Hinh: Unsuccessful Top operation. Stack remains unchanged. cọ Applications of Queue Implementation of Stacks Stacks and Queues Luong The Nhan, Tran Giang Son é Basic operations of Stacks Linked: lst implementation Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Stacks and Queues Linked-list implementation Luong The Nhan, Tran Giang Son Stack structure A ip 2% Stacks Implementation of Stacks “ Applications of Stack II Basic operations of Queues Implementation of Queue Conceptual Physical =5===—~ ray i Applications of Queue Linked-list implementation Stack structure count top Stack node structure data next stack count <integer> top <node pointer> end stack node data <dataType> next <node pointer> end node Stacks and Queues Luong The Nhan, Tran Giang Son a 3 Basic operations of Stacks Implementation of Stacks ‘Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Linked-list implementation in C++ template <class ItemType> struct Node { ItemType data; Node<ltemType> «next; }› template <class List ltemType> class Stack { public: Stack (); “Stack (); Stacks and Queues Luong The Nhan, Tran Giang Son a 3 Basic operations of Stacks Implementation of Stacks ‘Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Stacks and Queues Linked-list implementation in C++ Luong The Nhan, Tran Giang Son đà void Push(List ItemType dataln); BK int Pop(List_ItemType &dataOut); ¢3 int GetStackTop(List ItemType &dataOut),.
; void Clear(); geno int IsEmpty (); Implementation of int GetSize(); [ere ED Stack<List_ ItemType>+ Clone (); _ void Print2Console(); genes Basic operations of private: sent Node<List_ ItemType>x+ top; Queue int count; hove } + Applications of ' Queue Create an empty Linked Stack Before 2 |1? count top (no stack) After 0 count top (empty stack) Stacks and Queues Luong The Nhan, Tran Giang Son a 3 Basic operations of Stacks Implementation of Stacks ‘Array imple Applications of Stack Basic operations of Queues Implementation of Queue Applications of Queue Create an empty Linked Stack Stacks and Queue: Luong The Nhan, Tran Giang Son đà Algorithm createStack(ref stack «3 <metadata>) Initializes the metadata of a stack suc Pre: stack is a metadata structure of a stack —_smlementation of Post: metadata initialized — Applications of Stack stack.count = 0 Basic operation of stack.top = null Teer rier Queue return Linke Array is End createStack Applications of Queue Stacks and Queues Create an empty Linked Stack Luong The Nhan, Tran Giang Son BK template <class List ltemType> c¬ Stack<List_ ItemType >::Stack(){ Basic operations of this—>top = NULL; Stacks this—>count = 0; DU 20g } (Aktien Applications of template <class List_lItemType> Stack Stack<List_ItemType >::~ Stack (){ Ea this—>Clear(); Implementation of } Queue Applications of Queue Push data into a Linked Stack Stacks and Queue: Luong The Nhan, Tran Giang Son E18 data next data / next ¢3 eterno, Stacks count top data / next next count top data Implementation of Stacks £ z Applications of data next data _next Stack Basic operations of Queues @ Allocate memory for the new node and set up data. Impianrnfsttn ef @ Update pointers: sti e Point the new node to the top node (before adding the NuHuugặ: new node) Applications of. Queue e Point top to the new node. © Update count Push data into a Linked Stack Stacks and Queue: Luong The Nhan, Tran Giang Son Algorithm pushStack(ref stack <metadata>, f val data <dataType>) Inserts (pushes) one item into the stack Cae Pre: stack is a metadata structure to a valid Implementation of stack pe data contains value to be pushed into the Rd stack Basic operation of Post: data have been pushed in stack Implementation of Queue Return true if successful; false if memory a overflow Repertory Queue Push data into a Linked Stack Stacks and Queue: Luong The Nhan, Tran Giang Son if stack full then 6 | success = false ¢3 else allocate (pNew) Bastloperaboner i pNew -> data = data seen pNew -> next = stack.top = pNew peal stack.count + 1 Sea success = true ie renee end =o return success Applications of Queue End pushStack Push data into a Linked Stack Stacks and Queue: Luong The Nhan, Tran Giang Son BK template <class List_lItemType> 3 void Stack<List_ItemType >::Push Basic operations of (List ItemType value){ Stacks Node<List_ ItemType>x pNew = Decca new Node<List_ ltemType >(); as pNew—>data = value; Applications of pNew—>next = this—>top; Stack this—>top = pNew; Ea t h i b —>co unt +t; Implementation of + Queue Applications of Queue Push data into a Linked Stack e Push is successful when allocation memory for the new node is successful.
e 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->next: that's corresponding to a list having only one element). pNew—>next = top top = pNew count = count + 1 Stacks and Queues Luong The Nhan, Tran Giang Son a 3 Basic operations of Stacks Implementation of Stacks ‘Array implementation Applications of Stack Basic operations of Queues Implementation of Queue Linked implementation Array implementation Applications of Queue Pop Linked Stack Stacks and Queue: Luong The Nhan, Tran Giang Son Before After .