顺序栈

栈

1.栈是限定仅在表尾（栈顶）进行插入和删除操作的线性表
2.允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈
3.栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构
4.它的特殊之处就在于限制了这个线性表的插入和删除位置，始终只在栈顶进行，这就使得：栈顶是固定的，最先进栈的只能在栈底
5.栈的插入操作，叫做进栈，也称压栈、入栈。栈的删除操作叫做出栈或者弹栈
栈模型如下图所示：

栈

顺序栈

顺序栈的表示和实现：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。
1.附设top指针，指示栈顶元素在顺序栈中的位置，但是为了方便操作，通常top指示真正的栈顶元素之上的下标地址
2.附设base指针，指示栈底元素在顺序栈中的位置
3.另外，用stacksize表示栈可使用的最大容量
如下图所示：

顺序栈

stack.h

#pragma once
#define MAXSIZE 20
// 函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
//数据类型
typedef int SElemType;

typedef struct
{
    SElemType* base;    //栈底指针
    SElemType* top;     //栈顶指针
    int stacksize;      //栈可用最大容量
}SqStack;

//顺序栈初始化（构造一个空栈）
Status InitStack(SqStack& S);

//判断顺序栈是否为空
bool StackEmpty(SqStack S);

//求顺序栈长度
int StackLength(SqStack S);

//清空顺序栈
Status ClearStack(SqStack& S);

//销毁顺序栈
Status DestroyStack(SqStack& S);

//顺序栈入栈
Status Push(SqStack& S, SElemType e);

//顺序栈出栈
Status Pop(SqStack& S, SElemType& e);

//遍历顺序栈
void StackTraverse(SqStack S);

stack.cpp

空栈和栈满的情况如下图所示：

空栈和栈满
在这两种情况下，如果执行某些操作，可能会发生错误，如下：
下溢（overflow）:栈空，还要弹出元素
上溢（overflow）:栈满，还要压入元素
上溢是一种错误，使得问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束

#include "stack.h"
#include <iostream>
using namespace std;

//顺序栈初始化（构造一个空栈）
Status InitStack(SqStack& S)
{
    S.base = new SElemType[MAXSIZE];
    if (!S.base)
    {
        exit(OVERFLOW);                 //存储分配失败
    }
    S.top = S.base;                     //栈顶指针等于栈底指针
    S.stacksize = MAXSIZE;
    return OK;
}

//判断顺序栈是否为空
bool StackEmpty(SqStack S)
{
    if (!S.base)
    {
        cout << "栈不存在" << endl;
        exit(OVERFLOW);
    }
    if (S.top == S.base)
        return true;
    else
        return false;
}

//求顺序栈长度
int StackLength(SqStack S)
{
    if (!S.base)
    {
        cout << "栈不存在" << endl;
        return 0;
    }
    return S.top - S.base;
}

//清空顺序栈(逻辑清空)
Status ClearStack(SqStack& S)
{
    if (!S.base)
    {
        cout << "栈不存在" << endl;
        return ERROR;
    }
    S.top = S.base;
    S.stacksize = 0;
    cout << "已清空" << endl;
    return OK;
}

//销毁顺序栈
Status DestroyStack(SqStack& S)
{
    if (S.base)
    {
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
        cout << "已销毁" << endl;
    }
    return OK;
}

//顺序栈入栈
Status Push(SqStack& S, SElemType e)
{
    if (S.stacksize == StackLength(S))
    {
        cout << "栈满" << endl;
        return ERROR;
    }
    else if (!S.top)
    {
        cout << "栈不存在" << endl;
        return ERROR;
    }
    else
    {
        *S.top = e;
        S.top++;
        return OK;
    }
}

//顺序栈出栈
Status Pop(SqStack& S, SElemType& e)
{
    if (StackEmpty(S) | !S.top)
    {
        cout << "栈为空或者不存在" << endl;
        return ERROR;
    }
    S.top--;
    e = *(S.top);
    return OK;
}

//遍历顺序栈
void StackTraverse(SqStack S)
{
    SElemType* p = S.base;      //p指向栈底
    while (p != S.top)          
    {
        cout << *p++ << " ";
    }
    cout << endl;
}

main.cpp

测试：

#include <iostream>
#include "stack.h"
using namespace std;

int main(int argc, char** argv)
{
    SqStack S;
    InitStack(S);       //初始化栈

    Push(S, 1);         //入栈
    Push(S, 2);
    Push(S, 3);

    StackTraverse(S);   //遍历栈

    cout << "栈的长度为：" << StackLength(S) << endl;

    SElemType e;
    Pop(S, e);          //出栈
    cout << "出栈的元素为：" << e << endl;

    StackTraverse(S);   //遍历

    return 0;
}