5. Stacks and Queues
|
| |
| 5.1 Stack |
| |
 A stack is a last in, first out (LIFO) abstract data type and data structure.
A stack is characterized by only three fundamental operations: push, pop and stack top. |
– The push operation adds a new item to the top of the stack, or initializes the stack if it is empty. If the stack is full and does not contain enough space to accept the given item, the stack is then considered to be in an overflow state.
– The pop operation removes an item from the top of the stack. If the stack is empty then it goes into underflow state.
– The stack top operation gets the data from the top-most position and returns it to the user without deleting it. The same underflow state can also occur in stack top operation if stack is empty. |
| A stack can be easily implemented either through an array or a linked list. |
| |
| Implementation: Array |
| |
| The array implementation aims to create an array where the first element (usually at the zero-offset) is the bottom. That is, array[0] is the first element pushed onto the stack and the last element popped off. |
| |
#include <stdio.h>
#include <stdlib.h>
#define STACKSIZE 10
typedef struct {
int size;
int items[STACKSIZE];
} STACK;
void push(STACK *ps, int x)
{
if (ps->size == STACKSIZE) {
fputs("Error: stack overflow\n", stderr);
exit(0);
}
else
ps->items[ps->size++] = x;
}
int pop(STACK *ps)
{
if (ps->size == 0){
fputs("Error: stack underflow\n", stderr);
exit(0);
}
else
return ps->items[--ps->size];
}
int main()
{
STACK list;
int i;
list.size = 0;
for (i=0; i<STACKSIZE; i++)
push(&list, i);
for (i=0; i<STACKSIZE; i++)
printf("%d\n", pop(&list));
return 0;
}
|
|
| |
| Implementation: Linked List |
| |
| The linked-list implementation is equally simple and straightforward. In fact, a simple singly linked list is sufficient to implement a stack. |
| |
#include <stdio.h>
typedef struct stack {
int data;
struct stack *next;
} STACK;
void push(STACK **head, int value)
{
/* create a new node */
STACK *node = malloc(sizeof(STACK));
if (node == NULL){
fputs("Error: no space available for node\n", stderr);
exit(0);
}
else { /* initialize node */
node->data = value;
node->next = !(*head) ? NULL : *head;
*head = node;
}
}
int pop(STACK **head)
{
if (!(*head)) { /* stack is empty */
fputs("Error: stack underflow\n", stderr);
exit(0);
} else { /* pop a node */
STACK *top = *head;
int value = top->data;
*head = top->next;
free(top);
return value;
}
}
int main()
{
STACK *head = NULL;
int i;
for (i=0; i<10; i++) push(&head, i);
for (i=0; i<10; i++) printf("%d\n", pop(&head));
return 0;
} |
|
| |
| 5.2 Queue |
| |
A queue is a first in, first out (FIFO) abstract data type and data structure.
A queue is characterized by two fundamental operations: enqueue and dequeue.
Queue overflow results from trying to add an element onto a full queue and queue underflow happens when trying to remove an element from an empty queue.
A queue can be easily implemented either through an array or a linked list. |
| |
| Implementation: Linked List |
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
struct queue_node
{
int data;
struct queue_node *next;
};
struct queue
{
struct queue_node *first;
struct queue_node *last;
};
int enqueue(struct queue *q, const int value)
{
struct queue_node *node =
(struct queue_node *)malloc(sizeof(struct queue_node));
if (node == NULL) {
errno = ENOMEM;
return 1;
}
node->data = value;
if (q->first == NULL)
q->first = q->last = node;
else {
q->last->next = node;
q->last = node;
}
node->next = NULL;
return 0;
}
int dequeue(struct queue *q, int *value)
{
struct queue_node *tmp;
if (!q->first) {
*value = 0;
return 1;
}
*value = q->first->data;
tmp = q->first;
if (q->first == q->last)
q->first = q->last = NULL;
else
q->first = q->first->next;
free(tmp);
return 0;
}
void init_queue(struct queue *q)
{
q->first = q->last = NULL;
}
int queue_empty(const struct queue *q)
{
return q->first == NULL;
}
int main(void)
{
int i, data;
struct queue list;
init_queue(&list);
for (i=0; i<10; i++)
enqueue(&list, i);
for (i=0; !queue_empty(&list); i++) {
dequeue(&list, &data);
printf("%d: %d\n", i, data);
}
return 0;
} |
|
| |
| |