Stacks and queues using buffers

Prerequisites

Read about stacks using lists, queues using lists, and double-ended queue using buffer first.

Introduction

In this section, instead of using buffers directly to implement stacks and queues, we shall use a different technique, called delegation. The basic idea is that we use a more powerful data type to implement a less powerful one by using a subset of its operations. In our case, we shall use a double-ended queue implemented as a buffer to implement stacks and queues. In fact, we are not even going to refer to a particular implementation of a double-ended queue, but only use it as any other client. In the case of a buffer implementation of a queue, this is particularly good, since that implementation was harder to understand than the others.

Stack using a double-ended queue

The header file is the same as that for a stack using a list. Here is the implementation file:
  #include "stack.h"
  #include "dqueue.h"  

  struct stack
  {
    dqueue q;
  }

  stack
  stack_create(void)
  {
    stack s = malloc(sizeof(struct stack));
    s -> q = dq_create();
    return s;
  }

  int 
  stack_empty(stack s)
  {
    return dq_empty(s -> q);
  }
 
  void
  stack_push(stack s, void *element)
  {
    dq_enq_head(s -> q, element);
  }

  void
  stack_pop(stack s)
  {
    dq_deq_head(s -> q);
  }
 
  void *
  stack_top(stack s)
  {
    void *element = dq_deq_head(s -> q);
    dq_enq_head(s -> q, element);
    return element;
  }
As you can see, this is a particularly easy method of implementing a stack, given that we have a more powerful data structure such as the double-ended queue.

The implementation of a queue is even easier:

  #include "queue.h"
  #include "dqueue.h"

  struct queue
  {
    dqueue q;
  }

  queue
  queue_create(void)
  {
    queue q = malloc(sizeof(struct queue));
    q -> q = dqueue_create();
    return q;
  }

  int
  queue_empty(queue q)
  {
    return dq_empty(q -> q);
  }

  void
  queue_enq(queue q, void *element)
  {
    dq_enq_back(q -> q, element);
  }

  void *
  queue_deq(queue q)
  {
    return dq_deq_front(q -> q);
  }