如何理解“栈”？
后进先出(LIFO-last in first out):最后插入的元素最先出来。
关于“栈”，有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。
从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
顺序栈
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
/* 顺序栈结构 */
//Sequence Stack
typedef struct {
SElemType data[MAXSIZE];
int top; //栈顶指针，这里的指针（记录位置）并非c中的指针，
} SqStack;
//1.初始化空栈
Status initStack(SqStack *S) {
S->top = -1;
return OK;
}
//2.置空栈
Status clearStack(SqStack *S) {
//这里不需要清空数组中的元素，编译器在编译阶段就知道该为这个数组分配多少内存了，这就叫静态分配,静态分配的内存在栈里，每进入一个函数时都会建栈，栈里会存放函数用到的参数、局部变量等信息，函数执行完以后，会出栈销毁栈，这个过程就会释放你静态分配的数组内存，这是由系统自动完成的。
S->top = -1;
return OK;
}
//3.判断栈空
Status stackEmpty(SqStack S) {
//结构体点语法
return S.top == -1;
}
//4.进栈push
Status stackPush(SqStack *s,SElemType e) {
//判断栈满
if (s->top == MAXSIZE-1) {
return ERROR;
}
//栈顶指针加一，将新插入的元素赋值给栈顶空间
s->data[++s->top] = e;
return OK;
}
//5.pop出栈，并且用e带回
Status pop(SqStack *s,SElemType *e) {
//判断栈空
if (stackEmpty(*s)) {
return ERROR;
}
//栈顶指针-1；
*e = s->data[s->top--];
return OK;
}
//6.获取栈顶元素
Status getTopElem(SqStack s,SElemType *e) {
//判断栈空
if (stackEmpty(s)) {
return ERROR;
}
*e = s.data[s.top];
return OK;
}
//7. 从栈底到栈顶依次打印栈中的每个元素
Status stackTraverse(SqStack s){
int i = 0;
printf("此栈中所有元素:\n");
while (i<=s.top) {
printf("%d ",s.data[i++]);
}
printf("\n");
return OK;
}
int main(int argc, const char * argv[]) {
printf("Hello, World!\n");
// SqStack *Sq = (SqStack *)malloc(sizeof(SqStack));//若使用指针要给指针开辟内存区域
SqStack Sq;//在函数中定义变量，系统会自动为变量分配内存保存到栈中
printf("%p",&Sq);
initStack(&Sq);
for (int i=0; i<10; i++) {
stackPush(&Sq, i);
}
stackTraverse(Sq);
return 0;
}
链式栈
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
//链栈节点
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
//定义栈
typedef struct {
LinkStackPtr top;//栈顶指针
int count;
}LinkStack;
//1.创建一个空栈
Status InitStack(LinkStack *s) {
(s)->top = NULL;
(s)->count = 0;
return OK;
}
//2.置空
Status clearStack(LinkStack *s) {
LinkStackPtr p,q;
p = s->top;
while (p) {
q = p;
p = p->next;
free(q);
}
(s)->count = 0;
return OK;
}
//3.判断栈空
Status emptyStack(LinkStack s) {
if (s.count == 0) {
return TRUE;
} else {
return FALSE;
}
}
//4.返回栈长
int lentthStack(LinkStack s) {
return s.count;
}
//5.取栈顶元素
Status getTopElem(LinkStack s, SElemType *e) {
//判断栈空
if (emptyStack(s)) {
return ERROR;
}
*e = s.top->data;
return OK;
}
//6.push入栈
Status pushStack(LinkStack *s,SElemType e) {
//创建一个节点
LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
if (temp == NULL) {
return ERROR;
}
temp->data = e;
//头插入栈
temp->next = s->top;
s->top = temp;
s->count++;
return OK;
}
//7.遍历打印栈中的元素
void traverseStack(LinkStack s) {
LinkStackPtr p = s.top;
while (p) {
printf("%d ",p->data);
p = p->next;
}
}
Status popStack(LinkStack *s,SElemType *e) {
//判断栈空
if (emptyStack(*s)) {
return ERROR;
}
//头删
LinkStackPtr p;
p = s->top;
*e = p->data;
s->top = s->top->next;
free(p);
s->count--;
return OK;
}
int main(int argc, const char * argv[]) {
LinkStack p;
InitStack(&p);
for (int i = 0; i<10; i++) {
pushStack(&p, i);
}
traverseStack(p);
SElemType e;
popStack(&p, &e);
printf("\n%d", e);
traverseStack(p);
return 0;
}
网友评论