基本特点

• 后进先出（Last In First Out）
• 只在栈顶进行插入和删除等操作

栈的基本数据结构（顺序栈）

struct stack
{
    int *base;//尾指针，指向栈底
    int *top;//头指针，一般指向栈顶上一个元素
    int stacksize;//栈的最大容量
};

制作栈

void InitStack(struct Stack *S,int maxsize)
{
    S->base=new int[maxsize];//给栈开辟空间
    S->top=S->base;//置空栈
    S->stacksize=maxsize;
}

栈的基本操作

入栈

//入栈
void Push (struct Stack *S,int n)
{
    if(S->top-S->base==S->stacksize)
    {
        cout<<"NO"<<endl;
        return;
    }
    *S->top=n;//top是指针，赋值时候需要加上*
     S->top++;//此时是指针操作，不需要加*
}

出栈

//出栈
int Pop(struct Stack *S)
{
    if(S->top==S->base)
    {
        cout<<"NO"<<endl;
        return -1;
    }
    S->top--;//top指针指向实际顶部元素
    return *S->top;
}

查询栈顶元素

int Search(struct stack *S)
{
    if(S->top==S->base)
    {
        return -1;
    }
    int e;
    S->top--;
    e=*S->top++;
    return e;
}

销毁

void delete_stack(struct stack *S,int maxsize)
{
        free(S->base);
        S->stacksize=0;
        S->base=S->top=NULL;
}

显示栈内所有元素

void showStack (struct Stack * S)
{
    int a =S->top-S->base;
    int i;
    for (i=0;i<a;i++)
    {
       cout<<S->base<<" ";
        S->base++;
    }
    cout<<endl;
}

练习

SUDTOJ 题目链接 >

栈的基本操作