3.1 栈

栈（stack）是一种遵循先入后出逻辑的线性数据结构。

我们可以将栈类比为桌面上的一摞盘子，如果想取出底部的盘子，则需要先将上面的盘子依次移走。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构。

如图 3-1-1 所示，我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。

3.1.1 栈的实现

依据栈的存储方式不同,栈的实现方式大致上可以分为两种:

用顺序存储方式实现的栈 -- 顺序栈
用链式存储方式实现的栈 -- 链栈

顺序栈的实现

/* 顺序栈的定义 */
#define MaxSize 10              //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];     //静态数组存放栈中元素
    int top;                    //栈顶指针
}SqStack;

顺序栈实现常用操作

栈的常用操作如表 3-1 所示，具体的方法名需要根据所使用的编程语言来确定。在此，我们以常见的 push()、pop()、peek() 命名为例。

表 3-1 栈的操作效率

方法	描述	时间复杂度
`push()`	元素入栈（添加至栈顶）	O(1)
`pop()`	栈顶元素出栈	O(1)
`peek()`	访问栈顶元素	O(1)

初始化顺序栈入栈操作出栈操作读栈顶元素

/* 初始化顺序栈 */
void InitStack(SqStack *s){
    s->top = -1;             //初始化栈顶指针
}

/* 新元素入栈 */
bool Push(SqStack *S,ElemType x){
    if(S.top == MaxSize - 1)        //栈满，报错
        return false;
    S.top = S.top + 1;              //指针先加1
    S.data[S.top] = x;              //新元素入栈
    /*可以将以上两行合并成一行
    S.data[++S.top] = x;
    */
    return true;
}

/* 入栈操作 */
bool Pop(SqStack *S,ElemType &x){   //删除的元素需要返回查看，所以x形参传地址
    if(S.top == -1)                 //栈空，报错
        return false;
    x = S.data[S.top];              //先出栈
    S.top = S.top - 1;              //指针再减1
    /*可以将以上两行合并成一行
    x = S.data[S.top--];
    */
    return true;
}

/* 读栈顶元素 */
bool GetTop(SqStack S,ElemType &x){   
    if(S.top == -1)                 //栈空，报错
        return false;
    x = S.data[S.top];              //x记录栈顶元素
    return true;
}

3.1 栈

3.1.1 栈的实现

顺序栈的实现

顺序栈实现常用操作

评论