一、栈的特点
1、逻辑结构：线性结构，具有栈顶和栈底。
2、只允许在一端插入(入栈)和删除(出栈)，具有后进先出的特点。
二、顺序栈
top：
①栈顶数据下标
②空：top = -1
三、用C语言实现顺序栈
1、构造存储结构
#define SIZE 8
typedef int datatype;
typedef struct seqstack{
datatype data[SIZE];
int top;
}seq_stack, *seq_pstack;
2、初始化
初始化主要工作：①申请内存空间；②
top = -1;
void init_seqstack(seq_pstack *stack)
{
(*stack) = (seq_pstack)malloc(sizeof(seq_stack));
if (NULL == stack)
{
perror("malloc");
exit(1);
}
(*stack)->top = -1;
}
3、判断栈是否已满
判断top是否为SIZE - 1即可。
bool isfull_seqstack(seq_pstack stack)
{
if (SIZE - 1 == stack->top)
{
return true;
}
else
{
return false;
}
}
4、入栈
① top++
② data[top] = d;
void push_seqstack(seq_pstack stack, datatype dat)
{
if (isfull_seqstack(stack))
{
printf("栈已满\n");
return;
}
stack->top++;
stack->data[stack->top] = dat;
}
5、判断栈是否为空
bool isempty_seqstack(seq_pstack stack)
{
if (-1 == stack->top)
{
return true;
}
else
{
return false;
6、出栈
void pop_seqstack(seq_pstack stack, datatype *dat)
{
if (isempty_seqstack(stack))
{
printf("栈为空\n");
return;
}
*dat = stack->data[stack->top]; //出栈数据保存在*dat中
stack->top--;
}
三、练习题
用顺序栈实现整数的逆序输出。例如输入整数1，2，3，输出3，2，1
1、实现代码
int main(void)
{
seq_pstack stack = NULL;
int data = 0;
int ret = 0;
init_seqstack(&stack); // 初始化
while (1)
{
printf("输入整数:");
ret = scanf("%d", &data);
if (0 == ret)
{
printf("bye-bye\n");
break;
}
else
{
push_seqstack(stack, data);
printf("输出:\t");
show_seqstack(stack);
}
}
return 0;
}