COMP1927 - Staques

Staques are more commonly referred to as deques. They esesentially combine a queue and a stack, allowing insertion from both ends.

Create Staque

Staque createStaque () {
 
   Staque s = malloc(sizeof(struct staque));
   assert (s != NULL);
 
   s->first = NULL;
   s->last = NULL;
 
   return s;
 
}

Delete Staque

void deleteStaque (Staque s) {
 
   if (s != NULL) {
      Node current = s->first;
      while (current != NULL) {
         s->first = current->next;
         deleteNode(s, current);
         current = s->first;
      }
      free(s);    
   }
 
}

Create Node

Node createNode (int data) {
 
   Node n = malloc(sizeof(struct node));
   assert (n != NULL);
 
   n->next = NULL;
   n->value = data;   
 
   return n;
 
}

Delete Node

void deleteNode (Staque s, Node n) {
 
   if (n != NULL) {
      Node current = s->first;
      // If there is only one node we delete it and return an empty staque
      if (current->next == NULL) {
         free(current);
         s->first = NULL;
         s->last = NULL;
      // Else we find the second last one in the list to relink the pointers
      } else {
         while (current->next->next != NULL) {
            current = current->next;
         }
         // This allows us to make the previous second last the new last and point it to null
         current->next = NULL;
         s->last = current;
         free(n);
      }
   }
 
}

Pop an Item (Off the Front)

int pop (Staque s) {
 
   int data = s->last->value;
 
   deleteNode(s, s->last);   
 
   return data;
 
}

Push an Item (Onto the Front)

void push (Staque s, int data) {
 
   if (s->first == NULL) {
      s->last = createNode(data);
      s->last->next = NULL;
      s->first = s->last;
   } else {
      s->last->next = createNode(data);
      s->last = s->last->next;
      s->last->next = NULL;
   }
 
}

Qush an Item (Onto the Back)

void qush (Staque s, int data) {
 
   if (s->first == NULL) {
      s->first = createNode(data);
      s->first->next = NULL;
      s->last = s->first;
   } else {
      Node current = s->first;
      s->first = createNode(data);
      s->first->next = current;
   }
 
}

Query Empty/Full Status

int isEmpty (Staque s) {
 
   int empty = FALSE;
 
   if (s->first == NULL) {
      empty = TRUE;
   }
 
   return empty;
 
}