Question? Leave a message!




Abstract Deque

Abstract Deque
ECE 250 Algorithms and Data Structures Deques Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Queues 2 Outline This topic discusses the concept of a queue: – Description of an Abstract Deque – Applications – Implementations – The STL and IterationsQueues 3 3.4.1 Abstract Deque An Abstract Deque (Deque ADT) is an abstract data structure which emphasizes specific operations: – Uses a explicit linear ordering – Insertions and removals are performed individually – Allows insertions at both the front and back of the dequeQueues 4 3.4.1 Abstract Deque The operations will be called front back pushfront pushback popfront popback There are four errors associated with this abstract data type: – It is an undefined operation to access or pop from an empty dequeQueues 5 3.4.2 Applications Useful as a generalpurpose tool: – Can be used as either a queue or a stack Problem solving: – Consider solving a maze by adding or removing a constructed path at the front – Once the solution is found, iterate from the back for the solutionQueues 6 3.4.3 Implementations The implementations are clear: – We must use either a doubly linked list or a circular arrayQueues 7 3.4.4 Standard Template Library The C++ Standard Template Library (STL) has an implementation of the deque data structure – The STL stack and queue are wrappers around this structure The implementation is not specified, but the constraints are given which must be satisfied by any implementationQueues 8 3.4.4 Standard Template Library The STL comes with a deque data structure: dequeT The signatures use stack terminology: T front(); void pushfront(T const ); void popfront(); T back(); void pushback(T const ); void popback();Queues 9 3.4.4 Standard Template Library eceunix:1 g++ dequeexample.cpp eceunix:2 ./a.out include iostream Is the deque empty 0 include deque Size of deque: 4 using namespace std; Back of the deque: 6 int main() Back of the deque: 4 dequeint ideque; Back of the deque: 5 Back of the deque: 3 ideque.pushfront( 5 ); ideque.pushback( 4 ); Is the deque empty 1 ideque.pushfront( 3 ); eceunix:3 ideque.pushback( 6 ); // 3 5 4 6 cout "Is the deque empty " ideque.empty() endl; cout "Size of deque: " ideque.size() endl; for ( int i = 0; i 4; ++i ) cout "Back of the deque: " ideque.back() endl; ideque.popback(); cout "Is the deque empty " ideque.empty() endl; return 0; Queues 10 3.4.5 Accessing the Entries of a Deque We will see three mechanisms for accessing entries in the deque: – Two random access member functions • An overloaded indexing operator ideque10 • The at() member function; and ideque.at( 10 ); – The iterator design pattern The difference between indexing and using the function at( int ) is that the second will throw an outofrange exception if it accesses an entry outside the range of the dequeQueues 11 T deque::operator( int ) 3.4.5 T deque::at( int ) include iostream include deque using namespace std; int main() dequeint ideque; ideque.pushfront( 5 ); ideque.pushback( 4 ); ideque.pushfront( 3 ); ideque.pushback( 6 ); // 5 3 4 6 for ( int i = 0; i = ideque.size(); ++i ) cout idequei " " ideque.at( i ) " "; cout endl; return 0; eceunix:1 ./a.out output 5 5 3 3 4 4 6 6 0 terminate called after throwing an instance of 'std::outofrange' what(): deque::Mrangecheck AbortQueues 12 3.4.5 Stepping Through Deques From Project 1, you should be familiar with this technique of stepping through a Singlelist: Singlelistint list; for ( int i = 0; i 10; ++i ) list.pushfront( i ); for ( Singlenodeint ptr = list.head(); ptr = 0; ptr = ptrnext() ) cout ptrretrieve(); Queues 13 3.4.5 Stepping Through Deques There are serious problems with this approach: – It exposes the underlying structure – It is impossible to change the implementation once users have access to the structure – The implementation will change from class to class • Singlelist requires Singlenode • Doublelist requires Doublenode – An arraybased data structure does not have a direct analogy to the concept of either head() or next()Queues 14 3.4.5 Stepping Through Deques More critically, what happens with the following code Singlelistint list; for ( int i = 0; i 10; ++i ) list.pushfront( i ); Singlenodeint ptr = list.head(); list.popfront(); cout ptrretrieve() endl; // Queues 15 3.4.5 Stepping Through Deques Or how about… Singlelistint list; for ( int i = 0; i 10; ++i ) list.pushfront( i ); delete list.head(); // Queues 16 3.4.5 Iterators Project 1 exposes the underlying data structure for evaluation purposes – This is, however, not good programming practice The C++ STL uses the concept of an iterator to solve this problem – The iterator is not unique to C++ – It is an industry recognized approach to solving a particular problem – Such a solution is called a design pattern • Formalized in Gamma et al. work Design PatternsQueues 17 3.4.5 Standard Template Library Associated with each STL container class is an nested class termed an iterator: dequeint ideque; dequeint::iterator itr; The iterator “refers” to one position within the deque – It is similar a pointer but is independent of implementationQueues 18 3.4.5 Analogy Consider a filing system with an administrative assistant Your concern is not how reports are filed (so long as it’s efficient), it is only necessary that you can give directions to the assistant Of course, God help you if your assistant is sick...Queues 19 3.4.5 Analogy You can request that your assistant: – Starts with either the first or last file – You can request to see the file the assistant is currently holding – You can modify the file the assistant is currently holding – You can request that the assistant either: • Go to the next file, or • Go to the previous fileQueues 20 3.4.5 Iterators In C++, iterators overloads a number of operators: – The unary operator returns a reference to the element stored at the location pointed to by the iterator – The operator ++ updates the iterator to point to the next position – The operator updates the iterator to point to the previous location Note: these look like, but are not, pointers...Queues 21 3.4.5 Iterators We request an iterator on a specific instance of a deque by calling the member function begin(): dequeint ideque; ideque.pushfront( 5 ); ideque.pushback( 4 ); ideque.pushfront( 3 ); ideque.pushback( 6 ); // the deque is now 3 5 4 6 dequeint::iterator itr = ideque.begin();Queues 22 3.4.5 Iterators We access the element by calling itr: cout itr endl; // prints 3 Similarly, we can modify the element by assigning to itr: itr = 11; cout itr " == " ideque.front() endl; // prints 11 == 11Queues 23 3.4.5 Iterators We update the iterator to refer to the next element by calling ++itr: ++itr; cout itr endl; // prints 5Queues 24 3.4.5 Iterators The iterators returned by begin() and end() refer to: – The first position (head) in the deque, and – The position after the last element in the deque, respectively:Queues 25 3.4.5 Iterators The reverse iterators returned by rbegin() and rend() refer to: – the last position (tail) in the deque, and – the position before the first location in the deque, respectively:Queues 26 3.4.5 Iterators If a deque is empty then the beginning and ending iterators are equal: include iostream include deque using namespace std; int main() dequeint ideque; cout ( ideque.begin() == ideque.end() ) " " ( ideque.rbegin() == ideque.rend() ) endl; return 0; eceunix:1 ./a.out output 1 1 eceunix:2Queues 27 3.4.5 Iterators Because we can have multiple iterators referring to elements within the same deque, it makes sense that we can use the comparison operator == and =Queues 28 3.4.5 Iterators This code gives some suggestion as to why end() refers to the position after the last location in the deque: for ( int i = 0; i = ideque.size(); ++i ) cout idequei end; for ( dequeint::iterator itr = ideque.begin(); itr = ideque.end(); ++itr ) cout itr end; Queues 29 3.4.5 Iterators Note: modifying something beyond the last location of the deque results in undefined behaviour Do not use dequeint::iterator itr = ideque.end(); itr = 3; // wrong You should use the correct member functions: ideque.pushback( 3 ); // rightQueues 30 3.4.5 Iterators include iostream include deque using namespace std; int main() dequeint ideque; ideque.pushfront( 5 ); ideque.pushback( 4 ); ideque.pushfront( 3 ); ideque.pushback( 6 ); // 3 5 4 6 dequeint::iterator itr = ideque.begin(); cout itr endl; ++itr; cout itr endl; while ( itr = ideque.end() ) cout itr " "; ++itr; eceunix:1 ./a.out output 3 5 cout endl; 5 4 6 eceunix:2 return 0; Queues 31 3.4.5 Why Iterators Now that you understand what an iterator does, lets examine why this is standard softwareengineering solution; they – Do not expose the underlying structure, – Require Q(1) additional memory, – Provide a common interface which can be used regardless of whether or not it’s a vector, a deque, or any other data structure – Do not change, even if the underlying implementation doesQueues 32 Summary In this topic, we have introduced the more general deque abstract data structure – Allows insertions and deletions from both ends of the deque – Internally may be represented by either a doublylinked list or a two ended array More important, we looked at the STL and the design pattern of an iteratorQueues 33 References 1 Donald E. Knuth, The Art of Computer Programming, Volume 1: rd Fundamental Algorithms, 3 Ed., Addison Wesley, 1997, §2.2.1, p.238. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §3.3.1, p.75.Queues 34 References rd Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3 Ed., Addison Wesley, 1997, §2.2.1, p.238. Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, §11.1, p.200. rd Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §3.3.1, p.75. Koffman and Wolfgang, “Objects, Abstraction, Data Strucutes and Design using C++”, John Wiley Sons, Inc., Ch. 6. Wikipedia, http://en.wikipedia.org/wiki/Doubleendedqueue These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017