一、什么是堆栈(Stack)

堆栈是具有一定操作约束的线性表。
只在一端(栈顶, Top)做插入(入栈、PUSH)、删除(出栈、POP)。
后入先出：Last In First OUT (LIFO)。

二、堆栈的抽象数据类型描述

数据对象集: 一个有0个或多个元素的有穷线性表。
操作集: 长度为MaxSize的堆栈 $S\in Stack$ ,堆栈元素 $item\in ElementType$

操作	含义
Stack CreateStack(int MaxSize)	生成长度为MaxSize的空堆栈
int IsFull(Stack S,int MaxSIze)	判断堆栈S是否已满
void Push(Stack S,ElementType item)	将元素item压入堆栈
int IsEmpty(Stack S)	判断堆栈S是否为空
ElementType Pop(Stack S)	删除并返回栈顶元素

三、栈的顺序存储实现

顺序栈通常由一个一维数组和一个记录栈顶元素位置的变量组成。

#ifndef SEQSTACK_H
#define SEQSTACK_H
typedef int DataType;

const int  MaxSize = 100;

class SeqStack
{
public: 
    SeqStack() { top = -1; };       //生成长度为MaxSize的空堆栈
    int IsFull();                   //判断堆栈S是否已满
    void Push(DataType item);       //将元素item压入堆栈
    int IsEmpty();                  //判断堆栈S是否为空
    DataType Pop();                 //删除并返回栈顶元素
private:
    DataType data[MaxSize];         //定义数组
    int top;                        //定义栈顶
};

#endif

#include <iostream>
#include "stack.h"

using namespace std;

void SeqStack::Push(DataType item)
{
    //将元素item压入堆栈
    if (top == MaxSize - 1) {
        printf("Stack is full!");
        return;
    }
    else {
        data[++top] = item;
        return;
    }
}

DataType SeqStack::Pop()
{
    //删除并返回栈顶元素
    if (top == -1){
        printf("Stack is empty");
        return 0;
    }
    else {
        return top--;
    }
};

int SeqStack::IsFull()
{
    //判断堆栈S是否已满
    return (top == MaxSize-1);
}

int SeqStack::IsEmpty()
{
    //判断堆栈S是否为空
    return top == -1;
}

四、堆栈的链式存储实现

使用一个单链表实现。
插入和删除在栈顶进行。

#ifndef SEQSTACK_H
#define SEQSTACK_H
typedef int DataType;

typedef struct Node
{
    // 定义数据结构
    DataType data;
    Node* next;
};

class SeqStack
{
public:
    SeqStack() { top->next = nullptr; };                  //构造函数
    void Push(DataType item);       //将元素item压入堆栈
    int IsEmpty();                  //判断堆栈S是否为空
    DataType Pop();                 //删除并返回栈顶元素
private:
    Node* top = new Node;
};

#endif

#include <iostream>
#include "stack.h"

using namespace std;

int SeqStack::IsEmpty()
{
    //判断堆栈S是否为空
    return top->next == nullptr;
}

void SeqStack::Push(DataType item)
{
    //将元素item压入堆栈
    Node* p=new Node;
    p->data=item;
    p->next = top->next;
    top->next = p;
}

DataType SeqStack::Pop()
{
    //删除并返回栈顶元素
    Node* new_top;
    DataType x;
    
    if (IsEmpty()) {
        printf("Stack is empty");
        return 0;
    }
    else {
        new_top = top->next;
        x = new_top->data;
        top->next = new_top->next;
        delete new_top;
        return(x);
    }
};

本文作者：大师兄(superkmi)