【数据结构】【C++】堆栈的实现与应用

堆栈（Stack）

参考浙大版《数据结构（第2版）》

• 堆栈可以认为是具有一定约束的线性表，插入和删除的操作都在栈顶的位置，先进入的元素将在后进入的元素之后取出，与生活中的桶类似，故又称为后入先出(Last In First Out,LIFO)表。

  非STL的堆栈实现：

• 手写的堆栈主要有以下几种基本操作：

  • Stack CreateStack(int MaxSize):生成空堆栈，其最大长度为MaxSize；
  • bool IsFull(Stack S):判断堆栈S是否已满。若S中的元素个数等于MaxSize则返回true，否则返回false；
  • bool Push(Stack S, ElememtType X):将元素X压入堆栈。若堆栈已满，返回false；否则将元素X插入到堆栈S栈顶处并返回true；
  • bool IsEmpty(Stack S):判断堆栈S是否为空，若是返回true；否则返回false；
  • ElementType Pop(Stack S):删除并返回栈顶元素，若堆栈为空则返回错误信息；

  堆栈的顺序储存实现

• 顺序栈类型定义如下(以整数为例)：

typedef int ElementType;
typedef int Position;
typedef struct SNode * Stack;
struct SNode
{
    ElementType * Date;
    Position Top;
    int MaxSize;
};

• 顺序栈以上操作的代码实现：

//生成空堆栈
Stack CreateStack(int MaxSize)
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S ->Date = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S ->Top = -1;
    S ->MaxSize = MaxSize;
    return S;
}

//判断堆栈是否已满
bool IsFull(Stack S)
{
    return (S ->Top == S ->MaxSize);
}

//圧栈操作
bool Push(Stack S, ElementType x)
{
    if(IsFull(S)) return 0;
    else 
    {
        S ->Date[++(S ->Top)] = x;
        return 1;
    }
}

//判断堆栈是否为空
bool IsEmpty(Stack S)
{
    return (S ->Top == -1);
}

//弹出栈操作
ElementType Pop(Stack S)
{
    if(IsEmpty(S)) return ERROR;
    else 
    {
        return (S ->Date[(S ->Top)--]);
    }
}

未完待续……