stack是一种先进后出的数据结构。
stack主要操作为，入栈，出栈，判断栈空满等。
1. 数组实现栈
#include#include #include #define MAX 10int arr[MAX];int pos = 0;void push(int value){ arr[pos ++] = value;}int pop(void){ return arr[-- pos];}bool is_empty(void){ return pos == 0;}bool is_full(void){ return pos == MAX;}int main(int argc, char *argv[]){ char ch; while((ch = getchar()) != '\n') { if (! is_full()) { push(ch); } } while(! is_empty()) { putchar(pop()); } return 0;}
2. 数组栈
#ifndef _STACK_H_#define _STACK_H_#include#define MAX 10typedef struct stack { int arr[MAX]; int pos;} Stack;extern void stack_init(Stack *stack);extern void stack_push(Stack *stack, int value);extern int stack_pop(Stack *stack);extern bool stack_is_empty(Stack *stack);extern bool stack_is_full(Stack *stack);#endif //_STACK_H_#include "stack.h"void stack_init(Stack *stack){ stack->pos = 0;}void stack_push(Stack *stack, int value){ stack->arr[stack->pos ++] = value;}int stack_pop(Stack *stack){ return stack->arr[-- stack->pos];}bool stack_is_empty(Stack *stack){ return stack->pos == 0;}bool stack_is_full(Stack *stack){ return stack->pos == MAX;}#include #include #include #include "stack.h"bool is_digit(char ch){ if (ch >= '0' && ch <= '9') { return true; } return false;}int main(int argc, char *argv[]){ char ch; Stack s1, s2; stack_init(&s1); stack_init(&s2); while((ch = getchar()) != '\n') { if (is_digit(ch)) { if (! stack_is_full(&s1)) { stack_push(&s1, ch); } } else { if (! stack_is_full(&s2)) { stack_push(&s2, ch); } } } while(! stack_is_empty(&s1)) { putchar(stack_pop(&s1)); } putchar('\n'); while(! stack_is_empty(&s2)) { putchar(stack_pop(&s2)); } return 0;}
3. 链表栈
#ifndef _STACK_H_#define _STACK_H_#includestruct node { void *data; struct node *next;};typedef struct { struct node *top;} Stack;extern void stack_init(Stack *stack);extern void stack_push(Stack *stack, void *data);extern void *stack_pop(Stack *stack);extern bool stack_is_empty(Stack *stack);extern bool stack_is_full(Stack *stack);extern void stack_destroy(Stack *stack, void (*destroy)(void *data));#endif //_STACK_H_#include #include #include "stack.h"void stack_init(Stack *stack){ stack->top = NULL;}static struct node * make_node(void *data){ struct node *n; n = malloc(sizeof(struct node)); assert(n); n->data = data; n->next = NULL; return n;}void stack_push(Stack *stack, void *data){ struct node *n; n = make_node(data); /* if (stack->top == NULL) { stack->top = n; } else { n->next = stack->top; stack->top = n; }*/ n->next = stack->top; stack->top = n;}void *stack_pop(Stack *stack){ void *data; struct node *n; n = stack->top; stack->top = n->next; data = n->data; free(n); return data;}bool stack_is_empty(Stack *stack){ return stack->top == NULL;}bool stack_is_full(Stack *stack){ return false;}void stack_destroy(Stack *stack, void (*destroy)(void *data)){ while(! stack_is_empty(stack)) { if (destroy) { destroy(stack_pop(stack)); } else { stack_pop(stack); } } }#include #include #include #include "stack.h"void destroy_data(void *data){ char *p = data; free(p);}int main(int argc, char *argv[]){ char ch; char *p; Stack s; stack_init(&s); while((ch = getchar()) != '\n') { p = malloc(sizeof(char)); assert(p); *p = ch; if (! stack_is_full(&s)) { stack_push(&s, p); } } while(! stack_is_empty(&s)) { p = stack_pop(&s); putchar(*p); free(p); } stack_destroy(&s, destroy_data); return 0;}