You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
100 lines
1.5 KiB
100 lines
1.5 KiB
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
struct list {
|
|
int head;
|
|
struct list *tail;
|
|
};
|
|
|
|
typedef struct list list;
|
|
|
|
typedef struct {
|
|
list *front;
|
|
list *back;
|
|
} queue;
|
|
|
|
void list_free(list *lst) {
|
|
list *p;
|
|
|
|
while (lst != NULL) {
|
|
p = lst;
|
|
lst = lst->tail;
|
|
free(p);
|
|
}
|
|
}
|
|
|
|
list * cons(int val, list *lst) {
|
|
list *new = malloc(sizeof(list));
|
|
if (new == NULL) abort();
|
|
|
|
new->head = val;
|
|
new->tail = lst;
|
|
|
|
return new;
|
|
}
|
|
|
|
void list_print(list *lst) {
|
|
list *p = lst;
|
|
|
|
while (p != NULL) {
|
|
printf("%d ", p->head);
|
|
p = p->tail;
|
|
}
|
|
}
|
|
|
|
queue * make_queue() {
|
|
queue *new = malloc(sizeof(queue));
|
|
if (new == NULL) abort();
|
|
|
|
new->front = NULL;
|
|
new->back = NULL;
|
|
|
|
return new;
|
|
}
|
|
|
|
void push(int val, queue *q) {
|
|
if (q->front == NULL) { // empty queue
|
|
q->front = cons(val, NULL);
|
|
q->back = q->front;
|
|
}
|
|
|
|
else {
|
|
list *new = cons(val, NULL);
|
|
(q->back)->tail = new;
|
|
q->back = new;
|
|
}
|
|
}
|
|
|
|
int pop(queue *q) {
|
|
int val = (q->front)->head;
|
|
list *newhead = (q->front)->tail;
|
|
(q->front)->tail = NULL;
|
|
list_free(q->front);
|
|
q->front = newhead;
|
|
|
|
return val;
|
|
}
|
|
|
|
void queue_print(queue *q) {
|
|
printf("back ");
|
|
list_print(q->front);
|
|
printf("front\n");
|
|
}
|
|
|
|
void queue_free(queue *q) {
|
|
list_free(q->front);
|
|
free(q);
|
|
}
|
|
|
|
int main() {
|
|
queue *q = make_queue();
|
|
push(5, q);
|
|
push(3, q);
|
|
push(1, q);
|
|
queue_print(q);
|
|
printf("popped %d!\n", pop(q));
|
|
queue_print(q);
|
|
queue_free(q);
|
|
|
|
return 0;
|
|
}
|
|
|