一、概念
栈:栈是一个先进后出的线性表,它要求只在表尾进行删除和插入等操作。
所以栈其实就是一个线性表,不过操作有特殊的要求和限制:
- 元素必须先进后出;
- 操作只能在线性表尾进行
栈的基本操作只有2个
- 入栈(Push)
- 出栈(Pop)
栈的结构示意图(网上找的)
栈的结构示意图
二、栈的实现
下面介绍如何使用顺序表实现一个简单的栈
(1)定义栈的结构
typedef struct {
DATA data[SIZE+1]; //栈的数据元素,SIZE表示栈大小,数据从下标1开始保存
int top; //栈顶,top=0时表示栈为空
}SeqStack;
(2)初始化栈
SeqStack *SeqStackinit()
{
SeqStack *p;
if (p=(SeqStack *)malloc(sizeof(SeqStack))) {
p->top = 0;
return p;
}
return NULL;
}
(3)释放栈
void SeqStackFree(SeqStack *s)
{
if (s)
free(s);
}
(4)判断栈的状态
int SeqStackIsEmpty(SeqStack *s)
{
return (s->top == 0);
}
void SeqStackClear(SeqStack *s)
{
s->top = 0;
}
int SeqStackIsFull(SeqStack *s)
{
return (s->top == SIZE);
}
(5)入栈
int SeqStackPush(SeqStack *s, DATA data)
{
if ((s->top + 1) > SIZE) {
printf("栈溢出\n");
return 0;
}
s->data[++s->top] = data;
return 1;
}
(6)出栈
DATA SeqStackPop(SeqStack *s)
{
if (s->top == 0) {
printf("栈为空\n");
exit(0);
}
return (s->data[s->top--]);
}
(7)获取栈顶元素
DATA SeqStackPeek(SeqStack *s)
{
if (s->top == 0) {
printf("栈为空\n");
exit(0);
}
return (s->data[s->top]);
}
打完手工,可能有不完善或者bug,只能等以后发现了再修改了
网友评论