Question? Leave a message!

Deque Data structure

deque data structure implementation and dequeue algorithm in data structure
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
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 © 2006-2013 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 push_front push_back pop_front pop_back 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 general-purpose 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 push_front(T const &); void pop_front(); T &back(); void push_back(T const &); void pop_back();Queues 9 3.4.4 Standard Template Library eceunix:1 g++ deque_example.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.push_front( 5 ); ideque.push_back( 4 ); Is the deque empty? 1 ideque.push_front( 3 ); eceunix:3 ideque.push_back( 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.pop_back(); 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 10 ); – The iterator design pattern The difference between indexing and using the function at( int ) is that the second will throw an out_of_range 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.push_front( 5 ); ideque.push_back( 4 ); ideque.push_front( 3 ); ideque.push_back( 6 ); // 5 3 4 6 for ( int i = 0; i = ideque.size(); ++i ) cout idequei " " 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::out_of_range' what(): deque::_M_range_check AbortQueues 12 3.4.5 Stepping Through Deques From Project 1, you should be familiar with this technique of stepping through a Single_list: Single_listint list; for ( int i = 0; i 10; ++i ) list.push_front( i ); for ( Single_nodeint ptr = list.head(); ptr = 0; ptr = ptr-next() ) cout ptr-retrieve(); 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 • Single_list requires Single_node • Double_list requires Double_node – An array-based 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? Single_listint list; for ( int i = 0; i 10; ++i ) list.push_front( i ); Single_nodeint ptr = list.head(); list.pop_front(); cout ptr-retrieve() endl; // ??Queues 15 3.4.5 Stepping Through Deques Or how about… Single_listint list; for ( int i = 0; i 10; ++i ) list.push_front( 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...