数据结构——栈以及相应的操作

栈(Stack)

在维基百科中是这样定义的：
堆栈(stack) 又称为栈或堆叠，是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合中的一端（称为堆栈顶端，top）进行加入数据（push）和移除数据（pop）的运算。因而按照 后进后出 （LIFO,Last In First Out）的原理运作，堆栈常用 一维数组 或 链式串列 来实现。常与另一种有序的线性资料集合队列相提并论。

说白了就是，只允许在一端进行操作的线性表。

• 栈的定义

顺序存储, 使用一维数组的形式实现

#define MaxSize 8
typedef int ElemType;	// 使用类型的重定向
// 顺序存储实现栈
typedef struct {ElemType data[MaxSize];	// 使用数组来存储数据int top;	// 栈顶变量
}SqStack;// 定义顺序存储的栈
SqStack S;// 栈的初始化
void InitStack(SqStack &S)
{S.top = -1;
}
// 判断栈是否为空
bool isStackEmpty(SqStack S)
{if (-1 == S.top) return true;else 			 return false;
}

链式存储,只展现定义，不展现链式存储的栈的出栈和入栈操作

LinkStack Lhead = (LinkStack)malloc(sizeof(LinkNode));
Lhead->next = NULL;
LinkStack top = NULL;
top = (LinkStack)malloc(sizeof(LinkNode));
top->next = NULL;
top->data = 1;
top->next = Lhead->next;
Lhead->next = top;

入栈，压栈(Push Stack)

压栈，就是将要入栈的数据从栈顶(Top)向下“压”! 就像往弹夹中压子弹的操作一样，霰弹枪除外！

代码示例:

bool PushStack(SqStack &S, ElemType push_data)
{// 判断剩余的栈内存，如果栈满则return false 防止溢出if(S.top == MaxSize - 1) return false;S.data[++S.top] = push_data;	// 先让栈顶的位置自增1，再赋值return true;
} 

出栈 （Pop Stack）

栈的核心就是先入先出 ，所以出栈需要从栈顶开始"弹出"， 就像从弹夹中发射子弹一样，发射的总是最上面的子弹。

代码示例:

bool PopStack(SqStack &S, ElemType &pop_data)
{// 判断栈是否为空if (isStackEmpty(S)) return false;pop_data = S.data[S.top--];	// S.top用完再自减return true;
}

完整的栈操作代码示例:

#include <cstdio>
#include <cstdlib>
#include <cstdbool>#define MaxSize 5
typedef int ElemType;	// 类型重定义// 定义栈
typedef struct {ElemType data[MaxSize];	// 使用数组存储int top;	// 存储栈顶位置的变量
}SqStack;// 初始化栈
void InitStack(SqStack &S)
{S.top = -1;
}// 判断栈是否为空
bool isStackEmpty(SqStack S)
{if (-1 == S.top) return true;else 			 return false;
}
// 压栈
bool PushStack(SqStack &S, ElemType push_data)
{// 判断栈内剩余的空间if((MaxSize - 1) == S.top) return false;S.data[++S.top] = push_data;return true;
}// 出栈
bool PopStack(SqStack &S, ElemType &pop_data)
{// 判断栈是否为空if (isStackEmpty(S)) return false;pop_data = S.data[S.top--];return true;
}// 打印栈中的元素
void StackPrint(SqStack S)
{SqStack stack_copy = S;while (-1 != stack_copy.top) {printf(" %d", stack_copy.data[stack_copy.top--]);}printf("\n");
}int main()
{SqStack S;	//定义一个栈数据结构InitStack(S);for (int i = 0; i < 4; i++) PushStack(S, i + 1);bool ret = PushStack(S, 5);if (ret) {printf("Pushing stack is successful!, Stack's element:");StackPrint(S);}else printf("Pushing stack is fail!\n");ret = PushStack(S, 6);if (ret) {printf("Pushing stack is successful!, Stack's element:");StackPrint(S);}else printf("Pushing stack is fail!\n");ElemType pop_data;ret = PopStack(S, pop_data);if (ret) {printf("Poping stack is successful!, pop element: %d\n", pop_data);}else printf("Poping stack is fail!\n");return 0;
}

运行结果：