栈的多种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\n", stackEmpty(s));
 push(s, 2);
 push(s, 5);
 printf("stackEmpty - %d\n", stackEmpty(s));
 printf("pop - %d\n", 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\n", 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];
 }
}