【数据结构】栈和队列之栈各种操作

栈的定义

栈实际上也是线性表，只不过是一种特殊的线性表。其特殊性在于栈的基本操作是线性表操作的子集，他们的操作受限于线性表，可称为限定性的数据结构。

栈(stack)是限定仅在表尾进行插入和删除操作的线性表，它是一种后进先出(Last in First out ,LIFO)的线性表

栈的特性

• 允许插入和删除的一段称为栈顶(top)，另外一段称为栈底(bottom)。
• 不含任何数据元素的栈称为空栈。
• 栈的元素必须后进先出。

栈的操作

• 插入操作
  栈的插入操作(Push)，叫做进栈，也称压栈、入栈。
  进栈
• 删除操作
  栈的删除操作(Pop)，叫做出栈，也称弹栈。
  出栈

---

栈的顺序存储结构及实现

栈的本质是一个线性表，线性表有两种存储形式，栈也分为栈的顺序存储结构和栈的链式存储结构

在操作栈的时候，栈会有三种情况：栈普通情况、空栈、栈满。

栈的三种情况

定义一个顺序顺序存储结构

#include <stdio.h>
#include <stdlib.h>
#define OK 1;
#define ERROR 0;
#define TRUE 1;
#define FALSE 0;
#define STACK_INIT_SIZE 100  /* 初始化栈空间为 100 */
#define STACKINCREMENT 10

typedef int Status; /*Status是函数的类型，其值是函数结果状态码，如OK等*/
typedef int  ElemType;

typedef struct {
    
    ElemType * base;    /* 指向栈底的指针变量 */
    ElemType * top;     /* 指向栈顶的指针变量 */
    int stackSize;      /* 栈的当前可使用的最大容量 */
    
}sqStack;

也可以这样声明

typedef struct {
    
    ElemType data[MAXSIZE];
    int top;            /* 用于标注栈顶的位置 */
    int stackSize;      /* 栈的当前可使用的最大容量 */
}sqStack;

创建一个顺序顺序存储结构的栈

#define STACK_INIT_SIZE 100  /* 初始化栈空间为 100 */
/**
 * 创建栈
 */
void initStack(sqStack *s){
    
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!s->base) exit(0);
    
    s->top = s->base;   /* 最开始，栈顶就是栈底 */
    s->stackSize = STACK_INIT_SIZE;
}

一、入栈操作

/**
 * 入栈操作
 */
Status Push(sqStack * s, ElemType e){
    
    if (s->top - s->base >= s->stackSize) {  //栈满 ，追加空间
        
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        
        if (!s->base) exit(0);
        
        s->top = s->base + s->stackSize;  // 设置栈顶
        s->stackSize = s->stackSize + STACKINCREMENT;  // 设置栈的最大容量
    }
    
    *(s->top) = e;  // 元素e入栈，赋值到栈顶空间
    s->top++;       // 栈顶指针增加1

    return OK;
}

二、出栈操作

/**
 * 出栈操作（删除栈S的栈顶元素，用e返回其值）
 */
Status Pop(sqStack * s, ElemType *e){
    
    if (s->top == s->base) // 栈空
        return ERROR;
    
    s->top--;        // 栈顶指针减1
    *e = *(s->top);  // 将要删除的栈顶元素赋值给e
//    *e = *--(s->top);
    return OK;
}

三、清空栈

清空一个栈，就是将栈中的元素全部作废，但是栈本身物理空间并不发生变化。这里的方式定义的栈，只需要将s->top = s->base;即可实现栈的清空。

/**
 * 清空一个栈(将栈中的元素全部作废，栈本身的物理空间并不发生变化)
 */
Status ClearStack(sqStack *s){
    s->top = s->base;
    return OK;
}

四、销毁栈

销毁一个栈和释放一个栈不同，销毁一个栈是要释放该栈所占据的物理内存空间。

/**
 * 销毁栈(释放该栈锁占据的物理内存空间)
 */
Status DestoryStack(sqStack * s){
    
    int i,len;
    len = s->stackSize;   // 获取栈容量
    
    for (i = 0; i < len; i++) {
        free(s->base);
        s->base++;
    }
    
    s->base = s->top = NULL;
    s->stackSize = 0;
    
    return OK;
}

五、计算栈的当前容量

计算栈的当前容量也就是计算栈中元素的个数，在这里只需要返回即可

/**
 * 计算栈的当前容量
 */
int StackLen(sqStack s){
    
    return (s.top - s.base);
}