逻辑结构：在数据结构中栈只能在一段进行进栈和出栈操作的线性结构—所以满足后进先出的原则
物理结构：在存储结构上分为顺序栈和链栈
1.顺序栈
1.1顺序栈的结构体
#define MaxSize 10
typedef struct Stack
{
int data[MaxSize];//数组用于存放栈中的元素
int top;//栈顶指针
}SqStack;
1.2初始化顺序栈
//初始化栈
void InitStack(SqStack* S)
{
S->top = -1;//栈顶指针为-1表示为空栈
}
1.3栈的判空
//栈的判空
bool Empty(SqStack* S)
{
if (S->top == -1)
{
printf(" 这个栈是空栈\n");
return true;
}
else
{
return false;
}
}
1.4进栈操作
//进栈操作
bool Push(SqStack* S)
{
//进栈要先保证栈没有满
if (S->top >= MaxSize)
{
return false;
}
int x = 0;
printf("请输入要进栈的元素：");
scanf("%d", &x);
S->data[++S->top] = x;
//S->top=S->top+1;
// S->data[S->top]=x;
//先对指针加一，再进行赋值操作
return true;
}
1.5出栈操作
//出栈操作
bool Pop(SqStack* S,int* x)
{
//出栈要保证栈不空
if (S->top == -1)
{
return false;
}
//出栈操作只能取出栈顶元素
*x = S->data[S->top--];
//x=S->data[S->top];
//s->top--;
//这里的数据x依旧在内存当中并没有删除，只是在逻辑上删除了
return true;
}
1.6读出栈顶元素
//读栈顶元素与出栈操作区别不大
bool GetTop(SqStack* S,int* x)
{
//读栈顶元素要保证栈不空
if (S->top == -1)
{
return false;
}
*x = S->data[S->top];
return true;
}1.7完整的顺序栈代码
//顺序栈的基本操作
typedef struct Stack
{
int data[MaxSize];//数组用于存放栈中的元素
int top;//栈顶指针
}SqStack;
//初始化栈
void InitStack(SqStack* S)
{
S->top = -1;//栈顶指针为-1表示为空栈
}
//栈的判空
bool Empty(SqStack* S)
{
if (S->top == -1)
{
printf(" 这个栈是空栈\n");
return true;
}
else
{
return false;
}
}
//进栈操作
bool Push(SqStack* S)
{
//进栈要先保证栈没有满
if (S->top >= MaxSize)
{
return false;
}
int x = 0;
printf("请输入要进栈的元素：");
scanf("%d", &x);
S->data[++S->top] = x;
//S->top=S->top+1;
// S->data[S->top]=x;
//先对指针加一，再进行赋值操作
return true;
}
//出栈操作
bool Pop(SqStack* S,int* x)
{
//出栈要保证栈不空
if (S->top == -1)
{
return false;
}
//出栈操作只能取出栈顶元素
*x = S->data[S->top--];
//x=S->data[S->top];
//s->top--;
//这里的数据x依旧在内存当中并没有删除，只是在逻辑上删除了
return true;
}
//读栈顶元素与出栈操作区别不大
bool GetTop(SqStack* S,int* x)
{
//读栈顶元素要保证栈不空
if (S->top == -1)
{
return false;
}
*x = S->data[S->top];
return true;
}
int main()
{
SqStack S;
int x = 0;//用于记录栈顶元素，或者读出栈顶元素
InitStack(&S);
//先进栈5个元素
int i = 0;
for (i = 0; i < 5; i++)
{
Push(&S);
}
//出栈一个元素
Pop(&S,&x);
printf("出栈元素是%d\n", x);
//读出此时的栈顶元素
GetTop(&S,&x);
printf("此时的栈顶元素是%d\n", x);
return 0;
}
2.链栈
下面主要介绍不带头结点的链栈，并且把链表的表头当作链栈的栈顶。
2.1链栈的结构体和初始化
typedef struct LinkNode
{
int data;
struct LinkNode* next;
}LiStack;
//初始化链栈
void InitLiStack(LiStack** L)
{
(*L) = NULL;
}
int main()
{
LiStack* S=NULL;
int x = 0;
InitLiStack(&S);//这里涉及到二级指针
//进栈操作,先进栈五个元素
int i = 0;
for (i = 0; i < 5; i++)
{
Push(&S);
}
//出栈一个元素
Pop(&S,&x);
printf("出栈的元素是%d\n", x);
//获取栈顶元素
GetTop(S,&x);
printf("当前栈顶元素是%d\n", x);
}
2.2入栈操作
//入栈
bool Push(LiStack** L)
{
//对于链栈不存在栈满
int x = 0;
printf("请输入要进栈的整数:");
scanf("%d", &x);
LiStack* s = (LiStack*)calloc(1, sizeof(LiStack));
if (s == NULL)
{
return false;
}
s->data = x;
s->next = (*L);
(*L) = s;
return true;
}
2.3出栈操作
//出栈
bool Pop(LiStack** L, int* x)
{
//先判断栈是否为空
if (L == NULL)
{
return false;
}
(*x) = (*L)->data;
LiStack* p = (*L);
(*L) = p->next;
free(p);
return true;
}2.4读出栈顶元素
//获取栈顶元素
bool GetTop(LiStack* L,int* x)
{
//先判断栈是否为空
if (L == NULL)
{
return false;
}
(*x) = L->data;
return true;
}2.5链栈的整体代码
//不带头结点的链栈
typedef struct LinkNode
{
int data;
struct LinkNode* next;
}LiStack;
//初始化链栈
void InitLiStack(LiStack** L)
//这里涉及到二级指针
{
(*L) = NULL;
}
//入栈
bool Push(LiStack** L)
{
//对于链栈不存在栈满
int x = 0;
printf("请输入要进栈的整数:");
scanf("%d", &x);
LiStack* s = (LiStack*)calloc(1, sizeof(LiStack));
if (s == NULL)
{
return false;
}
s->data = x;
s->next = (*L);
(*L) = s;
return true;
}
//出栈
bool Pop(LiStack** L, int* x)
{
//先判断栈是否为空
if (L == NULL)
{
return false;
}
(*x) = (*L)->data;
LiStack* p = (*L);
(*L) = p->next;
free(p);
return true;
}
//获取栈顶元素
bool GetTop(LiStack* L,int* x)
{
//先判断栈是否为空
if (L == NULL)
{
return false;
}
(*x) = L->data;
return true;
}
int main()
{
LiStack* S=NULL;
int x = 0;
InitLiStack(&S);//这里涉及到二级指针，传递的是栈顶指针的地址
//进栈操作,先进栈五个元素
int i = 0;
for (i = 0; i < 5; i++)
{
Push(&S);
}
//出栈一个元素
Pop(&S,&x);
printf("出栈的元素是%d\n", x);
//获取栈顶元素
GetTop(S,&x);
printf("当前栈顶元素是%d\n", x);
}