栈操作C语言实现

栈是一种限制线性列表，该类列表的添加和删除操作只能在一端实现，称为栈顶。栈的实现可以使用数组也可以使用链表来实现。
下面的C语言部分实现了顺序栈的基本操作，包括栈的初始化、入栈、出栈、获得栈顶元素的值等。

#include <stdio.h>
#include <stdbool.h>
/*定义栈的大小*/
#define maxsize 100
typedef int ElemType;

/*顺序栈的实现*/
typedef struct SqStack
{
    ElemType data[maxsize];
    int top;
}SqStack;

/*栈的初始化*/
void initstack(SqStack * s)
{
     if(NULL == s)
        return;
    s->top = -1;
}

/*判断栈空*/
bool stackempty(SqStack *s)
{
     if(NULL == s)
        return true;
    if(-1 == s->top)
        return true;
    else
        return false;
}

/*判断栈满*/
bool stackfull(SqStack *s)
{
     if(NULL == s)
        return false;
    if(s->top >= maxsize-1)
        return true;
    else
        return false;
}

/*入栈操作*/
void push(SqStack *s,ElemType x)
{
    if(stackfull(s))
        return;
    s->top += 1;
    s->data[s->top] = x;
}
/*出栈操作*/
int pop(SqStack *s,ElemType *x)
{
    if(stackempty(s))
        return -1;
    
    *x = s->data[s->top];
    s->top--;
    return 0;
}
/*获取栈顶元素*/
int gettop(SqStack *s,ElemType *x)
{
    if(stackempty(s))
        return -1;
    *x = s->data[s->top];
    return 0;
}
/*清空栈*/
void clearstack(SqStack *s)
{
    if(stackempty(s))
        return;
    s->top = -1;
}
int main(int argc, const char * argv[])
{
    SqStack s;
    ElemType x = 0;
    initstack(&s);
    if(s.top != -1)
        printf("error");
    /*入栈100个元素*/
    for(int i = 0;i < 100;i++)
        push(&s,i);
    /*判断此时栈满*/
    if(!stackfull(&s))
        printf("error");
    /*出栈，打印栈顶元素值*/
    for(int i = 0;i < 100;i++)
    {
        pop(&s,&x);
        printf("%d ",x);
        /*每行打印10个元素*/
        if(0 == (i+1)%10)
            printf("\n");
    }
    /*判断此时栈满*/
    if(!stackempty(&s))
        printf("error");
    
    
    return 0;
}

上面的实现是使用数组来实现栈，有一个明显的缺陷是栈的大小在开始时就已经确定，无法扩展。可以使用realloc函数对上述代码进行修改.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/*定义栈的初始大小*/
#define STACK_INITSIZE   100
/*定义增幅*/
#define STACK_INCREMENT  100
typedef int ElemType;

int realsize = STACK_INITSIZE;
/*顺序栈的实现*/
typedef struct SqStack
{
    /*指向申请的内存，用于存储栈数据结构*/
    ElemType *data;
    int top;
}SqStack;

/*栈的初始化*/
int initstack(SqStack * s)
{
    /*入参为NULL，返错*/
    if(NULL == s)
        return -1;
    s->top = -1;
    s->data = (ElemType *)malloc(STACK_INITSIZE * sizeof(ElemType));
    /*申请内存失败，返错*/
    if(NULL == s->data)
        return -1;
    
    return 0;
}

/*判断栈空*/
bool stackempty(SqStack *s)
{
    if(NULL == s)
        return true;
    
    if(-1 == s->top)
        return true;
    else
        return false;
}

/*入栈操作*/
int push(SqStack *s,ElemType x)
{
    if(NULL == s)
        return -1;
    
    /*栈满，再分配STACK_INCREMENT个元素*/
    if(realsize-1 == s->top)
    {
        realsize += STACK_INCREMENT;
        s->data = (ElemType *)realloc(s->data,realsize*sizeof(ElemType));
        /*申请内存失败，返错*/
        if(NULL == s->data)
            return -1;
    }
    
    s->top += 1;
    s->data[s->top] = x;
    
    return 0;
}
/*出栈操作*/
int pop(SqStack *s,ElemType *x)
{
    if(NULL == s)
        return false;
    
    if(stackempty(s))
        return -1;
    
    *x = s->data[s->top];
    s->top--;
    return 0;
}
/*获取栈顶元素*/
int gettop(SqStack *s,ElemType *x)
{
    if(stackempty(s))
        return -1;
    *x = s->data[s->top];
    return 0;
}
/*清空栈,只是将top设置为-1,没有释放申请的内存*/
void clearstack(SqStack *s)
{
    if(stackempty(s))
        return;
    s->top = -1;
}
void destorystack(SqStack *s)
{
    if(NULL == s)
        return;
    
    if(s->data != NULL)
        free(s->data);
    s->top = -1;
}

int main(int argc, const char * argv[])
{
    SqStack s;
    ElemType x = 0;
    initstack(&s);
    if(s.top != -1)
        printf("error");
    /*入栈200个元素*/
    for(int i = 0;i < 200;i++)
        push(&s,i);
    
    /*出栈，打印栈顶元素值*/
    for(int i = 0;i < 200;i++)
    {
        pop(&s,&x);
        printf("%d ",x);
        /*每行打印10个元素*/
        if(0 == (i+1)%10)
            printf("\n");
    }
    /*判断此时栈空*/
    if(!stackempty(&s))
        printf("error");
    
    destorystack(&s);
    return 0;
}

52coder

栈操作C语言实现