>Should the implementation be based on front and
>rear and just change the value of front and rear.
Yes. When you add an item (stack as the example), add to the rear and increment it. If incrementing it would put it beyond the last element, reset it to 0. When you remove an item, decrement the rear. If decrementing it puts you into the negatives, reset it to the last element. Then return the rear value.
>the problem is that the program will have an empty cell between rear and front.
That's not a problem if you use an item count to determine if the array is full or empty:
#include <iostream>
#include <stdexcept>
template <typename T, int N>
class stack_type {
T _base[N];
int _front;
int _back;
int _size;
public:
stack_type()
: _front ( 0 ), _back ( 0 ), _size ( 0 )
{}
bool empty() const { return _size == 0; }
bool full() const { return _size == N; }
void push ( T data )
{
if ( full() )
throw std::runtime_error ( "Stack is full" );
_base[_back] = data;
if ( ++_back == N )
_back = 0;
++_size;
}
T pop()
{
if ( empty() )
throw std::runtime_error ( "Stack is empty" );
if ( --_back < 0 )
_back = N - 1;
--_size;
return _base[_back];
}
};
int main()
{
stack_type<int, 3> stack;
for ( int i = 5; !stack.full(); i-- )
stack.push ( i );
std::cout<< stack.pop() <<'\n';
std::cout<< stack.pop() <<'\n';
stack.push ( 2 );
stack.push ( 1 );
while ( !stack.empty() )
std::cout<< stack.pop() <<'\n';
}
Reputation Points: 6442
Solved Threads: 1391
Bad Cop
Offline 11,807 posts
since Sep 2004
Unsolved 
