引子 – 栈逻辑结构

栈依然是元素一个前驱，一个后继，典型的线性结构。
但是呢在操作上有了限制，插入删除只能从一端进行（后进先出LIFO），就像洗碗时叠的盘子，叠的时候从下往上，洗的时候从上往下（只能在上面一端出）。别说抽出来一个洗呐，小心砸碎。

n个不同元素进栈，出栈元素的不同排列个数为 1/(n + 1) * C(n,2n)。（阿Q推不出来）

栈的基本操作有：

• 创建 InitStack(&S)
• 判空 StackEmpty(S)
• 判满 StackFull(S)
• 获取栈顶元素 GetTop(S,&x)
• 清空栈 StackClear(&S)
• 销毁栈 DestroyStack(&S)
• 进栈 Push(&S,x)
• 出栈 Pop(&S,&x)

顺序栈

用数组来存咯，只不过要用到栈顶指针（可以用真的指针，也可以用逻辑上的指针i）

逻辑指针（静态分配）

存储类型表示

#define ElemType int
// typedef int ElemType;
// 顺序栈（逻辑指针）
#define MaxSize 50

typedef struct
{
    /* data */
    ElemType data[MaxSize];
    int top;
}SqStack;

操作

// C语言实现
#include<stdbool.h> // bool类型在这个头文件里
// 栈：顺序栈、链栈、共享栈
#define ElemType int
// typedef int ElemType;
// 顺序栈（逻辑指针）
#define MaxSize 50

typedef struct
{
    /* data */
    ElemType data[MaxSize];
    int top;
}SqStack;

// 该存储结构下的操作，分为 top从-1 / 0 开始，以下均为从0开始
void InitStack(SqStack *S) // 注意此处无法 SqStack &S,因为只要C++才有引用传递
{
    S->top = 0;
}

bool StackEmpty(SqStack S)
{
    return S.top == 0;
}

bool GetTop(SqStack S,ElemType *x)
{
    if(StackEmpty(S)) return false;
    *x = S.data[S.top - 1];  // 切记：此处top指向的栈顶元素的下一个
    return true;
}

void StackClear(SqStack S)
{
    // 逻辑上的情况即可。和创建栈一样
    S.top = 0;
}

void DestroyStack(SqStack *S)
{
    // 该部分 data[MaxSize]是静态存储，由系统自动释放，则无需操作
}

bool Push(SqStack *S, ElemType x)
{
    if(S->top == MaxSize) return false; //栈满
    S->data[S->top++] = x;  // 注意此处top从0开始（指向栈顶元素的上一个空间）
    return true;
}

bool Pop(SqStack *S, ElemType *x)
{
    if(StackEmpty(*S)) return false;
    *x = S->data[--S->top];
    return true; 
}

测试

int main(){
    SqStack S;
    InitStack(&S);
    Push(&S,1);
    Push(&S,2);
    Push(&S,3);
    Push(&S,4);
    Push(&S,5);
    int x;
    while(!StackEmpty(S))
    {
        Pop(&S,&x);
        printf("%d",x);
    }
    return 0;
}
/*
输出结果为：
54321
*/

阿Q感慨：C语言这也太麻烦了，C++有了引用传递后代码更好读。

咱们用C++快速实现以下（之后还是先用C，毕竟用了才知道C和C++区别还是不小的）

// C++完成
// C++ bool类型自带
typedef int ElemType;
// 顺序栈（逻辑指针）
#define MaxSize 50

typedef struct
{
    /* data */
    ElemType data[MaxSize];
    int top;
}SqStack;

// 该存储结构下的操作，分为 top从-1 / 0 开始，以下均为从0开始
void InitStack(SqStack &S)
{
    S.top = 0;
}

bool StackEmpty(SqStack S)
{
    return S.top == 0;
}

bool GetTop(SqStack S,ElemType &x)
{
    if(StackEmpty(S)) return false;
    x = S.data[S.top - 1];
    return true;
}

void StackClear(SqStack S)
{
    // 逻辑上的情况即可。和创建栈一样
    S.top = 0;
}

void DestroyStack(SqStack &S)
{
    // 该部分 data[MaxSize]是静态存储，由系统自动释放，则无需操作
}

bool Push(SqStack &S, ElemType x)
{
    if(S.top == MaxSize) return false; //栈满
    S.data[S.top++] = x;  // 注意此处top从0开始（指向栈顶元素的上一个空间）
    return true;
}

bool Pop(SqStack &S, ElemType &x)
{
    if(StackEmpty(S)) return false;
    x = S.data[--S.top];
    return true; 
}

真实指针 （动态分配）

存储类型表示

#define ElemType int

typedef struct
{
    /* data */
    ElemType *base; // 栈底指针，用于动态开扩空间
    ElemType *top;  // 栈顶指针，指向栈顶
    int StackSize;  // 可开扩的最大空间
}SqStack;

操作

// 此处直接用C++来写了
// 顺序栈（真实指针)
#include<cstdlib>
#define OVERFLOW -1 // exit状态码
#define MaxSize 50
#define ElemType int

