链栈的基本操作C/C++代码实现

链栈的结构：

由于栈的主要操作是在栈顶插入和删除， 显然以链表的头部作为栈顶是最方便的，且不需要附加一个头结点。

初始化：

栈顶指针S置空即可。

入栈：

链栈不需要判断栈是否满！

出栈：

栈顶指针S等于NULL表空栈，即链栈S==NULL时为空栈。

代码如下：

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 100
typedef int SElemType;

//链栈的存储结构
typedef struct StackNode
{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;

//初始化
void InitStack(LinkStack &S)
{
	S = NULL;	//构造一个空栈，栈顶指针置空即可
}

//入栈
int Push(LinkStack &S, SElemType e)
{
	//链栈不需要判断栈满

	StackNode *p = new StackNode;
	p->data = e;
	p->next = S;
	S = p;
	return 1;
}

//出栈
int Pop(LinkStack &S, SElemType &e)
{
	if (S==NULL) return 0;    //栈空

	StackNode *p = S;
	e = S->data;
	S = S->next;
	delete p;
	return 1;
}

//取栈顶元素
SElemType GetTop(LinkStack S)
{
	if (S!=NULL)	 //非栈空时返回
		return S->data;   
}

//遍历输出栈
void printStack(LinkStack S)
{
	printf("栈顶->");
	StackNode *p = S;
	while (p!=NULL)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

int main()
{
	LinkStack S;
	int e;
	InitStack(S);
	printf("请输入一个要入栈的元素（-1表示结束）：");
	scanf("%d",&e);
	while (e!=-1)
	{
		Push(S,e);
		printf("请输入一个要入栈的元素（-1表示结束）：");
		scanf("%d", &e);
	}
	printStack(S);
	printf("出栈测试：");
	Pop(S, e);
	printStack(S);

	printf("取栈顶元素测试：");
	e=GetTop(S);
	printf("取出的栈顶元素为：%d\n",e);
}

运行结果：