#ifndef FIFO_H
#define FIFO_H
template <typename T>
class fifo
{
public:
fifo( int sz = 100);
fifo( const fifo &rhs);
~fifo();
fifo& operator=( const fifo &rhs);
int size() const { return len; }
bool is_empty() const { return 0 == len; }
bool is_full() const { return cap == len; }
void push( const T &t);
T pop();
T& operator[]( int i);
T operator[]( int i) const;
void print( std::ostream &os);
private:
void release();
void copy( const fifo &rhs);
void grow();
int cap;
int top;
int len;
T *v;
};
template <typename T>
fifo<T>::fifo( int sz)
{
cap = sz;
top = 0;
len = 0;
v = new T[cap];
}
template <typename T>
fifo<T>::~fifo()
{
release();
}
template <typename T>
fifo<T>::fifo( const fifo &rhs)
{
copy(rhs);
}
template <typename T>
fifo<T> &fifo<T>::operator=( const fifo &rhs)
{
if ( this != &rhs )
{
release();
copy(rhs);
}
return *this;
}
template <typename T>
void fifo<T>::release()
{
delete [] v;
}
template <typename T>
void fifo<T>::copy( const fifo &rhs)
{
cap = rhs.cap;
top = rhs.top;
len = rhs.len;
v = new T[cap];
for ( int i = 0; i < cap; ++i)
{
v[i] = rhs.v[i];
}
}
template <typename T>
void fifo<T>::grow()
{
int newcap = 2*cap;
T *newv = new T[newcap];
for ( int i = 0; i < len; ++i )
newv[i] = operator[](i); // (*this)[i]
top = len;
delete [] v;
v = newv;
cap = newcap;
}
template <typename T>
void fifo<T>::push( const T &t)
{
if ( is_full() )
{
grow();
}
v[top] = t;
top = top==cap-1 ? 0 : top+1;
++len;
}
template <typename T>
T fifo<T>::pop()
{
if ( ! is_empty() )
{
int bottom = top-len;
if ( bottom < 0 )
bottom += cap;
--len;
return v[bottom];
}
else
return T();
}
template <typename T>
void fifo<T>::print( std::ostream &os)
{
os << std::endl;
os << "top = " << top << std::endl;
os << "len = " << len << std::endl;
os << "[ ";
for ( int i = 0; i < cap; ++i)
os << v[i] << " ";
os << "]" << std::endl;
}
template <typename T>
T& fifo<T>::operator[]( int i)
{
int curr = (cap + top - len + i) % cap;
return v[curr];
}
template <typename T>
T fifo<T>::operator[]( int i) const
{
int curr = (cap + top - len + i) % cap;
return v[curr];
}
#endif /* FIFO_H */
------------------------------------------
#include <iostream>
#include "fifo.h"
using namespace std;
int main()
{
fifo<int> fd(5);
fd.push(1);
fd.push(2);
fd.push(3);
fd.push(4);
for ( int i = 0; i < 5; ++i)
cout << fd[i] << " ";
cout << endl;
fd.push(5);
fd.push(6);
fd.push(7);
for ( int i = 0; i < 8; ++i)
cout << fd[i] << " ";
cout << endl;
while ( ! fd.is_empty() )
cout << fd.pop() << " ";
cout << endl;
return 0;
}