數據結構：堆疊的實現（c語言）含判斷以in[]順序進棧，能否以out[]順序出棧；

數據結構：堆疊的實現（c語言）

stack.h

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

typedef int T;
typedef struct Stack{
	T *base;          //記憶體
	size_t cap;       //容量
	size_t size;      //元素個數
}Stack;

int stack_init(Stack *s,size_t cap);//初始化一個棧
void stack_destroy(Stack *s);銷燬棧
bool stack_is_empty(Stack *s);//棧是否爲空
bool stack_is_full(Stack *s);//棧是否爲滿
void stack_push(Stack *s,T data);//壓入一個元素
void stack_clear(Stack *s);//清空棧
T stack_pop(Stack *s);//彈出棧頂元素
T stack_top(Stack *s);//檢視棧頂元素
void stack_foreach(Stack *s,void (*foreach)(T));//遍歷
bool is_stack_out(T in[],T out[],size_t n);//判斷以in[]順序進棧，能否以out[]順序出棧；
#endif //_STACK_H__

stack.c

#include "stack.h"

int stack_init(Stack *s,size_t cap){
	s->base = calloc(cap,sizeof(T));
	s->cap = cap;
	s->size = 0;
}
void stack_destroy(Stack *s){
	if(s->base)
		free(s->base);
	s->base = NULL;
}
bool stack_is_empty(Stack *s){
	return s->size == 0;	
}
bool stack_is_full(Stack *s){
	return s->size == s->cap;	
}
void stack_clear(Stack *s){
	s->size = 0;	
}
void stack_push(Stack *s,T data){
	s->base[s->size++] = data;	
}
T stack_pop(Stack *s){
	return s->base[--s->size];	
}
T stack_top(Stack *s){
	return s->base[s->size-1];	
}
void stack_foreach(Stack *s,void (*foreach)(T)){
	int i;
	for(i=0;i<s->size;i++){
		foreach(s->base[i]);	
	}
}
bool is_stack_out(T in[],T out[],size_t n){
	Stack s;
	stack_init(&s,n);
	int i=0,j=0;
	for(i=0;i<n;i++){
		stack_push(&s,in[i]);//壓一個元素到棧裏面
		while((!stack_is_empty(&s))&&stack_top(&s)==out[j]){
			stack_pop(&s);
			++j;
		}
	}
	bool ret = stack_is_empty(&s);
	stack_destroy(&s);
	return ret;
}