栈的顺序和链式的表示和实现

栈是一种只能在一端进行删除和插入操作的线性表，栈的主要特点是“先进后出”。

顺序栈：分配一块连续的存储区域存放栈中元素，并用一个变量指向当前的栈顶。

#include <stdio.h>
#define MAXSIZE 50

typedef int elemType;

typedef struct{
    elemType data[MAXSIZE];
    int top;
}SqStack;

//初始化栈 
void init(SqStack &stk){
    stk.top=-1;
}

//判断栈是否为空 
bool stackEmpty(SqStack stk){
    return stk.top==-1;
}

//入栈 
int push(SqStack &stk,elemType e){
    if(stk.top==MAXSIZE-1)
        return 0;
    stk.top++;
    stk.data[stk.top]=e;
    return 1;
}

//出栈 
int pop(SqStack &stk,elemType &x){
    if(stk.top==-1)
        return 0;
    x=stk.data[stk.top];
    stk.top--;
    return 1;
}

//取栈顶元素
int getTop(SqStack stk,elemType &x){
    if(stk.top==-1)
        return 0;
    x=stk.data[stk.top];
    return 1;
} 

链栈：采用链式存储结构存储栈，栈的所有操作都是在单链表的表头进行的。

typedef int elemType;
typedef struct linknode{
    elemType data;
    struct linknode *next;
}*LStack;

//初始化  带头节点的链栈 
void init(LStack &stk){
    stk=(linknode*)malloc(sizeof(linknode));
    stk->next=NULL;
}

//判断是否为空 
int isEmpty(LStack stk){
    return stk->next==NULL;
}

//入栈
int push(LStack &stk,elemType e){
    linknode *node = (linknode*)malloc(sizeof(linknode));
    if(node==NULL)
        return 0;
    node->data=e;
    node->next=stk->next;
    stk->next=node;
    return 1;
} 

//出栈
int pop(LStack &stk,elemType &x){
    if(stk->next==NULL)
        return 0;
    linknode *node = stk->next;
    x=node->data;
    stk->next=node->next;
    free(node);
    return 1;
} 

//获取栈顶元素
int getTop(LStack stk,elemType &x){
    if(stk->next==NULL)
        return 0;
    x=stk->next->data;
    return 1;
} 

//清空栈中元素
void clear(LStack &stk){
    linknode *node = stk->next;
    while(node!=NULL){
        stk->next=node->next;
        free(node);
        node=stk->next;
    }
}