Deque

[largedimples]

Will someone please check this and tell me if I did this problem correctly. The question is presented bold; I also need help with push. I couldn't figure out how to complete the definition or routine for it. I am not very good at big o notation to determine if the routines I wrote are O(1). Thanks in advance!!

A deque is a data structure consisting of a list of items, on which the following operations are possible:
push(x,d): Insert item x on the front end of deque d.
dq.push_front(x, d);

pop(d): Remove the front item from deque d and return it.

void Pop(Deque& d) 
{
    n = new Node;
  
  n->data = val;
  
  if (d.size == 0) 
  {
    d.front = d.rear = n;
    n -> prev = n -> next = NULL;
  }
  else {
    n-> next = NULL;
    n->prev = d.rear;
    d.rear->next = n;
    d.rear = n;
  }
  d.size--;

}

inject(x,d): Insert item x on the rear end of deque d.

void Inject(int val, Deque& d)
{  
  n = new Node;
  
  n->data = val;
  
  if (d.size == 0) 
  {
    d.front = d.rear = n;
    n -> prev = n -> next = NULL;
   }
  else 
  {
    n-> next = NULL;
    n->prev = d.rear;
    d.rear->next = n;
    d.rear = n;
  }
  d.size++;

}

eject(d): Remove the rear item from deque d and return it.

void Eject(Deque& d)
{
  x->data = val;
  
  if (d.size == 0) 
  {
    d.front = d.rear = x;
    x -> prev = x -> next = NULL;
  }
  else 
  {
    x-> next = NULL;
    x->prev = d.rear;
    d.rear->next = x;
    d.rear = x;
  }
  d.size--;

}

Write definitions and routines to support the deque that take O(1) time per operation.

[Tom Gunn]

I also need help with push. I couldn't figure out how to complete the definition or routine for it.

It looks like you are using a two way linked list for the implementation. If that is the case, push is no harder than the other operations. Push() is the inverse of Inject() just as Pop() is the inverse of Eject(). You posted in the C forum, so I will give you example code in C:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int value;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct Deque
{
    size_t size;
    Node* front;
    Node* rear;
} Deque;

Deque* NewDeque()
{
    Deque* d = malloc(sizeof *d);

    if (d)
    {
        d->size = 0;
        d->front = d->rear = NULL;
    }

    return d;
}

void DeleteDeque(Deque* d)
{
    Node* p = d->front;
    Node* next;

    while (p)
    {
        next = p->next;
        free(p);
    }

    free(d);
}

int Push(Deque* d, int value)
{
    Node* new = malloc(sizeof *new);

    if (new)
    {
        new->value = value;
        new->prev = NULL;
        new->next = d->front;

        if (!d->front) d->rear = new;
        else d->front->prev = new;

        d->front = new;
        ++d->size;

        return 1;
    }
    else return 0;
}

int Inject(Deque* d, int value)
{
    Node* new = malloc(sizeof *new);

    if (new)
    {
        new->value = value;
        new->prev = d->rear;
        new->next = NULL;

        if (!d->rear) d->front = new;
        else d->rear->next = new;

        d->rear = new;
        ++d->size;

        return 1;
    }
    else return 0;
}

int Pop(Deque* d, int* value)
{
    if (d->front)
    {
        Node* saved = d->front;

        d->front = saved->next;

        if (!d->front) d->rear = NULL;

        *value = saved->value;
        --d->size;
        free(saved);

        return 1;
    }
    else return 0;
}

int Eject(Deque* d, int* value)
{
    if (d->rear)
    {
        Node* saved = d->rear;

        d->rear = saved->prev;

        if (!d->rear) d->front = NULL;

        *value = saved->value;
        --d->size;
        free(saved);

        return 1;
    }
    else return 0;
}

void TestIsEmpty(Deque* deque);
void TestAddRemove(Deque* deque, 
                   int (*add)(Deque*, int),
                   int (*remove)(Deque*, int*),
                   int values[],
                   int validateFromLeft,
                   size_t sz);

int main()
{
    Deque* deque = NewDeque();
    int valueList[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int value;

    TestIsEmpty(deque);

    assert(Pop(deque, &value) == 0);
    assert(Eject(deque, &value) == 0);

    /* test Push()/Pop() */
    TestAddRemove(deque, Push, Pop, valueList, 0, 10);
    TestIsEmpty(deque);

    /* test Inject()/Eject() */
    TestAddRemove(deque, Inject, Eject, valueList, 0, 10);
    TestIsEmpty(deque);

    /* test Push()/Eject() */
    TestAddRemove(deque, Push, Eject, valueList, 1, 10);
    TestIsEmpty(deque);

    /* test Inject()/Pop() */
    TestAddRemove(deque, Inject, Pop, valueList, 1, 10);
    TestIsEmpty(deque);

    puts("All tests passed.");
    DeleteDeque(deque);

    return 0;
}

void TestIsEmpty(Deque* deque)
{
    assert(deque != NULL);
    assert(deque->size == 0);
    assert(deque->front == NULL);
    assert(deque->rear == NULL);
}

void TestAddRemove(Deque* deque, 
                   int (*add)(Deque*, int),
                   int (*remove)(Deque*, int*),
                   int values[],
                   int validateFromLeft,
                   size_t sz)
{
    int value;
    size_t x;

    for (x = 0; x < sz; ++x)
    {
        assert(add(deque, values[x]) == 1);
        assert(deque->size == x + 1);
    }

    for (x = 0; x < sz; ++x)
    {
        int index = x;

        if (!validateFromLeft) index = 10 - x - 1;

        assert(remove(deque, &value) == 1);
        assert(deque->size == 10 - (x + 1));
        assert(value == values[index]);
    }
}

The important part is not the implementation of the deque, but the testing framework. Thorough testing is how you can check for yourself that you did the problem correctly. In fact, it is a good idea to write your test code first to solidify your understanding of the interface and how the implementation is supposed to work.

I am not very good at big o notation to determine if the routines I wrote are O(1).

If you do not use any loops that depend on the number of items or call any functions that with loops that depend on the number of items, the algorithm is very likely to be O(1).