### 順序棧
#### 1.1順序棧的定義
~~~
/*
順序棧基本操作
*/
#include <stdio.h>
#include <stdlib.h>
//定義棧中最大元素的個數.
#define MAXNUM 20
typedef int DataType;
typedef struct SeqStack{
int t; //棧頂位置指示
DataType s[MAXNUM];
}SeqStack,*PSeqStack;
//創建一個空棧;為棧結構申請空間.并將棧頂元素變量賦值為－1
PSeqStack createEmptyStack(void);
//判斷pastack所指的棧是否為空，當pastack所指的棧為空時返回1;否者為0.
int isEmptyStack(PSeqStack pastack);
//壓棧操作
void push_seq(PSeqStack pastack,DataType e);
//出棧操作
void pop_seq(PSeqStack pastack);
//pastack不為空棧時，求棧頂元素
DataType getTop_seq(PSeqStack pastack);
~~~
#### 1.2 初始化棧
~~~
PSeqStack createEmptyStack(){
PSeqStack pastack=(PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack==NULL)
{
printf("Error:out of space\n");
}else{
pastack->t=-1;
}
return pastack;
}
~~~
#### 1.3判斷棧是否為空
~~~
int isEmptyStack(PSeqStack pastack){
return pastack->t==-1;
}
~~~
#### 1.4入棧操作
~~~
void push_seq(PSeqStack pastack,DataType e){
if(pastack->t>=MAXNUM-1){
printf("Stack Overflow!\n");
}else{
pastack->t++;
pastack->s[pastack->t]=e;
}
}
~~~
#### 1.5出棧操作
~~~
void pop_seq(PSeqStack pastack){
if (pastack->t==-1)
{
printf("UnderFlow!\n");
}else{
printf("Pop:%d\n",pastack->s[pastack->t]);
pastack->t--;
}
}
~~~
#### 1.6返回棧頂元素
~~~
DataType getTop_seq(PSeqStack pastack){
return pastack->s[pastack->t];
}
~~~
#### 1.7測試
~~~
int main(){
PSeqStack stack1=createEmptyStack();
push_seq(stack1,1);
push_seq(stack1,2);
push_seq(stack1,3);
printf("%d\n",getTop_seq(stack1));
pop_seq(stack1);
pop_seq(stack1);
pop_seq(stack1);
return 0;
}
~~~
### 鏈棧
#### 2.1鏈棧定義
~~~
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct Node;
typedef struct Node *PNode;
struct Node
{
DataType info;
PNode link;
};
struct LinkStack
{
PNode top;
};
typedef struct LinkStack *PLinkStack;
// 申請鏈棧結構空間，創建一個空鏈棧,返回指向空鏈接的指針.
PLinkStack createEmptyStack_link(void);
// 鏈式棧是否為空棧
int isEmptyStack_link(PLinkStack plstack);
//入棧
void push(PLinkStack plstack, DataType e);
//出棧
void pop(PLinkStack plstack);
//對非空棧求棧頂元素
~~~
#### 2.2初始化棧
~~~
PLinkStack createEmptyStack_link(){
PLinkStack plstack=(PLinkStack)malloc(sizeof(struct LinkStack));
if (plstack==NULL)
{
printf("Out of space\n");
}else{
plstack->top=NULL;
}
return plstack;
}
~~~
#### 2.3判斷棧是否為空
~~~
int isEmptyStack_link(PLinkStack plstack){
return plstack->top==NULL;
}
~~~
#### 2.4入棧操作
~~~
void push(PLinkStack plstack,DataType e){
PNode newnode=(PNode)malloc(sizeof(struct Node));
if(newnode==NULL){
printf("Out of space.\n");
}else{
newnode->info=e;
newnode->link=plstack->top;
plstack->top=newnode;
}
}
~~~
#### 2.5出棧操作
~~~
void pop(PLinkStack plstack){
if (isEmptyStack_link(plstack))
{
printf("Empty Stack pop.\n");
}else{
PNode p=plstack->top;
printf("%d\n",p->info);
plstack->top=plstack->top->link;
free(p);
}
}
~~~
#### 2.6測試代碼
~~~
int main(){
PLinkStack plstack1=createEmptyStack_link();
push(plstack1,1);
push(plstack1,3);
push(plstack1,5);
pop(plstack1);
pop(plstack1);
pop(plstack1);
pop(plstack1);
}
~~~
