C語言棧之順序棧

2022-02-10 19:01:11

定義

用順序儲存方式實現的棧稱為順序棧，順序棧對應於順序表。

設棧中的資料元素的型別是整型，用一個足夠長的一維陣列s來存放元素，陣列的最大容量為STACK_INTSIZE。同時假設棧頂指標top。（在以下的程式中，top不是指向當前的棧頂元素，而是指向下一次將要進棧的元素的儲存位置）

順序棧可以描述如下：

#define STACK_INTSIZE 50 /*分配棧的最大儲存空間*/
#define DataType int /*定義棧中資料元素的型別*/
DataType s[STACK_INTSIZE];/*用來存放棧中資料元素的記憶體空間*/
int top;/*定義棧頂指標*/

可以用結構體陣列來實現順序棧：

#define STACK_INTSIZE 50
#define DataType int
typedef struct
{
    DataType s[STACK_INTSIZE];
    int top;
} Stack;
Stack *st;/*指標st用來參照一個順序棧*/

棧頂指標動態地反映了棧中元素的變化情況，top=0時，表示空棧；top=1時，表示已經有一個元素進棧；進棧時，棧頂指標top上移，top加1；top=STACK_INTSIZE，表示棧滿；出棧時，棧頂指標top下移，top減1。

1.建立空棧

Stack *InitStack()
{
    Stack *s;
    s = (Stack *)malloc(sizeof(Stack));
    s->top = 0;
    return s;
}

2.進棧

void Push(Stack *st, DataType x)
{
    if (st->top >= STACK_INTSIZE)
        printf("棧已滿，不能入棧！n");/*若棧滿則不能進棧，輸出出錯資訊*/
    else
    {
        st->s[st->top] = x;/*元素x進棧*/
        st->top++;/*棧頂指標top加1*/
    }
}

3.出棧

void Pop(Stack *st)
{
    if (st->top == 0)
        printf("棧空，不能出棧！n");/*若棧空則不能出棧，且輸出棧空的資訊*/
    else/*棧非空*/
    {
        st->top--;/*top減1，元素出棧*/
    }
}

4.讀棧頂元素

DataType ReadTop(Stack *st)
{
    DataType x;
    if (st->top == 0)
    {
        printf("棧中無元素");
        return (0);
    }
    /*若棧空則返回0*/
    else
    {
        x = st->s[st->top-1];/*取棧頂元素*/
        return (x);/*返回x即棧頂元素的值*/
    }
}

5.遍歷棧

結合元素出棧演演算法和讀取棧頂元素演演算法，使用迴圈，當st->top=0時結束迴圈，即可遍歷棧。

void ShowStack(Stack *st)
{
    while (st->top > 0)
    {
        st->top--;
        printf("%d", st->s[st->top]);
    }
}

總結

本篇文章就到這裡了，希望能夠給你帶來幫助，也希望您能夠多多關注it145.com的更多內容!