棧的特點：先進后出

棧的操作：

用數組進行存儲

（1）初始化：

//棧
typedef struct {int *data;//指針模擬分配數組int top;//棧“頂”指針
}Stack;
//初始化
Stack InitStack(){Stack s;//給數組分配空間s.data = (int*)malloc(sizeof(int)*maxx);if(s.data == NULL){printf("內存申請失敗\n");return s;}//top是指向下一個數據的空間s.top = 0;return s;
}

（2）入棧：

//入棧
void push(Stack *s,int k){if(s == NULL){printf("棧區內存申請失敗\n");return ;}if(s->top == 0){printf("棧為空\n");return ;}s->data[s->top] = k;s->top++;}

（3）出棧：

//出棧
void pop(Stack *s){if(s == NULL){printf("棧區內存申請失敗\n");return ;}if(s->top == 0){printf("棧為空\n");return;}s->top--;
}

（4）判滿：

//判滿
int isFull(Stack s){if(s.top == maxx){printf("棧已滿\n");return -1;}return 1;}

（5）判空：

//判空
int isNull(Stack s){if(s.top == 0){printf("棧為空\n");return -1;}return 1;
}

上溢：數組滿了，繼續入棧，產生上溢

下溢：數組為空，繼續出棧，產生下溢

考題測試：

問：有n個數，入棧的順序固定好了，請問合法的出棧順序有多少個？

公式：C(2n,n)/(n+1),這稱為卡特蘭數。注：C(2n,n)是從2n個數中取出n個數。