数据结构与算法基础-学习-09-线性表之栈的理解、初始化顺序栈、判断顺序栈空、获取顺序栈长度的实现

一、个人理解

栈是线性表的一种衍生，和之前的顺序表和链表在插入和删除元素上有较大差异，其他基本相同，栈是数据只能插入表的尾部（栈顶），删除数据时只能删除表的尾部（栈顶）数据，就是大家经常背的顺口溜：后入先出。后插入的数据先删除。

二、图解

这里把数组竖起来了，是方便理解，看得更清楚。

三、名词解释

1、出栈、弹栈

是一个意思，就是把数据从栈顶移除。

2、入栈、压栈

是一个意思，就是把数据从栈顶插入。

3、LIFO

LAST IN FIRST OUT的简写，也就是后进先出的意思。

4、顺序栈和链栈

实现方式上的不同，顺序栈是用数组实现，而链栈是用链表实现。

5、上溢

栈已满，但数据还需要继续入栈。上溢一般认为是一种错误，因为可能导致数据录入失败，或者导致数据录入延时。当是顺序栈时，对此情况有两种措施：

一是抛出错误。

二是重新申请新栈，把旧栈数据写入到新栈中，不推荐，比较耗时。

6、下溢

栈已空，但还是要出栈。下溢一般认为是一种结束标志，因为并不会有数据上的缺失。

四、函数实现

1、InitSqStack

（1）用途

初始化顺序栈。

（2）源码

Status InitSqStack(SqStack* S)
{printf("Init SqStack  : ");JudgeAllNullPointer(S);S->BasePointer    = (SqElemType*)MyMalloc(sizeof(SqElemType) * SQ_STACK_MAX_SIZE);S->TopPointer     = S->BasePointer;S->SqStackMaxSize = SQ_STACK_MAX_SIZE;printf("OK\n");PrintPretty();return SuccessFlag;   
}

（3）参数

参数名	说明
S	需要初始化的SqStack*类型顺序栈。

2、JudgeSqStackIsEmpty

（1）用途

判断顺序栈是否为空。

当栈顶指针和栈底指针相等时，表示栈为空，反之非空。

（2）源码

Status JudgeSqStackIsEmpty(SqStack* S)
{printf("Judge SqStack : ");JudgeAllNullPointer(S);if(S->BasePointer == S->TopPointer){printf("Empty\n");PrintPretty();return SuccessFlag;}printf("Not Empty\n");PrintPretty();return FailFlag;
}

（3）参数

参数名	说明
S	需要判断是否为空的SqStack*类型顺序栈。

3、GetSqStackLen

（1）用途

求顺序栈的长度。

栈顶指针减去栈底指针为顺序栈的长度，原理为相同类型的指针相减得到字节数，它会再除以一个栈类型（头文件中的结构体SqElemType）的字节长度，得到最终的顺序栈的长度。

（2）源码

SqStackMaxSizeType GetSqStackLen(SqStack* S)
{JudgeAllNullPointer(S);return S->TopPointer - S->BasePointer;
}

（3）参数

参数名	说明
S	需要求栈长度的SqStack*类型顺序栈。

五、测试代码

1、SqStack.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/time.h>
#include "SqStack.h"void PrintPretty()
{printf("*********************************\n");
}void PrintPretty_V1()
{printf("################\n");
}void *MyMalloc(size_t size)
{void *Result = (void *)malloc(size);if(Result == NULL){printf("malloc Function Exec Fail , Out Of Memory ,Exit!!!\n");exit(ExceptionExitFlag);}return Result;
}void JudgeAllNullPointer(void* P)
{if(!P){printf("Pointer Is Null ,Exit !\n");exit(ExceptionExitFlag);}
}Status InitSqStack(SqStack* S)
{printf("Init SqStack  : ");JudgeAllNullPointer(S);S->BasePointer    = (SqElemType*)MyMalloc(sizeof(SqElemType) * SQ_STACK_MAX_SIZE);S->TopPointer     = S->BasePointer;S->SqStackMaxSize = SQ_STACK_MAX_SIZE;printf("OK\n");PrintPretty();return SuccessFlag;   
}Status JudgeSqStackIsEmpty(SqStack* S)
{printf("Judge SqStack : ");JudgeAllNullPointer(S);if(S->BasePointer == S->TopPointer){printf("Empty\n");PrintPretty();return SuccessFlag;}printf("Not Empty\n");PrintPretty();return FailFlag;
}SqStackMaxSizeType GetSqStackLen(SqStack* S)
{JudgeAllNullPointer(S);return S->TopPointer - S->BasePointer;
}

2、SqStack.h

#ifndef SqStack_H
#define SqStack_H#define InsertDataArrayLen 8
#define SQ_STACK_MAX_SIZE  6#define ExceptionExitFlag -1
#define SuccessFlag        1
#define FailFlag           0
#define StudentNumLen      8
#define StudentNameLen     8typedef int Status;
typedef long long int SqStackMaxSizeType;typedef struct SqElemType
{char StudentNum[StudentNumLen];char StudentName[StudentNameLen];int  StudentScore;
}SqElemType;typedef struct 
{SqElemType*        BasePointer;SqElemType*        TopPointer;SqStackMaxSizeType SqStackMaxSize;
}SqStack;void *MyMalloc(size_t size);
void JudgeAllNullPointer(void* P);
void PrintPretty();
void PrintPretty_V1();Status InitSqStack(SqStack* S);
Status JudgeSqStackIsEmpty(SqStack* S);
SqStackMaxSizeType GetSqStackLen(SqStack* S);#endif

3、main.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "SqStack.h"int main()
{//测试数据生成SqElemType *InsertSqElemArray = (SqElemType *)MyMalloc(sizeof(SqElemType) * InsertDataArrayLen);int i;for(i=0; i<InsertDataArrayLen; i++){strcpy(InsertSqElemArray[i].StudentNum ,"X666");strcpy(InsertSqElemArray[i].StudentName,"Sun");InsertSqElemArray[i].StudentScore = i + 100;}//测试顺序栈SqStack* S = (SqStack*)MyMalloc(sizeof(SqStack));InitSqStack(S);JudgeSqStackIsEmpty(S);printf("SqStack Len   : %lld\n",GetSqStackLen(S));PrintPretty();//释放内存free(InsertSqElemArray);InsertSqElemArray = NULL;return SuccessFlag;
}

4、makefile

CC = gcc
CFLAG_EXEC = -Wall -O3
CFLAG_ALIAS = -o
RM_COMM = rm -rfall : mainmain : $(CC) $(CFLAG_EXEC) SqStack.c main.c $(CFLAG_ALIAS) TestSqStackclean : $(RM_COMM) TestSqStack

六、测试结果

[gbase@czg2 LinearTable_Stack]$ make clean
rm -rf TestSqStack[gbase@czg2 LinearTable_Stack]$ make
gcc -Wall -O3 SqStack.c main.c -o TestSqStack[gbase@czg2 LinearTable_Stack]$ ./TestSqStack 
Init SqStack  : OK
*********************************
Judge SqStack : Empty
*********************************
SqStack Len   : 0
*********************************

七、顺序栈的应用

大家可以参考一下之前写的文章《leecode-C语言实现-20. 有效的括号》，里面用到了顺序栈的知识。