栈的多种C语言实现

标题：栈的多种C语言实现内容：栈是一种后进先出（LIFO）的数据结构，C语言中可以使用数组、全局变量、指针传参、引用传参等方法实现。作者：MilkCu

概念

栈的定义

我们可以使用下面的结构体来定义栈：typedef struct stack {
int top;
int key[M];
} stack;

栈的属性

以栈s为例讨论。s.top指向最新插入的元素。
当栈中包含的元素为s.key[1..s.top]，其中s.key[1]是栈底元素，s.key[s.top]是栈顶元素。

栈的操作

压入（push）：将数据放在栈顶；弹出（pop）：返回弹出值，并删除元素。

栈的状态

s.top = 0时，栈中不包含任何元素，即栈是空的。

实现

普通数组实现

最简单的实现方法，不会涉及到结构体的参数传递问题。使用s[0]表示s.top。# include <stdio.h>
# define M 100
int stackEmpty（int s[]）;
void push（int s[], int x）;
int pop（int s[]）;
int main（void）
{
int s[M];
s[0] = 0;
printf（"stackEmpty - %d ", stackEmpty（s））;
push（s, 2）;
push（s, 5）;
printf（"stackEmpty - %d ", stackEmpty（s））;
printf（"pop - %d ", pop（s））;
return 0;
}
int stackEmpty（int s[]）
{
if（s[0] == 0） {
return 1;
} else {
return 0;
}
}
void push（int s[], int x）
{
s[0]++;
s[s[0]] = x;
}
int pop（int s[]）
{
if（s[0] == 0） {
return -1;
} else {
return s[s[0]--];
}
}

指针传参实现

传递参数的时候要用指针，否则不能改变参数的值！# include <stdio.h>
# define M 100
typedef struct stack {
int top;
int key[M];
} stack;
int stackEmpty（stack s）;
void push（stack * s, int x）;
int pop（stack * s）;
int main（void）
{
stack s;
s.top = 0;
/* 测试代码 */
push（&s, 2）;
push（&s, 3）;
printf（"pop - %d ", pop（&s））;
printf（"stackEmpty - %d", stackEmpty（s））;
}
int stackEmpty（stack s）
{
if（s.top == 0） {
return 1;
} else {
return 0;
}
}
void push（stack * sp, int x）
{
sp -> top += 1;
sp -> key[sp -> top] = x;
}
int pop（stack * sp）
{
if（sp -> top == 0） {
return -1;
} else {
sp -> top--;
return sp -> key[sp -> top + 1];
}
}