栈（stack）: 在逻辑上是一种线性存储结构，它有以下几个特点：
1、栈中数据是按照"后进先出（LIFO, Last In First Out）"方式进出栈的。
2、向栈中添加/删除数据时，只能从栈顶进行操作。
栈通常包括的三种操作：push、peek、pop。
push -- 向栈中添加元素。
peek -- 返回栈顶元素。
pop -- 返回并删除栈顶元素的操作。
栈底层可以基于数组(顺序表)，也可以基于链表。
基于数组实现的栈，需要满足数组的特点，查询快，不能动态增长。
基于链表实现的栈，可以动态增长，开销大。
一、数组栈
#include
#include
static int *stack=NULL;//指针，指向栈
static int count=0;//栈中元素的数量
static int MAXSIZE=0;//最大容量
void create_stack(int size){//传入栈的容量
stack=(int *)malloc(size*sizeof(int));//给栈分配空间
if(!stack){
printf("stack error!");//确认栈已经创建
exit(0);
}
MAXSIZE=size;
printf("创建成功\n");
}
//判空
int empty(){
if(count==0){
return 1;
}
return 0;
}
//判满
int up(){
if(count==MAXSIZE){
return 1;
}
return 0;
}
//入栈
void push(int e){
if(up()){
printf("stack is up!!!");//满了不能入栈
exit(0);
}
stack[count]=e;
count+=1;
printf("push successful\n");
}
//出栈
int pop(){
if(empty()){
printf("stack is empty!!!");//空了不能出栈
exit(0);
}
int s=stack[count];
count--;
printf("pop successful\n");
return s;
}
//遍历
void display(){
if(empty()){
printf("Empty Stack!!!");
exit(0);
}
printf("共有%d个元素\n",count);
for(int i=0;i printf("The data is %d\n",stack[i]); } } //元素数量 int len(){ return count; } //销毁栈 void destory_stack(){ if(stack){ free(stack); } printf("stack aleardy destory!\n"); } 在主函数中测试： int main(){ create_stack(10);//create stack,the size equll 10 push(1); push(3); push(5); push(7); push(9); push(11); push(0); display(); pop(); pop(); pop(); display(); destory_stack(); } 结果如下： 创建成功 push successful push successful push successful push successful push successful push successful push successful 共有7个元素 The data is 1 The data is 3 The data is 5 The data is 7 The data is 9 The data is 11 The data is 0 pop successful pop successful pop successful 共有4个元素 The data is 1 The data is 3 The data is 5 The data is 7 stack aleardy destory! 二、链表栈 链表有单链表，双链表，循环链表等。都可以实现栈，以下就是基于单链表实现的栈。 #include #include typedef struct list_stack{ int data; struct list_stack *next; }Stack; static int count=0;//长度 static Stack *head=NULL;//头指针 static Stack *tail=NULL;//尾巴指针 //节点初始化的工具 Stack *init(){ Stack *p=(Stack *)malloc(sizeof(Stack)); return p; } //创建栈 Stack *create_stack(){ head=init(); head->data=NULL; tail=head;//尾巴指针，作为工作指针 printf("Stack is created!\n"); count++;//栈有了头节点 } //判空 int empty(){ if(count==0){ return 1; } return 0; } //入栈 void push(int e){ Stack *p=init(); p->data=e; tail->next=p; tail=p; count+=1; printf("push successful\n"); } //出栈 int pop(){ if(empty()){ printf("stack is empty!!!");//空了不能出栈 exit(0); } int n=tail->data; Stack *p=head; for(int i=1;i p=p->next; } tail=p; count--; printf("pop is successful!\n"); free(tail->next); return n; } //遍历 void display(){ if(empty()){ printf("Empty Stack!!!"); exit(0); } printf("共有%d个元素\n",count-1); Stack *p=head; for(int i=1;i p=p->next; printf("The data is %d\n",p->data); } } //销毁栈 void destory_stack(){ for(Stack *p=head;head!=NULL;){ head=head->next; free(p); p=head; } printf("stack aleardy destory!\n"); } 主函数： int main(){ create_stack(); push(1); push(3); push(5); push(7); push(9); display(); pop(); pop(); display(); destory_stack(); } 输出： ^ Stack is created! push successful push successful push successful push successful push successful 共有5个元素 The data is 1 The data is 3 The data is 5 The data is 7 The data is 9 pop is successful! pop is successful! 共有3个元素 The data is 1 The data is 3 The data is 5 数据结构与算法学习目录