栈的代码实现

更多数据结构实现代码

• 栈：一种特殊的线性表，它的插入和删除元素操作其只允许在线性表固定的一端进行。
• 允许进行数据操作的一端称为栈顶，另一端称为栈底。
• 处于栈顶位置的数据元素成为栈顶元素
• 不含任何元素的栈称为空栈
• 栈又称为后进先出的线性表

和线性表类似，栈也有两种存储结构：顺序存储结构和链式存储结构。

顺序栈

通常由一个一维数组和一个记录栈顶元素位置的变量组成。习惯上将栈底放在数组下标小的那端。顺序栈所有的操作时间复杂度为O(1)

顺序栈的代码实现

#define _CRT_SECURE_NO_WARNINGS 1

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

#define StackSize 5
typedef int DataType;

typedef struct SqStack
{
	DataType data[StackSize];  //保存栈中元素,元素的类型为DataType
	int top;   //栈指针，top的取值范围0~StackSize-1；top=-1表示栈空；top=StackSize-1表示栈满；top++表示进栈；top--表示出栈

}SqStack;

//初始化
void InitStack(SqStack &pst)//pst为引用型参数(C++)
{
	pst.top = -1;
}

//进栈：栈指针加1，将栈顶元素放进栈顶处
void Push(SqStack &pst, DataType x)
{
	if (StackSize-1 == pst.top)
	{
		printf("栈已满\n");
		return;
	}
	else {
		pst.top++;
		pst.data[pst.top] = x;
	}

}

//出栈：先将栈顶元素取出，然后将栈指针减一
DataType Pop(SqStack &pst)
{
	if (- 1 == pst.top)
	{
		printf("栈为空\n");
		return -1;
	}
	else {
		int x = pst.data[pst.top];
		pst.top--;
		return x;
	}
}

//查看栈顶元素：将栈指针top出的元素返回
DataType GetTop(SqStack st)
{
	if (-1 == st.top)
	{
		printf("栈为空\n");
		return -1;
	}
	else
		return st.data[st.top];
}

//判断栈是否为空
void StackEmpty(SqStack st)
{
	if (-1 == st.top)
	{
		printf("栈为空\n");
	}
	else
		printf("栈不为空\n");
}

//打印
void SeqListPrint(const SqStack st)
{
	int i = 0;
	for (i = 0; i < StackSize; i++)
	{
		printf("%d ", st.data[i]);
	}
	printf("\n");
}

void Test()
{
	SqStack s;
	SqStack& ps = s;
	InitStack(s);

	Push(ps, 1);
	Push(ps, 2);
	Push(ps, 3);
	Push(ps, 4);
	Push(ps, 5);
	SeqListPrint(s);

	printf("此时栈顶元素为：%2d\n", GetTop(s));

	printf("出栈元素为：%2d", Pop(ps));
	printf(",此时栈顶元素为：%2d\n", GetTop(s));
	printf("出栈元素为：%2d", Pop(ps));
	printf(",此时栈顶元素为：%2d\n", GetTop(s));
	
	StackEmpty(s);
}

int main()
{
	Test();
	system("pause");
	return 0;
}

结果展示：

链栈

采用链式存储结构的栈简称为链栈，其组织形式与单链表类似。其中，单链表的第一个结点就是链栈栈顶结点，栈由栈顶指针唯一确定，栈底结点的next指向NULL，因为链栈本身没有容量限制，故不存在栈满的情况。

代码：

#define _CRT_SECURE_NO_WARNINGS 1

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

typedef int DataType;

typedef struct SListStack
{
	struct SListStack* next;  //指针域
	DataType data;  //存储节点数据

}SListStack;


//初始化
void InitStack(SListStack *&pst)//pst为引用型参数(C++),
{
	pst = NULL;//pst为栈顶指针
}

//进栈
void Push(SListStack *&pst, DataType x)//SListStack **pst
{
	SListStack *p = (SListStack*)malloc(sizeof(SListStack));//创建一个节点
	p->data = x;
	p->next = pst;//p->next = *pst;
	pst = p;//*p = p;
	
}

//出栈
DataType Pop(SListStack *&pst)
{
	if (pst == NULL)
	{
		printf("栈为空\n");
		return -1;
	}
	else {
		SListStack *cur = pst;
		int x = cur->data;
		pst = cur->next;
		free(cur);
		return x;
	}
}

//查看栈顶元素
DataType GetTop(SListStack *st)
{
	if (NULL == st)
	{
		printf("栈为空\n");
		return -1;
	}
	else
		return st->data;
}

//判断栈是否为空
void StackEmpty(SListStack *st)
{
	if (NULL == st)
	{
		printf("栈为空\n");
	}
	else
		printf("栈不为空\n");
}

//打印
void StackPrint(SListStack *st)
{
	SListStack *cur = st;
	for (; cur != NULL; cur = cur->next)
	{
		printf("%2d->", cur->data);
	}
	printf("NULL\n");
}



void Test()
{
	SListStack *s;
	SListStack*& ps = s;
	InitStack(ps);

	Push(ps, 1);
	Push(ps, 2);
	Push(ps, 3);
	Push(ps, 4);
	Push(ps, 5);
	StackPrint(s);

	printf("此时栈顶元素为：%2d\n", GetTop(s));

	printf("出栈元素为：%2d", Pop(ps));
	printf(",此时栈顶元素为：%2d\n", GetTop(s));
	printf("出栈元素为：%2d", Pop(ps));
	printf(",此时栈顶元素为：%2d\n", GetTop(s));

	StackEmpty(s);
}

int main()
{
	Test();
	system("pause");
	return 0;
}

结果展示：