#include <stdio.h>
#include <stdlib.h>
#define class(a) typedef struct a a; struct a
#define make(a) (a *)malloc(sizeof(a))
// 内存
class(storage) {
int *data; // 数据
size_t size; // 大小
};
void storage_init(storage *s) {
s->size = 16;
s->data = malloc(sizeof(int) * s->size);
}
// 倍增
void storage_enlarge(storage *s) {
size_t size = ((s->size << 1) + s->size) >> 1;
int *data = realloc(s->data, sizeof(int) * size);
if (!data) {
fprintf(stderr, "realloc error\n");
exit(EXIT_FAILURE);
}
s->data = data;
s->size = size;
}
void storage_free(storage *s) {
free(s->data);
}
// 栈
class(stack) {
storage s;
size_t top;
};
void stack_init(stack *s) {
storage_init(&s->s);
s->top = 0;
}
int stack_empty(stack *s) {
return s->top == 0;
}
void stack_push(stack *s, int x) {
if (s->top == s->s.size) storage_enlarge(&s->s);
s->s.data[s->top++] = x;
}
int stack_pop(stack *s) {
if (stack_empty(s)) {
fprintf(stderr, "pop empty stack\n");
exit(EXIT_FAILURE);
}
return s->s.data[--s->top];
}
void stack_free(stack *s) {
storage_free(&s->s);
}
void stack_show(stack *s) {
printf("stack:");
for (size_t i = s->top; i > 0; i--)
printf(" %c", s->s.data[i - 1]);
printf("\n");
}
// 循环数组队列
class(queue) {
storage s;
size_t head, tail;
};
void queue_init(queue *q) {
storage_init(&q->s);
q->head = q->tail = 0;
}
int queue_empty(queue *q) {
return q->tail == q->head;
}
void queue_push(queue *q, int x) {
if ((q->tail + 1) % q->s.size == q->head) {
storage *s = &q->s;
size_t size = s->size;
s->size = ((size << 1) + size) >> 1;
int *data = malloc(sizeof(int) * s->size);
for (size_t i = q->head, j = 0; i != q->tail; i = (i + 1) % size)
data[j++] = s->data[i];
free(s->data);
s->data = data;
q->head = 0;
q->tail = size - 1;
}
q->s.data[q->tail] = x;
q->tail = (q->tail + 1) % q->s.size;
}
int queue_shift(queue *q) {
if (queue_empty(q)) {
fprintf(stderr, "pop empty queue\n");
exit(EXIT_FAILURE);
}
int data = q->s.data[q->head];
q->head = (q->head + 1) % q->s.size;
return data;
}
void queue_free(queue *q) {
storage_free(&q->s);
}
void queue_show(queue *q) {
printf("queue:");
for (size_t i = q->head; i != q->tail; i = (i + 1) % q->s.size) {
printf(" %c", q->s.data[i]);
}
printf("\n");
}
void test_all(char *p, stack *s, queue *q) {
static int n = 1;
printf("Case #%d\n", n++);
for (; *p; ++p) {
stack_push(s, *p);
queue_push(q, *p);
}
stack_show(s);
queue_show(q);
while (!stack_empty(s) && !queue_empty(q) && stack_pop(s) == queue_shift(q))
;
if (!stack_empty(s) || !queue_empty(q))
printf("not palindrome\n");
else
printf("palindrome\n");
while (!stack_empty(s)) stack_pop(s);
while (!queue_empty(q)) queue_shift(q);
printf("\n");
}
int main(void) {
stack s;
stack_init(&s);
queue q;
queue_init(&q);
test_all("", &s, &q);
test_all("a", &s, &q);
test_all("hello, world!", &s, &q);
test_all("12345678987654321", &s, &q);
queue_free(&q);
stack_free(&s);
return 0;
}
