鏈棧的c語言實現

1.鏈棧結構

typedef struct StackNode
{
        SElemType data;
        struct StackNode *next;
}StackNode,*LinkStackPtr;


typedef struct
{
        LinkStackPtr top;
        int count;
}LinkStack;

2.構造一個空棧S

Status InitStack(LinkStack *S)
{ 
        S->top = (LinkStackPtr)malloc(sizeof(StackNode));
        if(!S->top)
                return ERROR;
        S->top=NULL;
        S->count=0;
        return OK;
} 

3. 把S置為空棧

Status ClearStack(LinkStack *S)
{ 
        LinkStackPtr p,q;
        p=S->top;
        while(p)
        {  
                q=p;
                p=p->next;
                free(q);
        } 
        S->count=0;
        return OK;
}

4. 若棧S為空棧，則返回TRUE，否則返回FALSE

Status StackEmpty(LinkStack S)
{ 
        if (S.count==0)
                return TRUE;
        else
                return FALSE;
}

5. 返回S的元素個數，即棧的長度

int StackLength(LinkStack S)
{ 
        return S.count;
}

6.若棧不空，則用e返回S的棧頂元素，並返回OK；否則返回ERROR

Status GetTop(LinkStack S,SElemType *e)
{
        if (S.top==NULL)
                return ERROR;
        else
                *e=S.top->data;
        return OK;
}

7. 插入元素e為新的棧頂元素

Status Push(LinkStack *S,SElemType e)
{
        LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); 
        s->data=e; 
        s->next=S->top;	/* 把當前的棧頂元素賦值給新結點的直接後繼，見圖中① */
        S->top=s;         /* 將新的結點s賦值給棧頂指針，見圖中② */
        S->count++;
        return OK;
}

8.若棧不空，則刪除S的棧頂元素，用e返回其值，並返回OK；否則返回ERROR

Status Pop(LinkStack *S,SElemType *e)
{ 
        LinkStackPtr p;
        if(StackEmpty(*S))
                return ERROR;
        *e=S->top->data;
        p=S->top;					/* 將棧頂結點賦值給p，見圖中③ */
        S->top=S->top->next;    /* 使得棧頂指針下移一位，指向後一結點，見圖中④ */
        free(p);                    /* 釋放結點p */        
        S->count--;
        return OK;
}

9.顯示全部數據

Status StackTraverse(LinkStack S)
{
        LinkStackPtr p;
        p=S.top;
        while(p)
        {
                 visit(p->data);
                 p=p->next;
        }
        printf("\n");
        return OK;
}

Status visit(SElemType c)
{
        printf("%d ",c);
        return OK;
}

參考<<大話數據結構>>