【数据结构】【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)--]);
    }
}

未完待续……

上一篇:静态链表(数据结构)


下一篇:稀疏数组和队列