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;

}
```
page revision: 2, last edited: 25 Oct 2011 07:09