Hi

I have a homework assignment that ask you to complete an empty project that contains a queue and stack. the data should be stored in a circular array.
Functions of the queue are:
pushBack : to insert in the back
pushFront : to insert in the front
popBack : to remove from the back
popFront : to remove from the front
rotate(n) : to rotate the array. if numbers are 3, 2, 1, 0, 7, 8 and then you rotate(2) it will be 1, 0, 7, 8, 3, 2
reverse: to reverse the array. if numbers are 8, 3, 2, 1, 0, 7 and you reverse it will be 7, 0, 1, 2, 3, 8

I just couldn't come with an appropriate method to do it.

Should the implementation be based on front and rear and just change the value of front and rear. if yes, what is the right way to code it? the problem is that the program will have an empty cell between rear and front.

any help will be appreciated

>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';
}

Hi

thanks for this nice explanation with example.
>>That's not a problem if you use an item count to determine if the array is full or empty:
how can i display my queue if the array is like this
1 2 3 _ 8 7 0
where front is 3 and back is 8
also when i rotate front (-1) front will be in the empty area

to find more about my assignment Click here
it's the same project

Thanks

This article has been dead for over six months. Start a new discussion instead.