基本的抽象數(shù)據(jù)類型（ADT）是編寫C程序必要的過程，這類ADT有鏈表、堆棧、隊列和樹等，本文主要講解下堆棧的幾種實現(xiàn)方法以及他們的優(yōu)缺點。
　　堆棧（stack）的顯著特點是后進先出（Last-In First-Out, LIFO），其實現(xiàn)的方法有三種可選方案：靜態(tài)數(shù)組、動態(tài)分配的數(shù)組、動態(tài)分配的鏈式結(jié)構(gòu)。
　　靜態(tài)數(shù)組：特點是要求結(jié)構(gòu)的長度固定，而且長度在編譯時候就得確定。其優(yōu)點是結(jié)構(gòu)簡單，實現(xiàn)起來方便而不容易出錯。而缺點就是不夠靈活以及固定長度不容易控制，適用于知道明確長度的場合。
　　動態(tài)數(shù)組：特點是長度可以在運行時候才確定以及可以更改原來數(shù)組的長度。優(yōu)點是靈活，缺點是由此會增加程序的復(fù)雜性。
　　鏈式結(jié)構(gòu)：特點是無長度上限，需要的時候再申請分配內(nèi)存空間，可最大程度上實現(xiàn)靈活性。缺點是鏈式結(jié)構(gòu)的鏈接字段需要消耗一定的內(nèi)存，在鏈式結(jié)構(gòu)中訪問一個特定元素的效率不如數(shù)組。
　　首先先確定一個堆棧接口的頭文件，里面包含了各個方案下的函數(shù)原型，放在一起是為了實現(xiàn)程序的模塊化以及便于修改。然后再接著分別介紹各個方案的具體實施方法。
注意：棧的鏈式存儲結(jié)構(gòu)實際上是一個單鏈表，叫鏈棧。只是插入和刪除操作只能在鏈棧的棧頂進行??！

一、靜態(tài)數(shù)組

#include <stdio.h>
#include <assert.h>

#define STACK_TYPE int
#define stack_size 50
static int top_index = -1;
static STACK_TYPE stack[stack_size];

void push(STACK_TYPE);
void pop();
int is_empty();
int is_full();
STACK_TYPE top();
void print();
void destroystack();

int main(int argc, const char * argv[]) {
    return 0;
}

void push(STACK_TYPE value)
{
    assert(!is_full());
    top_index ++;
    stack[top_index] = value;
}
void pop()
{
    assert(!is_empty());
    top_index --;
}
STACK_TYPE top()
{
    assert(!is_empty());
    return stack[top_index];
}
void print()
{
    if (is_empty()) {
        perror("kong shu zu");
    }
        int i = top_index;
    while (i!=-1) { 
    printf(“%d”,stack[i—]);
    }
    printf(“\n")
}

二、動態(tài)數(shù)組

#include <stdio.h>
#include<assert.h>
#include<stdio.h> 
#include<malloc/malloc.h>
#include <stdlib.h>
#define STACK_TYPE int

static size_t        stack_size;
static STACK_TYPE *stack;
static int top_index = -1;

void create_stack(size_t size);
void destroy_stack(void);
void push(STACK_TYPE);
void pop();
STACK_TYPE top();
int is_empty(void);
int is_full(void);
void print();


int main(int argc, const char * argv[]) {
    create_stack(50);
    push(10); push(9); push(8); push(7); push(6); push(5);
    push(4);  push(3); push(2); push(1); push(0);
    printf("push壓入數(shù)值后：\n");
    print();
    printf("\n");
    pop();
    pop();
    printf("經(jīng)過pop彈出幾個元素后的堆棧元素:\n");
    print();
    printf("\n");
    printf("top()調(diào)用出來的值: %d\n",top());
    return 0;
}
void create_stack(size_t size)
{
    assert(stack_size == 0);
    stack_size = size;
    stack = (STACK_TYPE *)malloc(stack_size * sizeof(STACK_TYPE));
    if (stack == NULL) {
        perror("malloc分配失敗");
    }
}
void destroy_stack(void)
{
    assert(stack_size > 0);
    stack_size = 0;
    free(stack);
    stack = NULL;
}
void push(STACK_TYPE value)
{
    assert(!is_full());
    top_index ++;
    stack[top_index] = value;
}
void pop()
{
    assert(!is_empty());
    stack[top_index] = 0x0;
    top_index --;
}
STACK_TYPE top()
{
    assert(!is_empty());
    return stack[top_index];
}
int is_empty(void)
{
    return top_index == -1;
}
int is_full(void)
{
    return top_index == stack_size - 1;
}
void print()
{
    for (int i = top_index; i>=0; i--) {
        printf("%d",stack[i]);
        printf("\n");
    }
}

三、鏈式結(jié)構(gòu)

#include <stdio.h>
#include<assert.h>
#include<stdio.h> 
#include<malloc/malloc.h>
#include <stdlib.h>
#define STACK_TYPE int
typedef struct STACK_NODE {
    struct STACK_NODE *next;
    STACK_TYPE value;
}StackNode;
static StackNode *stack;
void print();

void create_stack()
{
    assert(stack==NULL);
    stack = (StackNode *)malloc(sizeof(StackNode));
    if (stack == NULL) {
        printf("malloc fail");
    }
}
int is_empty()
{
    return stack == NULL;
}
void pop()
{
    assert(!is_empty());
    StackNode *topNode = stack;
    stack = stack -> next;
    free(topNode);
    topNode = NULL;
}
void destroy_stack()
{
    while (!is_empty())
    {
        pop();
    }
}

void push(STACK_TYPE value)
{
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        perror("malloc fail");
    }
    newNode -> value = value;
    newNode -> next = stack;//此時stack為NULL
    stack = newNode;
}

STACK_TYPE top()
{
    assert(!is_empty());
    return stack -> value;
}

int main(int argc, const char * argv[]) {
    push(10); push(9); push(8); push(7); push(6); push(5);
    push(4);  push(3); push(2); push(1); push(0);
    printf("push壓入數(shù)值后：\n");
    print();
    printf("\n");
    pop();
    pop();
    printf("經(jīng)過pop彈出幾個元素后的堆棧元素:\n");
    print();
    printf("\n");
    printf("top()調(diào)用出來的值: %d\n",top());
    return 0;
}
void print()
{
    if (is_empty()) {
        perror("kong shu zu");
    }
    StackNode *top = stack;
    while (top != NULL) {
        printf("%d",top->value);
        top = top -> next;
    }
    printf("\n");
}

鏈接：https://blog.csdn.net/jjzhoujun2010/article/details/6856164