#include <stdio.h>
#include <stdlib.h>
#define class(a) typedef struct a a; struct a
#define make(a) (a *)malloc(sizeof(a))
// 双向链表
class(node) {
int data; // 数据
node *prev, *next; // 前后节点
};
// 栈
class(stack) {
node *top; // 栈顶
};
stack *stack_init(stack *s) {
s->top = NULL;
return s;
}
stack *stack_push(stack *s, int data) {
node *n = make(node);
*n = (node) { data, s->top, NULL };
s->top = n;
return s;
}
int stack_pop(stack *s) {
node *n = s->top;
int d = n->data;
s->top = n->prev;
free(n);
return d;
}
void stack_show(stack *s) {
for (node *p = s->top; p; p = p->prev) {
printf("%c ", p->data);
}
printf("\n");
}
// 队列
class(queue) {
node *head, *tail; // 队列头尾
};
queue *queue_init(queue *s) {
s->head = s->tail = NULL;
return s;
}
queue *queue_push(queue *s, int data) {
node *n = make(node);
*n = (node) { data, s->tail, NULL };
if (s->tail) s->tail->next = n;
s->tail = n;
if (!s->head) s->head = s->tail;
return s;
}
int queue_shift(queue *s) {
node *n = s->head;
int d = n->data;
if ((s->head = n->next)) s->head->prev = NULL;
free(n);
if (!s->head) s->tail = NULL;
return d;
}
void queue_show(queue *s) {
for (node *p = s->head; p; p = p->next) {
printf("%c ", p->data);
}
printf("\n");
}
// 测试
void test_all(char *string, stack *s, queue *q) {
static int n_case = 1;
printf("Case #%d:\n", n_case++);
for (char *p = string; *p; ++p) {
s = stack_push(s, *p);
q = queue_push(q, *p);
}
printf("stack: ");
stack_show(s);
printf("queue: ");
queue_show(q);
while (s->top && q->head && stack_pop(s) == queue_shift(q))
;
if (s->top || q->head)
printf("not palindrome\n");
else
printf("palindrome\n");
while (s->top) stack_pop(s);
while (q->head) queue_shift(q);
printf("\n");
}
int main(void) {
stack s;
queue q;
stack_init(&s);
queue_init(&q);
test_all("", &s, &q);
test_all("a", &s, &q);
test_all("hello, world", &s, &q);
test_all("12345678987654321", &s, &q);
return 0;
}
