- 栈的定义
- 基本运算:
- 顺序栈：
- 顺序栈基本运算代码实现:
- 创建空栈:`CreateStack(len)`
- 清空栈:`ClearStack(S)`
- 判断是否栈空:`EmptyStack(S)`
- 判断是否栈满:`FullStack(S)`
- 元素进栈:`PushStack(s,x)`
- 元素出栈:`PopStack(S)`
- 取栈顶元素:`GetTop(S)`
- 链式栈
- 链式栈基本运算代码实现:
- 创建空栈:`CreateLinkStack()`
- 判断是否栈空:`EmptyStack(linkstack_t *top)`
- 元素入栈:`PushLinkStack(linkstack_t *top , dadta_t x)`
- 元素出栈:`PopLinkStack(S)`
- 取栈顶元素:`GetTop(S)`
- 清空栈:`ClearLinkStack(S)`
- 释放栈:`freeLinkStack(S)`
- 栈： 栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈)，允许进行操作的一端称为“栈顶”，另一固定端称为“栈底”，当栈中没有元素时称为“空栈”。
- 特点:后进先出(LIFO)。
我们来检验一下你是否明白了后进先出，
已知元素的入栈顺序为abcde，则出栈顺序为多少？哪个不可能
答案：edcba ，bcdea，dcbae 可能，cabde 不可能
- 创建空栈:CreateStack(len)
- 清空栈:ClearStack(S)
- 判断是否栈空:EmptyStack(S)
- 判断是否栈满:FullStack(S)
- 元素进栈:PushStack(s,x)
- 元素出栈:PopStack(S)
- 取栈顶元素:GetTop(S)
栈的存储方式：顺序存储，链式存储
顺序栈：它是顺序表的一种，具有顺序表相同的存储结构，由数组定义，配合用数组下标表示的栈顶指针tip（相对指针）完成各种操作。
typedef int data_t; //定义栈中数据元素的数据类型
typedef struct{
data_t *data; //用指针指向栈的存储空间
int maxlen; //当前栈的最大元素个数
int top; //指示栈顶位置（数组下标）的变量
}seqstack_t; //顺序栈类型定义
顺序栈基本运算代码实现:
创建空栈:CreateStack(len)
#include"sqstack.h"
sqstack *stack_create(int len){
sqstack *s;
if((s=(sqstack *)malloc(sizeof(sqstack)))==NULL){
printf("malloc falsen");
return NULL;
}
if((s->data=(datatype *)malloc(len *sizeof(datatype))) == NULL){
printf("malloc falsen");
return NULL;
}
s->maxlen = len;
s->top =-1;
return s;
}
清空栈:ClearStack(S)
void stack_clear(sqstack *s){
s->top= -1;
}
判断是否栈空:EmptyStack(S)
int stack_empty(sqstack *s){
return(s->top == -1 ? 1 : 0);
}
判断是否栈满:FullStack(S)
int stack_full(sqstack *s){
return(s->top == s->maxlen-1 ? 1 : 0);
}
元素进栈:PushStack(s,x)
- 入栈前考虑的问题
- 栈空间是否已经满了
- 先存入数据
- top+1
int stack_push(sqstack *s,datatype value){
if(s->top == s->maxlen-1){
puts("stack is fulled");
return -1;
}
s->data[s->top+1] = value;
s->top++;
return 1;
}
元素出栈:PopStack(S)
datatype stack_pop(sqstack *s){
s->top--;
return s->data[s->top+1];
}
取栈顶元素:GetTop(S)
datatype stack_top(sqstack *s){
return(s->data[s->top]);
}
链式栈
插入操作和删除操作均在链表头部进行，链表尾部就是栈底，栈顶指针就是头指针。
允许操作的一端叫栈顶，不允许操作的一端叫栈底。
typedef int data_t; //定义栈中数据元素数据类型
typedef struct node_t
{
data_t data; //数据域
struct node_t *next; //链接指针域
}linkstack_t; //链栈类型定义
链式栈基本运算代码实现:
创建空栈:CreateLinkStack()
#include"linkstack.h"
linklist linkstack_create(){
linklist s;
if((s=(linklist)malloc(sizeof(listnode)))==NULL){
printf("malloc falsen");
return NULL;
}
s->next = NULL;
return s;
}
判断是否栈空:EmptyStack(linkstack_t *top)
判断栈顶（s->next）是否为空
#include"linkstack.h"
int linkstack_empty(linklist s){
return (s->next == NULL ? 1:0);
}
元素入栈:PushLinkStack(linkstack_t *top , dadta_t x)
#include"linkstack.h"
int linkstack_push(linklist s,datatype value){
linklist p;
if((p=(linklist)malloc(sizeof(listnode)))==NULL){
printf("malloc falsen");
return NULL;
}
p->data=value;
p->next = s->next;
s->next = p;
return 0;
}
元素出栈:PopLinkStack(S)
#include"linkstack.h"
datatype linkstack_pop(linklist s){
linklist p;
datatype ret;
p = s->next;
s->next = p->next;
ret = p->data;
free(p);
p=NULL;
return ret;
}
取栈顶元素:GetTop(S)
#include"linkstack.h"
datatype linkstack_top(linklist s){
return (s->next->data);
}
清空栈:ClearLinkStack(S)
void linkstack_clear(linklist s){
linklist p;
p=s->next;
puts("clean: ");
while(p){
s->next = p->next;
printf("%d ",p->data);
free(p);
p = s->next;
}
}
释放栈:freeLinkStack(S)
释放栈和清空栈的区别是：头结点也删除了
datatype linkstack_top(linklist s){
return (s->next->data);
}
linklist_free(linklist s){
linklist p;
while(p){
s = s->next;
free(p);
p=s;
}
}
-----------------------------------------很棒学习完了数据结构的 栈--------------------------------------------------
--------------------------------------------------------[下期预告：队列]------------------------------------------------------
