deque
The word deque (pronounced either "deck" or "DQ") is a shortend form of double-ended queue
and denoted a list in which entries can be added or removed from either the first or the last
position of the list, but no changes can be made elsewhere in the list. Thus a deque is a
generalization of both a stack and a queue. The fundmantal operations on a deque are
appedn_front, append_rear, serve_front, serve_rear, retrieve_front, and retrieve_rear.
The word deque (pronounced either "deck" or "DQ") is a shortend form of double-ended queue
and denoted a list in which entries can be added or removed from either the first or the last
position of the list, but no changes can be made elsewhere in the list. Thus a deque is a
generalization of both a stack and a queue. The fundmantal operations on a deque are
appedn_front, append_rear, serve_front, serve_rear, retrieve_front, and retrieve_rear.
//implemented in circular array
#define maxque 15 // small number for test
enum Error_code {success, fail, underflow, overflow};
typedef int deque_entry;
class Deque {
public:
Deque(); // constructor
Error_code append_front (const deque_entry &item);
Error_code append_rear (const deque_entry &item);
Error_code serve_front ();
Error_code serve_rear ();
Error_code retrieve_front ( deque_entry &item);
Error_code retrieve_rear ( deque_entry &item);
int size() const;
bool is_empty() const;
protected:
deque_entry entry[maxque];
int front, rear;
int count;
};
Deque::Deque()
/* Post: The Deque is initialized to be empty.*/
{
count=0;
front=0;
rear = maxque-1;
}
int Deque::size() const
{
return count;
}
bool Deque::is_empty() const
{
if(count==0)
return true;
else return false;
}
Error_code Deque::append_front (const deque_entry &item)
{
if (count==maxque) return overflow;
front = (front==0) ? maxque-1:front-1;
entry[front]=item;
count++;
return success;
}
Error_code Deque::serve_front()
/* Post: The front of the Deque is removed. If the Deque
is empty return an Error_code of underflow. */
{
if (is_empty()) return underflow;
front = (front==maxque-1) ? 0: front+1;
count--;
return success;
}
Error_code Deque::append_rear (const deque_entry &item)
{
if (count==maxque) return overflow;
rear = (rear==maxque-1) ? 0 :rear+1;
count++;
return success;
}
Error_code Deque::serve_rear()
/* Post: The rear of the Deque is removed. If the Deque
is empty return an Error_code of underflow. */
{
if (is_empty()) return underflow;
rear = (rear==0) ? maxque-1:rear-1;
count--;
return success;
}
Error_code Deque::retrieve_rear ( deque_entry &item)
{
if (is_empty()) return underflow;
item=entry[rear];
rear=(rear==0) ? maxque-1: rear-1;
count--;
return success;
}
Error_code Deque::retrieve_front ( deque_entry &item)
{
if (is_empty()) return underflow;
item=entry[front];
rear=(front==maxque) ? 0: front+1;
count--;
return success;
}
#define maxque 15 // small number for testenum Error_code {success, fail, underflow, overflow};
typedef int deque_entry;class Deque {public: Deque(); // constructor Error_code append_front (const deque_entry &item); Error_code append_rear (const deque_entry &item); Error_code serve_front (); Error_code serve_rear (); Error_code retrieve_front ( deque_entry &item); Error_code retrieve_rear ( deque_entry &item); int size() const; bool is_empty() const;protected: deque_entry entry[maxque]; int front, rear; int count;};Deque::Deque()/* Post: The Deque is initialized to be empty.*/{ count=0; front=0; rear = maxque-1;}int Deque::size() const{ return count;}bool Deque::is_empty() const{ if(count==0) return true; else return false;}Error_code Deque::append_front (const deque_entry &item){ if (count==maxque) return overflow; front = (front==0) ? maxque-1:front-1; entry[front]=item; count++; return success;}Error_code Deque::serve_front()/* Post: The front of the Deque is removed. If the Deque is empty return an Error_code of underflow. */{ if (is_empty()) return underflow; front = (front==maxque-1) ? 0: front+1; count--; return success;}Error_code Deque::append_rear (const deque_entry &item){ if (count==maxque) return overflow; rear = (rear==maxque-1) ? 0 :rear+1; count++; return success;}Error_code Deque::serve_rear()/* Post: The rear of the Deque is removed. If the Deque is empty return an Error_code of underflow. */{ if (is_empty()) return underflow; rear = (rear==0) ? maxque-1:rear-1; count--; return success;}Error_code Deque::retrieve_rear ( deque_entry &item){ if (is_empty()) return underflow; item=entry[rear]; rear=(rear==0) ? maxque-1: rear-1; count--; return success;}Error_code Deque::retrieve_front ( deque_entry &item){ if (is_empty()) return underflow; item=entry[front]; rear=(front==maxque) ? 0: front+1; count--; return success;}