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

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

順序棧，就是用一組地址連續(xù)的存儲單元來存放棧元素，然后用一個棧結構去維護一個棧。在C中，可用動態(tài)開辟的數(shù)組去表示，維護的棧結構需要有一個棧底和一個棧頂指針

順序棧的定義

首先，我們先來簡單了解一下順序棧，前面線性表我們知道，根據(jù)順序存儲或者鏈式存儲分為順序表和單鏈表，同樣的，根據(jù)存儲方式的不同，我們把棧分為順序存儲的棧稱為順序棧，鏈式存儲的棧稱為鏈棧。我們要講的就是順序棧。實際上，有了前面線性表的一些知識后，關于棧的操作我們還是比較容易理解的。

順序棧的理解

問題來了？我們怎么去定義呢？通常我們可以用一個數(shù)組和記錄棧頂元素位置的變量組成，棧頂位置用整型變量Top記錄當前棧頂元素的下標值。當Top==-1時，表示空棧。當top==MAXSIZE-1時，表示滿棧。好了，下面開始實現(xiàn)順序棧。

準備工作

1.宏定義及其重命名

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

2.結構體（順序棧的表示方式）

/* 順序棧結構 */
typedef struct
{
        SElemType data[MAXSIZE];
        int top; /* 用于棧頂指針 */
}SqStack;

具體實現(xiàn)

1.初始化

/*  構造一個空棧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.求長度

/* 返回S的元素個數(shù)，即棧的長度 */
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];	/* 將要刪除的棧頂元素賦值給e */
    S->top--;				/* 棧頂指針減一 */
    return OK;
}

8.遍歷

/* 從棧底到棧頂依次對棧中每個元素顯示 */
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 棧的長度為%d\n", e, StackLength(s));
    ClearStack(&s);
    printf("清空棧后，棧空否：%d(1:空 0:否)\n", StackEmpty(s));
    return 0;
}

好啦，本次順序棧的一些知識就結束了。

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

您可能感興趣的文章: