数据结构基础--顺序栈

顺序栈的概念：顺序栈是栈的顺序实现。顺序栈是指利用顺序存储结构实现的栈。采用地址连续的存储空间（数组)依次存储栈中数据元素，由于人栈和出栈运算都是在栈顶进行，而栈底位置是固定不变的，可以将栈底位置设置在数组空间的起始处；栈顶位置是随入栈和出栈操作而变化的，故需用一个整型变量top来记录当前栈顶元素在数组中的位置（来自百科）。

栈结构图

空栈：top=-1代表着为空栈

空栈

顺序栈的结构

• 我们可以根据概念来设计一个栈结构

#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
{
    SElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}SqStack;

如何构建一个空栈

空栈我们只需要将栈顶指针设置为-1即可

Status InitStack(SqStack *S){
   //构建空栈
    S->top = -1;
    return OK;
}

如何将一个顺序栈置空

将栈置空,需要将顺序栈的元素都清空吗？不需要，只需要修改top标签就可以了，和构建空栈相同，只需要将top =-1。

Status ClearStack(SqStack *S){
    S->top = -1;
    return OK;
}

判断顺序栈是否为空

判断一个栈是不是空，只需要判断top是不是-1。

Status StackEmpty(SqStack S){
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}

获取栈的长度

栈的长度的获取，我们可以根据栈顶指针来计算，由于顺序栈采用的是顺序存储结构，第一个存储位置top=0开始的，所以我们可以有栈顶指针+1来计算

int StackLength(SqStack S){
    return S.top + 1;
}

获取栈顶元素

Status GetTop(SqStack S,SElemType *e){
    if (S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
   
    return OK;
    
}

插入元素e为新栈顶元素（push入栈）

先要安全判断，判断栈是否已经满了，如果已将满了返回ERROR，否则插入元素，将top++

Status PushData(SqStack *S, SElemType e){
    
    //栈已满
    if (S->top == MAXSIZE -1) {
        return ERROR;
    }
    
    //栈顶指针+1;
    S->top ++;
    //将新插入的元素赋值给栈顶空间
    S->data[S->top] = e;
    
    return OK;
}

删除S栈顶元素,并且用e带回（pop出栈）

• pop 的时候为防止意外发生，先判断是不是空栈
• 获取栈顶元素，然后返回该元素
• 将栈顶指针减1

Status Pop(SqStack *S,SElemType *e){
   
    //空栈,则返回error;
    if (S->top == -1) {
        return ERROR;
    }
    
    //将要删除的栈顶元素赋值给e
    *e = S->data[S->top];
    //栈顶指针--;
    S->top--;
    
    return OK;
}

栈的遍历

Status StackTraverse(SqStack S){
    int i = 0;
    printf("此栈中所有元素");
    while (i<=S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
    return OK;
}

总结：先入后出