CLRS 10.1.5 Implement Dequeue

http://clrs.skanev.com/10/01/05.html
Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double-ended queue) allows insertion and deletion at both ends. Write four O(1)-time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.

typedef struct {
    int items[MAX_SIZE];
    int head;
    int tail;
} deque_t;

void init_deque(deque_t *deque) {
    deque->head = -1;
    deque->tail = 0;
}

int is_empty(deque_t *deque) {
    return (deque->head == -1);
}

void push(deque_t *deque, int n) {
    if (deque->head == deque->tail) {
        fprintf(stderr, "Deque overflow\n");
        exit(1);
    }

    deque->items[deque->tail] = n;

    if (deque->head == -1) {
        deque->head = deque->tail;
    }

    deque->tail = (deque->tail + 1) % MAX_SIZE;
}

void unshift(deque_t *deque, int n) {
    if (deque->head == deque->tail) {
        fprintf(stderr, "Deque overflow\n");
        exit(1);
    }

    if (deque->head == -1) {
        deque->head = deque->tail;
    }

    deque->head = (deque->head - 1 + MAX_SIZE) % MAX_SIZE;
    deque->items[deque->head] = n;
}

int pop(deque_t *deque) {
    if (deque->head == -1) {
        fprintf(stderr, "Deque underflow\n");
        exit(1);
    }

    deque->tail = (deque->tail + MAX_SIZE - 1) % MAX_SIZE;

    if (deque->tail == deque->head) {
        deque->head = -1;
    }

    return deque->items[deque->tail];
}

int shift(deque_t *deque) {
    if (deque->head == -1) {
        fprintf(stderr, "Deque underflow\n");
        exit(1);
    }

    int result = deque->items[deque->head];

    deque->head = (deque->head + 1) % MAX_SIZE;

    if (deque->head == deque->tail) {
        deque->head = -1;
    }

    return result;
}

https://code.google.com/p/clrs/source/browse/ch10/10.1-5.py

class my_deque():

def __init__(self):

self.data=[None]*5

self.head=0

self.tail=0 #超出末端

self.is_empty=True

self.is_full=False

def append_right(self,x):

if self.is_full:

raise Exception('Deque Overflow')

self.data[self.tail]=x

if self.tail==len(self.data)-1:

self.tail=0

else:

self.tail+=1

self.is_empty=False

if self.tail==self.head:

self.is_full=True

def append_left(self,x):

if self.is_full:

raise Exception('Deque Overflow')

if self.head==0:

self.head=len(self.data)-1

else:

self.head-=1

self.data[self.head]=x

self.is_empty=False

if self.tail==self.head:

self.is_full=True

def pop_left(self):

if self.is_empty:

raise Exception('Deque Unerflow')

x=self.data[self.head]

if self.head==len(self.data)-1:

self.head=0

else:

self.head+=1

self.is_full=False

if self.head==self.tail:

self.is_empty=True

return x

def pop_right(self):

if self.is_empty:

raise Exception('Deque Underflow')

if self.tail==0:

self.tail=len(self.data)-1

else:

self.tail-=1

x=self.data[self.tail]

self.is_full=False

if self.head==self.tail:

self.is_empty=True

return x

http://www.cnblogs.com/shuaiwhu/archive/2011/04/16/2065059.html

template <class T>
class Deque
{public:  void push_front(T t);  void push_back(T t);
  T pop_front();
  T pop_back();
  Deque(int m);  ~Deque();

 

private:
  T* arr;  int max;  int count;  int head;  int tail;
};
int main()
{
  Deque<int> d(3);
  d.push_front(0);
  d.push_back(2);
  d.push_front(4);

  cout<<d.pop_front()<<endl;
  d.push_back(3);
  cout<<d.pop_back()<<endl;  return0;
}

template <class T>
void Deque<T>::push_front(T t)
{  if(count == max)
  {
    cout<<"deque is full"<<endl;    return;
  }  //保证新插入的元素总在前面
  head = (head ==0) ? max -1 : head -1;
  arr[head] = t;
  count++;
}

template <class T>
void Deque<T>::push_back(T t)
{  if(count == max)
  {
    cout<<"deque is full"<<endl;    return;
  }  //保证新插入的元素总在后面
  tail = (tail == max -1) ?0 : tail +1;
  arr[tail] = t;
  count++;
}

template <class T>
T Deque<T>::pop_front()
{  if(count ==0)
  {
    cout<<"deque is empty"<<endl;    return NULL;
  }  int temp = head;
  head = (head == max -1) ?0 : head +1;
  count--;  return arr[temp];
}

template <class T>
T Deque<T>::pop_back()
{  if(count ==0)
  {
    cout<<"deque is empty"<<endl;    return NULL;
  }  int temp = tail;
  tail = (tail ==0) ? max -1 : tail -1;
  count--;  return arr[temp];
}

template <class T>
Deque<T>::Deque(int m)
{
  max = m;
  count =0;
  head =0;
  tail = m -1;
  arr =new T[m];
}

template <class T>
Deque<T>::~Deque()
{
  delete[] arr;
}

https://sites.google.com/site/clrssolutions/home/chapter10