栈的C语言实现

栈的C语言实现

简述

栈是实现后进先出（FIFO）策略的一种基本数据结构。我们可以通过多种方式实现栈这种数据结构。

我们可以用下面的结构体来定义栈：

typedef struct stack {

inttop;

intkey[M];

} stack;

栈的一个属性s.top指向最新插入的元素。栈的另外一个属性s.key[]存放的是元素的关键字，包含的元素为s.key[1…s.top]，其中s.key[1]是栈底元素，s.key[s.top]是栈顶元素。当s.top = 0时，栈空。

代码实现

下面程序省略了对上溢和下溢的检查。main()函数中的语句主要是栈的初始化和测试。

数组实现

最简单的方法也许就是数组了，不用考虑参数传递问题。

源代码如下：

# include <stdio.h>

# define M 100

int stackEmpty(int s[]);

void push(int s[], int x);

int pop(int s[]);

int main(void)

{

ints[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));

return0;

}

int stackEmpty(int s[])

{

if(s[0]== 0) {

return1;

}else {

return0;

}

}

void push(int s[], int x)

{

s[0]++;

s[s[0]]= x;

}

int pop(int s[])

{

if(s[0]== 0) {

return-1;

}else {

returns[s[0]--];

}

}

参数传值实现

注意：在参数传递的过程中使用的是地址。

源代码如下：

# include <stdio.h>

# define M 100

typedef struct stack {

inttop;

intkey[M];

} stack;

int stackEmpty(stack s);

void push(stack * s, int x);

int pop(stack * s);

int main(void)

{

stacks;

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) {

return1;

}else {

return0;

}

}

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--;

returnsp -> key[sp -> top + 1];

}

}

引用实现

引用很好用，可惜C语言里没有。

源代码如下：

# include <stdio.h>

# define M 100

typedef struct stack {

inttop;

intkey[M];

} stack;

int stackEmpty(stack s);

void push(stack & s, int x);

int pop(stack & s);

int main(void)

{

stacks;

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) {

return1;

}else {

return0;

}

}

void push(stack & s, int x)

{

s.top+= 1;

s.key[s.top]= x;

}

int pop(stack & s)

{

if(s.top== 0) {

return-1;

}else {

s.top--;

returns.key[s.top + 1];

}

}

全局变量实现

全局变量可以一直保存变量的值，不会因某个函数的结束而销毁，并且不用作为参数传递给函数。

源代码如下：

# include <stdio.h>

# define M 100

typedef struct stack {

inttop;

intkey[M];

} stack;

stack s;

int stackEmpty(void);

void push(int x);

int pop(void);

int main(void)

{

s.top= 0;

/*测试代码 */

push(2);

push(3);

printf("pop- %d\n", pop());

printf("stackEmpty- %d", stackEmpty());

}

int stackEmpty(void)

{

if(s.top== 0) {

return1;

}else {

return0;

}

}

void push(int x)

{

s.top+= 1;

s.key[s.top]= x;

}

int pop(void)

{

if(s.top== 0) {

return-1;

}else {

s.top--;

returns.key[s.top + 1];

}

}

另一种数组实现

第一种数组实现的时候使用s[0]表示s.top，如果定义一个新变量stop，可以让程序变得更加简单易读。

源代码如下：

# include <stdio.h>

# define M 100

int s[M];

int stop;

//stop = 0; //外部变量不能赋值吗？？

int stackEmpty(void);

void push(int x);

int pop();

int main(void)

{

stop= 0;

printf("stackEmpty- %d\n", stackEmpty());

push(3);

printf("stackEmpty- %d\n", stackEmpty());

push(5);

//printf("pop- %d - %d\n", pop(), pop()); //这是一个未定义行为

printf("pop- %d\n", pop());

printf("pop- %d\n", pop());

printf("stackEmpty- %d\n", stackEmpty());

return0;

}

int stackEmpty(void)

{

if(stop== 0) {

return1;

}else {

return0;

}

}

void push(int x)

{

s[++stop]= x;

}

int pop(void)

{

returns[stop--];

}

小记

作为一种基本的数据结构，栈的实现还是挺简单的。

（全文完）