簡(jiǎn)介

• 棧是一種數(shù)據(jù)結(jié)構(gòu)
• ?？梢杂脕?lái)存放數(shù)字
• 一次只能向棧里加入一個(gè)數(shù)字，一次也只能從棧里獲得一個(gè)數(shù)字
• 棧里到的數(shù)字有前后順序，先進(jìn)入到的數(shù)字在前，后進(jìn)入的數(shù)字在后
• 每次從棧里獲取的數(shù)字一定是最后面的數(shù)字，最后獲取的數(shù)字一定是最前面的數(shù)字
• 這種取數(shù)字的方法叫先進(jìn)后出，后進(jìn)先出

下面是它存儲(chǔ)數(shù)據(jù)的過(guò)程

下面是它取出這三個(gè)數(shù)據(jù)的過(guò)程

上面兩幅圖展示了棧存儲(chǔ)數(shù)據(jù)和取出數(shù)據(jù)的一個(gè)過(guò)程，體現(xiàn)了先進(jìn)后出，后進(jìn)先出這個(gè)特性。

代碼實(shí)現(xiàn)

以下就是創(chuàng)建棧的數(shù)據(jù)結(jié)構(gòu)，并且實(shí)現(xiàn)其功能的相關(guān)函數(shù)。

1. 定義棧

typedef struct stack{
    int *arr;  // 分配存儲(chǔ)區(qū)的首地址
    int cap;  // 棧中的元素個(gè)數(shù)
    int top;  // 入棧和出棧的位置
}stack_t;

2. 初始化棧

void stack_init(stack_t* pstack, int cap){
    pstack->arr = malloc(sizeof(int) * cap);  // 分配內(nèi)存給存儲(chǔ)區(qū)
    if(pstack->arr == NULL){
        printf("棧的存儲(chǔ)區(qū)分配失敗!\n");
        return;
    }
    pstack->cap = cap;  // 初始化傳入的元素個(gè)數(shù)
    pstack->top = 0;  // 一開(kāi)始入棧的索引是在0
}

3. 釋放棧

void stack_deinit(stack_t* pstack){
    // 釋放內(nèi)存，并重置為0和NULL
    free(pstack->arr);
    pstack->arr = NULL;
    pstack->cap = 0;
    pstack->top = 0;
}

4. 壓棧

void stack_push(stack_t* pstack, int data){
    // 將傳入的數(shù)據(jù)放到棧中
    pstack->arr[pstack->top++] = data;  // 先將數(shù)據(jù)放入索引為top的位置，然后將top++，往后移
}

5. 出棧

int stack_pop(stack_t* pstack){
    // 當(dāng)棧中有數(shù)據(jù)時(shí)，此時(shí)top肯定是指向最后一個(gè)傳進(jìn)去的數(shù)據(jù)后一個(gè)，此時(shí)只需將top--，之后再將數(shù)據(jù)取出即可
    return pstack->arr[--pstack->top];
}

6. 判斷棧是否已滿

int stack_full(stack_t* pstack){
    // 因?yàn)閠op索引是從0開(kāi)始的，有一個(gè)數(shù)據(jù)進(jìn)來(lái)，top就加1，所以top的值就是當(dāng)前棧中元素的個(gè)數(shù)，當(dāng)它等于cap時(shí)，說(shuō)明棧滿了
    return pstack->top >= pstack->cap;  // 滿了返回真(非0)，沒(méi)滿返回假(0)
}

7. 判斷棧是否為空

int stack_empty(stack_t* pstack){
    // 參考第6條，top的值就是當(dāng)前棧中元素的個(gè)數(shù)，top值為0說(shuō)明為空
    return pstack->top == 0;  // 為空返回真(非0)，不為空返回假(0)
}

8. 獲取棧中的元素個(gè)數(shù)

int stack_size(stack_t* pstack){
    // 參考第6條，top的值就是當(dāng)前棧中元素的個(gè)數(shù)
    return pstack->top;
}

實(shí)例代碼

創(chuàng)建三個(gè)文件: stack.c，stack.h，main.c文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-637483.html

• stack.c定義棧具體的函數(shù)

#include "stack.h"

// 初始化棧
void stack_init(stack_t* pstack, int cap){
    pstack->arr = malloc(sizeof(int) * cap);
    if(pstack->arr == NULL){
        printf("棧的存儲(chǔ)區(qū)分配失敗!\n");
        return;
    }
    pstack->cap = cap;
    pstack->top = 0;
}

// 釋放棧
void stack_deinit(stack_t* pstack){
    free(pstack->arr);
    pstack->arr = NULL;
    pstack->cap = 0;
    pstack->top = 0;
}

// 壓棧
void stack_pull(stack_t* pstack, int data){
    pstack->arr[pstack->top++] = data;
}

// 出棧
int stack_pop(stack_t* pstack){
    return pstack->arr[--pstack->top];
}

// 判斷棧是否已滿
int stack_full(stack_t* pstack){
    return pstack->top >= pstack->cap;
}

// 判斷棧是否為空
int stack_empty(stack_t* pstack){
    return pstack->top == 0;
}

// 獲取棧中的元素個(gè)數(shù)
int stack_size(stack_t* pstack){
    return pstack->top;
}

• stack.h聲明棧的相關(guān)函數(shù)和定義棧

#ifndef __STACK_H  // 頭衛(wèi)士
#define __STACK_H
#include <stdio.h>
#include <stdlib.h>

// 定義棧的數(shù)據(jù)結(jié)構(gòu)
typedef struct stack{
    int* arr;
    int cap;
    int top;
}stack_t;

// 聲明棧的函數(shù)
extern void stack_init(stack_t* pstack, int cap);
extern void stack_deinit(stack_t* pstack);
extern void stack_pull(stack_t* pstack, int data);
extern int stack_pop(stack_t* pstack);
extern int stack_full(stack_t* pstack);
extern int stack_empty(stack_t* pstack);
extern int stack_size(stack_t* pstack);
#endif

• main.c主函數(shù)使用棧

#include "stack.h"

int main(void){
    // 1. 聲明一個(gè)棧: stack
    stack_t stack;

    // 2. 初始化stack
    stack_init(&stack, 5);

    // 3. 將棧放滿數(shù)據(jù)
    int data = 100;
    printf("開(kāi)始放入數(shù)據(jù): ");
    while(!stack_full(&stack)){
        // 沒(méi)滿的狀態(tài)下，放入數(shù)據(jù)
        printf("%d ", data);
        stack_pull(&stack, data++);
    }
    printf("結(jié)束!\n");
    printf("此時(shí)棧中元素個(gè)數(shù)為: %d\n\n", stack_size(&stack));

    // 4. 將棧中的數(shù)據(jù)一個(gè)個(gè)取出來(lái)
    printf("開(kāi)始取出數(shù)據(jù): ");
    while(!stack_empty(&stack)){
        // 非空的狀態(tài)，取數(shù)據(jù)
        data = stack_pop(&stack);
        printf("%d ", data);
    }
    printf("結(jié)束!\n");
    printf("此時(shí)棧中元素個(gè)數(shù)為: %d\n\n", stack_size(&stack));

    // 5. 釋放棧
    stack_deinit(&stack);
    return 0;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-棧（C語(yǔ)言簡(jiǎn)單實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！