快捷導(dǎo)航

C語(yǔ)言詳解如何實(shí)現(xiàn)順序棧

更新時(shí)間：2022年04月22日 11:54:52 作者：平凡的人1

順序棧，就是用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放棧元素，然后用一個(gè)棧結(jié)構(gòu)去維護(hù)一個(gè)棧。在C中，可用動(dòng)態(tài)開(kāi)辟的數(shù)組去表示，維護(hù)的棧結(jié)構(gòu)需要有一個(gè)棧底和一個(gè)棧頂指針

順序棧的定義

首先，我們先來(lái)簡(jiǎn)單了解一下順序棧，前面線性表我們知道，根據(jù)順序存儲(chǔ)或者鏈?zhǔn)酱鎯?chǔ)分為順序表和單鏈表，同樣的，根據(jù)存儲(chǔ)方式的不同，我們把棧分為順序存儲(chǔ)的棧稱(chēng)為順序棧，鏈?zhǔn)酱鎯?chǔ)的棧稱(chēng)為鏈棧。我們要講的就是順序棧。實(shí)際上，有了前面線性表的一些知識(shí)后，關(guān)于棧的操作我們還是比較容易理解的。

順序棧的理解

問(wèn)題來(lái)了？我們?cè)趺慈ザx呢？通常我們可以用一個(gè)數(shù)組和記錄棧頂元素位置的變量組成，棧頂位置用整型變量Top記錄當(dāng)前棧頂元素的下標(biāo)值。當(dāng)Top==-1時(shí)，表示空棧。當(dāng)top==MAXSIZE-1時(shí)，表示滿棧。好了，下面開(kāi)始實(shí)現(xiàn)順序棧。

準(zhǔn)備工作

1.宏定義及其重命名

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */
typedef int Status; 
typedef int SElemType; /* SElemType類(lèi)型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

2.結(jié)構(gòu)體（順序棧的表示方式）

/* 順序棧結(jié)構(gòu) */
typedef struct
{
        SElemType data[MAXSIZE];
        int top; /* 用于棧頂指針 */
}SqStack;

具體實(shí)現(xiàn)

1.初始化

/*  構(gòu)造一個(gè)空棧S */
Status InitStack(SqStack *S)
{ 
        /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */
        S->top=-1;
        return OK;
}

2.清空

/* 把S置為空棧 */
Status ClearStack(SqStack *S)
{ 
        S->top=-1;
        return OK;
}

3.判斷是否為空

/* 若棧S為空棧，則返回TRUE，否則返回FALSE */
Status StackEmpty(SqStack S)
{ 
        if (S.top==-1)
                return TRUE;
        else
                return FALSE;
}

4.求長(zhǎng)度

/* 返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度 */
int StackLength(SqStack S)
{ 
        return S.top+1;
}

5.求棧頂元素

/* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */
Status GetTop(SqStack S, SElemType* e)
{
    if (S.top == -1) {
        return ERROR;
    }
    else {
        *e = S.data[S.top];
        return OK;
    }
}

6.入棧（判斷是否滿了）

/* 插入元素e為新的棧頂元素 */
Status Push(SqStack* S, SElemType e)
{
    if (S->top == MAXSIZE - 1) /* 棧滿 */
    {
        return ERROR;
    }
    S->top++;				/* 棧頂指針增加一 */
    S->data[S->top] = e;  /* 將新插入元素賦值給棧頂空間 */
    return OK;
}

7.出棧（判斷是否為空）

/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */
Status Pop(SqStack* S, SElemType* e)
{
    if (S->top == -1)
        return ERROR;
    *e = S->data[S->top];	/* 將要?jiǎng)h除的棧頂元素賦值給e */
    S->top--;				/* 棧頂指針減一 */
    return OK;
}

8.遍歷

/* 從棧底到棧頂依次對(duì)棧中每個(gè)元素顯示 */
Status StackTraverse(SqStack S)
{
    int i;
    i = 0;
    while (i <= S.top)
    {
        visit(S.data[i++]);
    }
    printf("\n");
    return OK;
}
Status visit(SElemType c)
{
    printf("%d ", c);
    return OK;
}

主函數(shù)

int main()
{
    int j;
    SqStack s;
    int e;
    if (InitStack(&s) == OK)
        for (j = 1; j <= 10; j++)
            Push(&s, j);
    printf("棧中元素依次為：");
    StackTraverse(s);
    Pop(&s, &e);
    printf("彈出的棧頂元素 e=%d\n", e);
    printf("?？辗瘢?d(1:空 0:否)\n", StackEmpty(s));
    GetTop(s, &e);
    printf("棧頂元素 e=%d 棧的長(zhǎng)度為%d\n", e, StackLength(s));
    ClearStack(&s);
    printf("清空棧后，棧空否：%d(1:空 0:否)\n", StackEmpty(s));
    return 0;
}

好啦，本次順序棧的一些知識(shí)就結(jié)束了。

到此這篇關(guān)于C語(yǔ)言詳解如何實(shí)現(xiàn)順序棧的文章就介紹到這了,更多相關(guān)C語(yǔ)言順序棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: