C語言資料結構(5)--順序棧

1. 背景

棧應該是第一次出現一個很專業名詞的資料結構了吧，但是棧依然是一個非常簡單一維結構。

之是以稱之為棧，就是因為棧的特點是後進先出，就像一個貨棧，先放進去東西總是放在裡面，後放進去的東西放到門口，是以往外拿出來的時候，就先拿出來門口的。

2. 順序棧

我們把線性表看為從上到下的一個一維結構，不管是往線性表裡添加元素還是取出元素，都是在上部（頂部）操作，不就是後進先出了嗎。

是以棧其實就是在一維線性表頂部（最後面）進行添加或者取出的集合。

棧可以使用數組或者連結清單作為存儲結構，當使用數組時為順序棧，使用連結清單時為鍊棧。

3. 棧的操作

入棧，将一個元素放入棧中

出棧，将棧頂元素拿出來

其他操作實際上都是以這幾個操作為基礎實作的。

4. 順序棧的代碼實作

/*
* 順序棧的實作
* 作者：熊貓大大
* 時間：2019-09-28
*/
#include<stdio.h>
#define STACK_LENGTH 10

//定義結構體儲存棧資訊
struct Stack
{
    //棧元素
    int element[STACK_LENGTH];
    //棧頂位置 top==0表示元素為空 top==x表示有x個元素且棧頂元素在element[x-1]處
    int top;
};

//展示棧内所有元素(友善測試)，從棧頂到棧底的順序展示即可
void printStack(struct Stack *p)
{
    int i;
    printf("==================目前棧内元素如下\n");
    for (i = p->top - 1; i >= 0; i--)
    {
        printf("%d ", p->element[i]);
    }
    printf("\n==================\n");
}

//入棧
int stackIn(struct Stack *p, int num)
{
    if (p->top>STACK_LENGTH - 1)//棧滿了
        return 0;//入棧失敗
    p->element[p->top] = num;
    p->top++;
    return 1;//入棧成功
}

//出棧，以傳回值的形式提供出棧元素的值
int stackOut(struct Stack *p, int *result)
{
    if (p->top <= 0)//空棧
        return 0;
    //取棧頂元素
    *result = p->element[p->top - 1];
    //棧頂元素出棧
    p->top--;
    return 1;
}

//入口
int main()
{
    //初始化
    struct Stack stack;
    stack.top = 0;
    printStack(&stack);

    //入棧
    stackIn(&stack, 1);
    stackIn(&stack, 2);
    stackIn(&stack, 3);
    stackIn(&stack, 7);
    stackIn(&stack, 8);
    stackIn(&stack, 9);
    //輸出
    printStack(&stack);

    //出棧
    int result;
    stackOut(&stack, &result);
    printf("OUT:%d\n", result);
    stackOut(&stack, &result);
    printf("OUT:%d\n", result);
    stackOut(&stack, &result);
    printf("OUT:%d\n", result);
    printStack(&stack);
    stackOut(&stack, &result);
    printf("OUT:%d\n", result);
    stackOut(&stack, &result);
    printf("OUT:%d\n", result);
    stackOut(&stack, &result);
    printf("OUT:%d\n", result);
    printStack(&stack);
    return 1;
}