详解堆栈的几种实现方法——C语言版

基本的抽象数据类型（ADT）是编写C程序必要的过程，这类ADT有链表、堆栈、队列和树等，本文主要讲解下堆栈的几种实现方法以及他们的优缺点。
　　堆栈（stack）的显著特点是后进先出（Last-In First-Out, LIFO），其实现的方法有三种可选方案：静态数组、动态分配的数组、动态分配的链式结构。
　　静态数组：特点是要求结构的长度固定，而且长度在编译时候就得确定。其优点是结构简单，实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制，适用于知道明确长度的场合。
　　动态数组：特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活，缺点是由此会增加程序的复杂性。
　　链式结构：特点是无长度上限，需要的时候再申请分配内存空间，可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存，在链式结构中访问一个特定元素的效率不如数组。
　　首先先确定一个堆栈接口的头文件，里面包含了各个方案下的函数原型，放在一起是为了实现程序的模块化以及便于修改。然后再接着分别介绍各个方案的具体实施方法。
注意：栈的链式存储结构实际上是一个单链表，叫链栈。只是插入和删除操作只能在链栈的栈顶进行！！

一、静态数组

#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")
}

二、动态数组

#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压入数值后：\n");
    print();
    printf("\n");
    pop();
    pop();
    printf("经过pop弹出几个元素后的堆栈元素:\n");
    print();
    printf("\n");
    printf("top()调用出来的值: %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");
    }
}

三、链式结构

#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压入数值后：\n");
    print();
    printf("\n");
    pop();
    pop();
    printf("经过pop弹出几个元素后的堆栈元素:\n");
    print();
    printf("\n");
    printf("top()调用出来的值: %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

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,922评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,591评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,546评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,467评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,553评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,580评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,588评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,334评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,780评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,092评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,270评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,925评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,573评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,194评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,437评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,154评论 2赞 366
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,127评论 2赞 352