CS计算机代考程序代写 prolog data structure compiler c++ algorithm Container Types, Stacks, and Queues

Container Types, Stacks, and Queues
Overview
• Stacks
• Container types and references
References
• Bruno R. Preiss: Data Structures and Algorithms with Object-Oriented Design Patterns in C++. John Wiley & Sons, Inc. (1999)
• Richard F. Gilberg and Behrouz A. Forouzan: Data Structures – A Pseudocode Approach with C. 2nd Edition. Thomson (2005)
• Nicolai M. Josuttis: The C++ Standard Library – A Tutorial and Reference. Addison-Wesley (1999)
• Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo: C++ Primer. 4th Edition. Addison-Wesley (2006)
316
© Dr Markus Lumpe, 2021

Stacks
• A stack is a special version of a linear list where items are added and deleted at only one end called the top.
push
top
pop
20 top 20 top
pop
29
20
29
5
3
29
5
3
29
5
3
top
5
3
317
© Dr Markus Lumpe, 2021

Stack Frames (PASCAL)
arguments
static link
return address
temporaries save registers
arguments
static link
incoming arguments frame pointer
higher addresses
previous frame
current frame next frame
outgoing arguments stack pointer
318
© Dr Markus Lumpe, 2021

Stack Behavior
• Stacks manage elements in last-in, first-out (LIFO) manner.
• A stack underflow happens when one tries to pop on an empty stack.
• A stack overflow happens when one tries to push onto a full stack.
319
© Dr Markus Lumpe, 2021

Applications of Stacks
• Reversal of input
• Checking for matching parentheses (e.g., stack automata in compiler implementations)
• Backtracking (e.g., Prolog or graph analysis)
• State of program execution (e.g., storage for parameters and local variables of functions)
• Tree traversal
320
© Dr Markus Lumpe, 2021

Reverse Polish Notation
• Reverse Polish Notation (RPN) is a prefix notation wherein operands come before operators.
RPN: a b * c +
Infix: a * b + c 321
© Dr Markus Lumpe, 2021

RPN Calculation
3
5
15
29
Stack:
• x = 3 * 5 + 29
3 15 44
load 3 load 5
mul
load 29 add
store x
322
© Dr Markus Lumpe, 2021

Stack Interface
• When defining a container type we wish to minimize the number of value copies required for the objects stored in the container. In order to achieve this, we use references.
323
© Dr Markus Lumpe, 2021

Container Types
• Stacks belong to a special group of data types called container types.
• The de facto standard approach for the definition of container types in C++ is to use value-based semantics.
• Other examples of container types are Lists, Queues, Hash Tables, Maps, Arrays, or Trees.
324
© Dr Markus Lumpe, 2021

The Stack’s Private Interface
• Inside Stack we need to be able to store objects of type T. Hence we need to dynamically allocate memory (i.e, an array of type T) and store the address of the first element in a matching pointer variable.
325
© Dr Markus Lumpe, 2021

Stack Constructor
326
© Dr Markus Lumpe, 2021

Stack Destructor
• There are two forms of delete:
• delete ptr – release the memory associated with pointer ptr.
• delete [] ptr – release the memory associated with all elements of array ptr and the array ptr itself.
• Whenever you allocate memory for an array of elements of a generic type, say T* arr = new T[10], you must use the array form of delete, delete [], to guarantee that all array cells are released before the array itself is freed.
327
© Dr Markus Lumpe, 2021

Stack Auxiliaries
• isEmpty(): Boolean predicate to indicate whether there are elements on the stack.
• size(): returns the actual stack size. 328
© Dr Markus Lumpe, 2021

Push
• The push method stores a item at the next free slot
in the stack, if there is room. © Dr Markus Lumpe, 2021
329

Pop
• The pop method shifts the stack pointer to the previous slot in the stack, if there is such a slot. Note, the element in the current slot itself is not yet destroyed.
330
© Dr Markus Lumpe, 2021

Top
• The top method returns a const reference to the item in the current slot in the stack, if there is such a slot.
331
© Dr Markus Lumpe, 2021

Stack Sample
332
© Dr Markus Lumpe, 2021

Dynamic Stack
• We can define a dynamic stack that uses a list as underlying data type to host an arbitrary number of elements:
333
© Dr Markus Lumpe, 2021

Queues
• A queue is a special version of a linear list where access to items is only possible at its front and end.
enqueue
dequeue
20
5
29 3
334
© Dr Markus Lumpe, 2021

Queue Behavior
•Queues manage elements in first-in, first-out (FIFO) manner.
• A queue underflow happens when one tries to dequeue on an empty queue.
• A queue overflow happens when one tries to enqueue on a full queue.
335
© Dr Markus Lumpe, 2021

Implementation of Queues
• A concrete queue implementation requires us to split the dequeue operation into two steps: access to the first element (via top) and removal of first element (the actual dequeue).
• If we were to perform both steps as one (just dequeue), we would create a memory leak in C++ (i.e., we would create a reference to released memory). Hence, we need:
enqueue
29
top
3
20
5
336
© Dr Markus Lumpe, 2021
dequeue

Requirements for a Priority Queue
• The underlying data structure for a priority queue must be sorted (e.g., SortedList).
• Elements are queued using an integer to specify priority. We use a Pair to store elements with their associated priority.
• We need to provide a matching operator< on key values to sort elements in the priority queue. 341 © Dr Markus Lumpe, 2021 Priority Queue (5,29) enqueue (10,5) dequeue (1,14) (4,20) (5,30) (10,6) (10,5) (1,14) (4,20) (5,29) (5,30) (10,6) 342 © Dr Markus Lumpe, 2021 © Dr Markus Lumpe, 2021 The Pair Class 344 © Dr Markus Lumpe, 2021 SortedList uses an increasing order. A Priority Queue 345 © Dr Markus Lumpe, 2021 Priority Queue Semantics 346 © Dr Markus Lumpe, 2021 A PriorityQueue Test 347 © Dr Markus Lumpe, 2021

Related Posts