数据结构——堆栈

概念

• 插入数据：入栈（Push）

• 删除数据：出栈（Pop）

• 后入先出：Last In First Out（LIFO）

主要操作

储存结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

入栈

#define MaxSize <最大元素个数>
struct SNode{
   ElementType Data[MaxSize];  
    int Top;
};
void Push(SNode* PtrTop,Element item)
{
    if(PtrTop->Top==MaxSize-1){
        cout << "堆栈满";
        return ;
    }else{
        PtrTop->Data[++(PtrTop->Top)]=item;
        return ;
    }
}

出栈

ElementType Pop(SNode* PtrTop)
{
	if(PtrTop=-1){
        cout << "栈为空";
        return ;
    }
    else 
        return (PtrTop->Data[PtrTop->Top--]);
}

链表实现堆栈

栈的链式存储结构实际上是一个单链表，叫做链栈。

Top在链表头上。

struct SNode
{
	ElementType Data;
    SNode* next;
};
//构建一个堆栈的头结点，返回指针
SNode* CreateStack()
{
    SNode *PtrTop;
    PtrTop=(SNode*)new SNode;
    PtrTop->next=NULL;
    return PtrTop;
}
//判断堆栈是否为空
SNode* IsEmpty(SNode PtrTop)
{
    return (PtrTop->next == NULL);
}

入栈

void Push(ElementType item,SNode* PtrTop)
{
    SNode* p;
    p=(SNode*)new SNode;
    p->next=PtrTop->next;
    p->Data=item;
    PtrTop->next=p;
}

出栈

ElemtType Pop(SNode* PtrTop)
{
    SNode* FirstCell;
    ElementType TopElem;
    if(IsEmpty(PtrTop)){
        cout << "堆栈为空";
        return NULL;
    }else{
        FirstCell=PtrTop->Next;
        PtrTop->next=FirstCell->next;
        TopElem = FirstCell->Data;
        delete FirstCell;
        return TopElem;
    }
}