栈的代码实现
- 栈：一种特殊的线性表，它的插入和删除元素操作其只允许在线性表固定的一端进行。
- 允许进行数据操作的一端称为栈顶，另一端称为栈底。
- 处于栈顶位置的数据元素成为栈顶元素
- 不含任何元素的栈称为空栈
- 栈又称为后进先出的线性表
和线性表类似，栈也有两种存储结构：顺序存储结构和链式存储结构。
顺序栈
通常由一个一维数组和一个记录栈顶元素位置的变量组成。习惯上将栈底放在数组下标小的那端。顺序栈所有的操作时间复杂度为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;
}
结果展示：
