【数据结构】栈及其C语言实现

栈

1 栈的定义与概念2 栈的基本操作3 栈的存储结构(代码实例介绍

3.1 顺序栈3.2 链栈3.3 顺序栈和链栈的优缺点 4 栈的扩展及其应用5 参考文献

图 1 数据结构 − 栈图1 ~数据结构-栈图1 数据结构−栈

1 栈的定义与概念

定义：栈就是只允许在一端进行插入删除的线性表。
概念: 1 栈底 2 栈顶 3空栈

图 2 栈的表示图2~栈的表示图2 栈的表示

2 栈的基本操作

I n i t S t a c k InitStack InitStack 初始化栈
P u s h Push Push 进栈
P o p Pop Pop 出栈
G e t T o p GetTop GetTop 获取栈顶元素
S t a c k E m p t y StackEmpty StackEmpty 判断栈是否为空
D e s t o r y S t a c k DestoryStack DestoryStack 销毁栈

3 栈的存储结构(代码实例介绍

以下顺序栈和链栈，将分别创造实例代码来讲述栈，同时通过实例来验证代码的正确性。

例：创建一个栈，元素 1 入栈，元素 2 入栈，元素 2 出栈，元素 3 入栈，元素 4 入栈，元素 5 入栈，再清除栈例：创建一个栈，元素1入栈，元素2入栈，元素2出栈，元素3入栈，元素4 入栈，元素5入栈，再清除栈例：创建一个栈，元素1入栈，元素2入栈，元素2出栈，元素3入栈，元素4入栈，元素5入栈，再清除栈

代码实现此例的三个时刻

时刻 ① ：时刻①：时刻①：初始时刻，栈内无元素，为空栈，栈长度为0；
时刻 ② ：时刻②：时刻②：元素1入栈，元素2入栈，元素2出栈，此时栈的长度为1，出栈元素为2；
时刻 ③ ：时刻③：时刻③：元素5入栈后，此时栈内长度为4，站内元素为 1 3 4 5 1~ 3 ~4 ~5 1 3 4 5；
时刻 ④ ：时刻④：时刻④：最后时刻，清除栈，栈内无元素，为空栈，栈长度为0.

3.1 顺序栈

#include
#include 
#define MAXSIZE 5
typedef struct
{
    int data[MAXSIZE];
    int top; // 用于栈顶指针 
}SqStack;

void InitStack(SqStack *S) // 初始化一个空栈 
{
	S->top=-1;
}

// 入栈：插入元素e为新的栈顶元素 
bool Push(SqStack *S, int e)
{
	if(S->top==MAXSIZE-1) return false; // 如果栈满，则错误 
	else{
		S->top++; // 栈顶指针加1 
		S->data[S->top]=e;
		return true;
	}
}

// 出栈：删除栈顶元素并将栈顶元素赋值给e
bool Pop(SqStack *S, int *e)
{
	if(S->top==-1) return false; // 如果栈空，报错
	else{
		*e=S->data[S->top]; // 将栈顶元素赋值给e 
		S->top--; // 栈顶指针减一 
		return true;
	} 
} 

// 获得栈顶元素 
bool GetTop(SqStack *S, int *e)
{
	if(S->top==-1) return false; // 栈空则没有栈顶元素 获取失败
	else{
	    *e=S->data[S->top]; // 将栈顶元素赋值给e 
		return true; 
	} 
}

// 判断栈是否为空
bool StackEmpty(SqStack *S)
{
	if(S->top==-1) return true;
	else{
		return false;
	}
} 

// 清空栈
bool ClearStack(SqStack *S)
{ 
        S->top=-1;
        return true;
} 


// 栈中元素个数
int StackLength(SqStack *S)
{ 
        return S->top+1;
} 

// 访问栈中元素 
bool visit(int c)
{
        printf("%d ",c);
        return true;
}

// 依次输出栈中元素
bool StackTraverse(SqStack *S)
{
        int i;
        i=0;
        while(i<=S->top)
        {
                visit(S->data[i++]);
        }
        printf("n");
        return true;
}
 
int main()
{
	SqStack S;
	InitStack(&S);  // 初始化一个空栈 
	
	printf("时刻①栈中元素：");
	StackTraverse(&S);
	printf("时刻①栈长为：%dn", StackLength(&S));
	printf("时刻①栈是否为空：");
	if(StackEmpty(&S)==true) printf("为空n");
	else printf("不为空n"); 
	printf("n");
	
	
	int j;
	for(j=1;j<=2;j++) Push(&S,j); // 元素1 2 入栈 
	int i; // i为出栈元素 应为2 
	Pop(&S, &i);
	printf("时刻②出栈元素为：%dn", i); 
	printf("时刻②栈中元素：");
	StackTraverse(&S);
	printf("时刻②栈长为：%dn", StackLength(&S));
	printf("时刻②栈是否为空：");
	if(StackEmpty(&S)==true) printf("为空n");
	else printf("不为空n"); 
	printf("n");
	
	
	for(j=3;j<=5;j++) Push(&S,j); // 元素3,4,5 入栈 

	printf("时刻③栈中元素：");
	StackTraverse(&S);
	printf("时刻③栈长为：%dn", StackLength(&S));
	printf("时刻③栈是否为空：");
	if(StackEmpty(&S)==true) printf("为空n");
	else printf("不为空n"); 
	printf("n");
	
	
	ClearStack(&S);
	printf("时刻④栈长为：%dn", StackLength(&S));
	printf("时刻④栈是否为空：");
	if(StackEmpty(&S)==true) printf("为空n");
	else printf("不为空n"); 
	printf("n");
}

运行结果：运行结果：运行结果：从结果来看，与例子一致。

图 3 顺序栈运行结果图3~ 顺序栈运行结果图3 顺序栈运行结果

3.2 链栈

在这里插入代码片

3.3 顺序栈和链栈的优缺点 4 栈的扩展及其应用 5 参考文献

【数据结构】栈及其C语言实现

C/C++/C#相关栏目本月热门文章