数据结构(三)——栈

三、栈、队列和数组

3.1 栈

3.1.1 栈的基本概念

线性表是具有相同数据类型的n（n≥0）个数据元素的有限 序列，其中n为表长，当n = 0时线 性表是一个空表。若用L命名线性表，则其一般表示为 L = (a1, a2, … , ai , ai+1, … , an)

栈（Stack）是只允许在一端进行插入或删除操作的线性表
逻辑结构：与普通线性表相同 数据的运算：插入、删除操作有区别

重要术语：栈顶、栈底、空栈
栈顶：允许插入 和删除的一端 (最后进的即最上面的为栈顶元素)
栈底：不允许插 入和删除的一端(最先进的即最下面的为栈底元素)
空栈：不含任何元素的栈

特点：后进先出(后进栈的元素先出栈)  记为LIFO (Last In First Out)

栈的基本操作

• InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
• DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
• Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
• Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
• GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素

其他常用操作

• StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false

栈的常考题型
进栈顺序为： a à b à c à d à e  有哪些合法的出栈顺序？

3.1.2 栈的顺序存储实现

顺序栈的定义：

#define MaxSize 10         //定义栈中元素的最大个数
typedef struct{    ElemType data[MaxSize];       //静态数组存放栈中元素    int top;                      //栈顶指针 用于指向此时栈中的栈顶元素 一般用来记录数组的下标
}SqStack;void testStack(){    SqStack S;       //声明一个顺序栈(分配空间)
}

顺序存储：给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType) 

初始化操作

#define MaxSize 10                 //定义栈中元素的最大个数
typedef struct{   ElemType data[MaxSize];        //静态数组存放栈中元素int top;                       //栈顶指针
}SqStack;// 初始化栈
void InitStack(SqStack &S){ S.top = -1;                   //初始化栈顶指针
}void testStack(){SqStack S;                    //声明一个顺序栈(分配空间)InitStack(S);//...后续操作...
}// 判断栈是否为空
bool StackEmpty(SqStack S){    if(S.top == -1)                //栈空return true;    else                           //不空return false;
}

进栈操作

#define MaxSize 10                    //定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize];           //静态数组存放栈中元素int top;                          //栈顶指针
}SqStack;    // 新元素进栈
bool Push(SqStack &S, ElemType x){    // 判断栈是否已满   满了报错  if(S.top == MaxSize - 1)        return false;    S.top = S.top+1;                  //指针先加1S.data[S.top]=x;                  //新元素入栈 把x存到top指针所在的位置return true;
}S.top = S.top+1;                  //指针先加1S.data[S.top]=x;                  //新元素入栈 把x存到top指针所在的位置上面两句代码等价于S.data[++S.top]=x;                //++top表示，先让top的值加1 再来使用top

 出栈操作

#define MaxSize 10                    //定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize];           //静态数组存放栈中元素int top;                          //栈顶指针
}SqStack;    // 出栈
bool Pop(SqStack &x, ElemType &x){    // 判断栈是否为空    if(S.top == -1)                   //栈空报错return false;    x = S.data[S.top--];    return true;
}x = S.data[S.top--];    等价于x=S.data[S.top];                     //栈顶元素先出栈S.top=S.top-1;                       //指针再减1top指针减1 数据还残留在内存中，指示逻辑上被删除了

栈顶指针：S.top,初始化时设置S.top=-1;栈顶元素：S.data[S.top]
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶
出栈操作：栈非空时，先取栈顶元素，再将栈顶指针减1
栈空条件：S.top==-1,栈满条件：S.top==MaxSize-1；栈长：S.top+1

读取栈顶元素

// 读栈顶元素 
bool GetTop(SqStack S, ElemType &x){        if(S.top == -1)               //栈空 报错   return false;        x = S.data[S.top];            //x记录栈顶元素 和出栈操作基本一样，唯一区别是这里top不需要-- return true; 
}

 仅为读取栈顶元素，并没有出栈操作，因此原栈顶元素依然保留在栈中
共享栈（利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间）：
将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

#define MaxSize 10                //定义栈中元素的最大个数
typedef struct{       ElemType data[MaxSize];       //静态数组存放栈中元素  int top0;                     //0号栈栈顶指针  int top1;                     //1号栈栈顶指针
}ShStack;// 初始化栈
void InitSqStack(ShStack &S){    S.top0 = -1;                  //初始化栈顶指针S.top1 = MaxSize;   
}/*仅当两个栈顶指针相邻(top1-top0=1)时，判断为栈满
0号栈进栈时top0先加1再赋值
1号栈进栈时top1先减1再赋值
出栈时则相反*/

栈满的条件：top0 + 1 == top1

共享栈是为了更有效地利用存储空间，两个栈的空间相互调剂，只有在整个存储空间被占满时才发生上溢，其存取数据的时间复杂度为O(1)，所以对存取效率没有什么影响

3.1.3 栈的链式存储实现

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况，通常采用单链表实现，并规定所有操作都是在单链表的表头进行的

链栈的定义 和单链表的定义几乎没差别

typedef struct Linknode{        ElemType data;        //数据域    Linknode *next;       //指针域
}*LiStack;void testStack(){   LiStack L;            //声明一个链栈
}

采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链的表头进行。需要注意的是，对于带头结点和不带头结点的链栈，具体的实现会有所不同。

链栈的初始化

typedef struct Linknode{       ElemType data;      Linknode *next;
}*LiStack;// 初始化栈
bool InitStack(LiStack &L){    L = (Linknode *)malloc(sizeof(Linknode));   if(L == NULL)             return false;   L->next = NULL;    return true;
}// 判断栈是否为空
bool isEmpty(LiStack &L){    if(L->next == NULL)      return true;   else           return false;
}

入栈出栈

// 新元素入栈
bool pushStack(LiStack &L,ElemType e){  Linknode *s = (Linknode *)malloc(sizeof(Linknode));  if(s == NULL)               //内存分配失败 return false;   s->data = e;                //用结点s保存数据元素es->next = L->next;          //头插法      L->next = s;                //把s结点连到L后return true;
}// 出栈
bool popStack(LiStack &L, int &e){     if(L->next == NULL)         // 栈空不能出栈  return false;    Linknode *s = L->next;  x = s->data;       L->next = s->next;free(s);       return true;
}