typedef struct
{
    /* data */
    ElemType *base; // 栈底指针，用于动态开扩空间
    ElemType *top;  // 栈顶指针，指向栈顶
    int StackSize;  // 可开扩的最大空间
}SqStack;

bool InitStack(SqStack &S)
{
    // 需要动态分配空间了
    S.base = new ElemType[MaxSize];
    // c语言版：S.base = (ElemType *)malloc(MaxSize * sizeof(ElemType));
    // 判断是否分配成功
    if(!S.base) exit(OVERFLOW);
    S.top = S.base;
    S.StackSize = MaxSize;
    return true;
}

bool StackEmpty(SqStack S)
{
    // 逻辑上 类似于 顺序指针 top从0开始
    return S.top == S.base;
}

bool StackFull(SqStack S)
{
    return (S.top - S.base) == MaxSize;
    // 此处 S.top - S.base 则为当前数组中存的元素个数
}

bool GetTop(SqStack S, ElemType &x)
{
    if(StackEmpty(S)) return false;
    x = *(S.top - 1);
    return true;
}

void StackClear(SqStack &S)
{
    S.top = S.base;
}

void DestroyStack(SqStack &S)
{
    if(S.base){
        // 释放动态分配的空间
        delete S.base;
        // 要注意将 base和 top指针指向空，不然变成野指针了
        S.StackSize = 0;
        S.base = S.top = NULL;
    }
}

bool Push(SqStack &S, ElemType x)
{
    if(StackFull(S)) return false;
    *S.top++ = x;
    return true;
}

bool Pop(SqStack &S, ElemType &x)
{
    if(StackEmpty(S)) return false;
    x = *--S.top;
    return true;
}

共享栈

两个栈放在一起存了，要维护两个栈顶指针（一个是从右往左，一个是从左往右）

存储类型表示（建议用顺序栈存）

当然可以用链栈来存，但不合适，这种主要就是节省空间，两个栈放一块（空间给大点），也减少了任意一个栈上溢的风险。而链栈压根没这上溢顾虑，再拿链栈来存共享栈，阿Q觉得是脱裤子放屁。

// 阿Q只写静态存储（逻辑指针）的共享栈了 - 懒
#define ShareStackSize 100
typedef int Elemtype;

typedef struct
{
    /* data */
    Elemtype data[ShareStackSize];
    int top[2]; // top[0] - 从右往左;  top[1] - 从左往右
}ShareStack;

操作

// #include<cstdlib>
#define ShareStackSize 100
typedef int Elemtype;

typedef struct
{
    /* data */
    Elemtype data[ShareStackSize];
    int top[2]; // top[0] - 从右往左;  top[1] - 从左往右
}ShareStack;

void InitStack(ShareStack &SS)
{
    SS.top[0] = -1;  // 写一次 top 从 -1 开始
    SS.top[1] = ShareStackSize; // 那么接下来那个就是从 MaxSize 开始咯
}

// 对接下来的操作都要设定一个操作数，0 - 表示对 top[0]这边操作， 1 - 表示对 top[1]这边操作
bool StackEmpty(int operate, ShareStack SS)
{
    switch (operate)
    {
    case 0: return SS.top[0] == -1; break;
    case 1: return SS.top[1] == ShareStackSize; break;
    default:
        return false;
        /*
        激进做法（不推荐）
            exit(-1);  // -1状态码就说明操作数输错了
        */
    }
}

bool StackFull(ShareStack SS)
{
    return (SS.top[1] - SS.top[0] == 1); // 若此时 top1就在 top0的右侧，那说明塞不下啦
}

bool GetTop(int operate, ShareStack SS, Elemtype &x)
{
    if(operate < 0 || operate > 1) exit(-1);
    if(StackEmpty(operate,SS)) return false;
    x = SS.data[SS.top[operate]];
    return true;
}

void StackClear(ShareStack &SS)
{
    SS.top[0] = -1;
    SS.top[1] = ShareStackSize;
}

bool Push(int operate, ShareStack &SS, Elemtype x)
{
    if(StackFull(SS)) return false;
    switch (operate)
    {
    case 0:
        /* code */
        SS.data[++SS.top[0]] = x;
        break;
    case 1:
        SS.data[--SS.top[1]] = x;
        break;
    default:
        return false;
    }
    return true;
}

bool Pop(int operate, ShareStack &SS, Elemtype &x)
{
    if(StackEmpty(operate,SS)) return false;
    switch (operate)
    {
    case 0:
        /* code */
        x = SS.data[SS.top[0]--];
        break;
    case 1:
        x = SS.data[SS.top[1]++];
        break;
    // default:
    //     return false;  此处就不需要了，因为 operate错误已经在 StackEmpty条件中
    }
    return true;
}

阿Q感觉没必要这样做吧，分成两个栈分别操作不好嘛。

链栈

阿Q：链式存储有很多（单链表、双链表、循环链表），也可以用这些来存栈。

