Mercurial > Algorithms__Sedgewick
view algs4-c++/src/CircularQueue.hpp @ 20:86281e8f24ba
1.3.39 CircularQueue (ring buffer)
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Mon, 22 Jun 2015 15:38:25 -0500 |
| parents | |
| children |
line source
1 #ifndef CIRCULARQUEUE_HPP
3 #define CIRCULARQUEUE_HPP
5 #include <cassert>
6 #include <cstddef>
7 #include <vector>
9 template <typename T>
10 class CircularQueue {
11 public:
12 CircularQueue ( size_t max );
14 void enqueue( T &item);
15 T dequeue( void );
17 bool empty( void );
18 bool full( void );
19 size_t size( void );
21 private:
22 std::vector<T> data;
23 size_t first;
24 size_t end;
25 size_t N;
26 };
29 ////////////////////////////////////////////////////////////////////////////////
31 template <typename T>
32 CircularQueue<T>::CircularQueue( size_t max ) :
33 first (0),
34 end (0),
35 N (0)
36 {
37 data.resize( max );
38 }
40 template <typename T>
41 void CircularQueue<T>::enqueue( T &item ) {
42 data[end] = item;
43 if ( N < data.size() )
44 ++N;
45 else {
46 ++first;
47 if ( first > data.size() )
48 first = 0;
49 }
50 ++end;
51 if ( end == data.size() )
52 end = 0;
53 }
55 template <typename T>
56 T CircularQueue<T>::dequeue( void ) {
57 assert( N > 0 );
58 T item = data[first];
59 if ( N > 0 )
60 --N;
61 ++first;
62 if ( first == data.size() )
63 first = 0;
65 return item;
66 }
68 template <typename T>
69 bool CircularQueue<T>::empty( void ) {
70 return ( N == 0 );
71 }
73 template <typename T>
74 bool CircularQueue<T>::full( void ) {
75 return ( N == data.size() );
76 }
78 template <typename T>
79 size_t CircularQueue<T>::size( void ) {
80 return N;
81 }
85 #endif