数据结构-栈（C语言）

栈的实现 数组

top指针指向栈里下一个可用空间的位置，top指向的地方永远没有元素。

#include
using namespace std;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define SElemType int
#define Status int
#define OK 1
#define ERROR 0
typedef struct {
	SElemType* base;
	SElemType* top;  //栈顶指针
	int stacksize;  //当前已分配的存储空间
}SqStack;

//栈的初始化
//1.申请一个数组空间
//2.初始化top指针指向base地址，意味着栈为空
//3.当栈满了，top指针的值=base+stacksize
Status InitStack(SqStack& S)
{
	S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base) exit(OVERFLOW);
	S.top = S.base;  
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}

//入栈
//1.top指针始终指向栈顶元素的上一个位置
//2.每入栈一个元素，top指针需向上移动
Status Push(SqStack &S, SElemType& e)
{
	if (S.top - S.base >= S.stacksize)  //栈满，追加存储空间
	{
		S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!S.base) exit(OVERFLOW);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;  //先将e赋值给当前top指针指向的位置，然后top++
	return OK;
}

//出栈
Status Pop(SqStack& S, SElemType& e)
{
	if (S.top == S.base) return ERROR;
	e = *--S.top; 
	return OK;
}

//获取栈顶元素值
Status GetTop(SqStack S, SElemType& e)
{
	if (S.top == S.base) return ERROR;  //栈为空
	e = *(S.top - 1);
	return OK;
}

//遍历栈
Status StackTraverse(SqStack S)
{
	SElemType* p;
	p = S.base;
	while (p < S.top)
	{
		cout << *p << ' ';
		p++;
	}
	cout << endl;
	return OK;
}
int main()
{
	SqStack s;
	SElemType e;
	InitStack(s);
	int n;
	cout << "输入初始化栈中元素的个数：";
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> e;
		Push(s, e);
	}
	
	cout << "栈中元素依次为：";
	StackTraverse(s);
	Pop(s, e);
	cout << "弹出的栈顶元素是：" << e << endl;
	GetTop(s, e);
	cout << "此时栈顶元素是：" << e;
	return 0;
}

链表

#include
using namespace std;

#define SElemType int
#define Status int
#define OK 1
#define ERROR 0
typedef struct StackNode {
	SElemType data;
	struct StackNode* next;
}StackNode,*LinkStack;

//栈的初始化
void InitStack(LinkStack& S)
{
	S= NULL;
}

//判断栈是否为空
Status StackEmpty(LinkStack S)
{
	return S == NULL;
}

//入栈
Status Push(LinkStack& S, SElemType &e)
{
	StackNode* p = (StackNode*)malloc(sizeof(StackNode));
	if (!p) return ERROR;
	p->data = e;
	p->next = S;
	S = p;
	return OK;
}

//出栈
Status Pop(LinkStack& S, SElemType& e)
{
	if (!S) return ERROR;
	StackNode* p = S;
	S = S->next;
	e = p->data;
	free(p);
	return OK;
}

//访问栈顶元素
Status GetTop(LinkStack& S,SElemType &e)
{
	e = S->data;
	return OK;
}

//从栈顶开始遍历栈
void LinkStackTraverse(LinkStack &S)
{
	StackNode* p = S;
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

int main()
{
	LinkStack s;
	SElemType e;
	InitStack(s);
	int n;
	cout << "输入初始化栈中元素的个数：";
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> e;
		Push(s, e);
	}
	cout << "栈中元素依次为：";
	LinkStackTraverse(s);
	Pop(s, e);
	cout << "弹出的栈顶元素是：" << e << endl;
	GetTop(s, e);
	cout << "此时栈顶元素是：" << e;
	return 0;
}