此处呢为了简单，阿Q选择单链表。那么是怎样一种单链表可以表示为栈呢？最简单的当然是只有头指针的链表，此时存储可以用下图表示：

存储类型表示

typedef int ElemType;

typedef struct LinkNode
{
    /* data */
    ElemType data;
    struct LinkNode *next;
}LinkNode,*LiStack;

// 头指针确定整个链表

操作

阿Q注：头指针分配的是静态空间（指针）；链表的操作结点都需要动态开辟空间，不然导致栈中（栈区）的节点在函数返回后失效（悬空指针）

在Push中存放了这方面的错误代码（详情见C++一览中的内存分配模型）

// C头文件 NULL
// #include<stdio.h>
// #include<stdlib.h>
// C++头文件
#include<cstdlib>

void InitStack(LiStack &L)
{
    L = NULL;
}

bool StackEmpty(LiStack L)
{
    return L == NULL;
}

bool GetTop(LiStack &L, ElemType &x)
{
    if(StackEmpty(L)) return false;
    x = L->data;
    return true;
}


void StackClear(LiStack &L)
{
    LiStack tmp;
    tmp = L;
    while(!StackEmpty(L)){
        L= tmp->next;
        delete tmp;
        tmp = L;
    }
    // L = NULL;
}

// 由于头指针是静态分配的，因此销毁操作只需要清空链表，然后头指针由系统自动释放

bool Push(LiStack &L, ElemType x)
{
    /*
    错误代码：
        LinkNode node;
        node.data = x;
        node.next = L;
        L = &node;
    
    阿Q注：它使用局部变量 node，导致栈中的节点在函数返回后失效（悬空指针）
    */ 
   // 必须要动态分配，这样才能由自己手动释放
   LinkNode *node = new LinkNode;
   if(!node) return false; 
   node->data = x;
   node->next = L;
   L = node;
   return true;
}

bool Pop(LiStack &L, ElemType &x)
{
    if(StackEmpty(L)) return false;
    LinkNode *tmp;
    tmp = L;
    L = tmp->next;
    x = tmp->data;
    delete tmp; // 结点均为动态开辟的，所以需要释放
    return true;
}

题目

非算法题

算法题

1、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假设被判定的操作序列已存入一维数组中）。

方法一：用栈的逻辑，但不使用栈的具体结构

bool legal(char Operate[])
{
    int i = 0; // 数组下标
    int Input = 0, Output = 0; // 记录出入栈的次数
    while(Operate[i] != '\0')  // 系统会对字符串型自动添加串尾标识符
    {
        switch (Operate[i])
        {
        case 'I':
            /* code */
            Input++;
            break;
        case 'O':
            Output++;
            break;
        default:
            return false;  // 操作序列本身就有误
            break;
        }
        if(Output > Input) return false;  // 出栈次数 > 入栈次数  不合法
        i++;
    }
    if(Output != Input) return false; // 终态栈不为空
    return true;
}

测试

int main(){
    char *operate = (char*)"IIIOIOIO";  // 此处需要强制类型转换
    bool l = legal(operate);
    std::cout << (l == 1? "yes":"no") << std::endl;  // <<运算符的优先级高于三元运算符
    return 0;
}

方法二 直接使用栈

bool legal_with_stack(char operate[])
{
    SqStack S;
    InitStack(S);
    int i = 0;
    char tmp;
    while(operate[i] != '\0')
    {
        if(operate[i] == 'I') Push(S,'I');
        else if(!Pop(S,tmp)) return false;
        i++;
    }
    if(!StackEmpty(S)) return false;
    return true;
}

阿Q：有时候写有关栈算法，不一定需要使用具体的栈结构。

---

2、设单链表的表头指针为L，结点由data和next两个域组成，其中data为字符型，设计算法判断该链表的全部n个字符是否中心对称，如：xyx，xyyx都是中心对称。

阿Q最先想到的是将单链表遍历一遍，元素分别存入栈和队列中，然后再依次取出进行对比（好笨重的方法）

若关于中心对称，那么将 n/2个元素入栈即可，然后再出栈和 剩余 n/2个 元素 逐一匹配即可。（可以不用具体的栈的结构）

另外此题需要区分 头指针（指向第一个链表元素，静态分配）和 头结点（特殊的结点，结点内不存值，动态分配）

bool symm(LinkList L, int n)
{
    LinkList tmp = L;
    char s[n/2];  // 前 n/2 个元素存入
    int i = 0;    // 栈顶指针(逻辑上)
    // 入栈操作
    while(i < n/2)
    {
        s[i] = tmp->data;
        tmp = tmp->next;
        i++;
    }

    i--; // 此时已经越界 - 指向栈顶元素的上一个位置了哦（容易错）

    // 当 n 为奇数 , n / 2 + 1 就直接跳过
    if(n%2 == 1) tmp = tmp->next;

    // 出栈 和 后续的 n/2 个元素 逐一匹配
    while(i > -1)
    {
        if(s[i] != tmp->data) return false;  // 不匹配即不对称
        i--;
        tmp = tmp->next;
    }
    return true;
}