栈的c语言实现

栈的基本概念

栈是限定仅在表尾进行插入或删除的操作.因此,对于栈来说,表尾端有其特殊的含义,称为栈顶(top),相应的表头端称为栈底(bottom).不含元素的空表称为空栈.
栈的修改是按照后进先出的原则进行的,又成为lifo结构.插入元素的操作称为入栈,删除栈顶元素的操作成为出栈.

栈的基本操作有:

插入 删除 初始化 判空 取栈顶元素 清除栈 销毁栈 遍历栈 栈的长度

栈的表示和实现

栈有两种表示方式:

1. 顺序栈

使用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置.
一般实现方法:
    先为 栈分配一个基本容量,然后在应用过程中,当栈的空间不够使用时在逐段增大.
    顺序栈的定义如下:
    typedef struct{
        selemtype *base;
        selemtype *top;
        int stacksize;
    }
其中stacksize指示栈的当前可使用的最大容量,base称为栈底指针,始终指向栈底位置.top为栈顶指针,当top=base时,栈为空.当base=null时,栈结构不存在.

2. 链式栈

链式栈就是一个特殊的只能对第一个结点进行操作的单链表.这里不在做过多的论述

代码实现

顺序栈

基本上参考严蔚敏老师的《数据结构》（版）代码实现

/* 接口的定义文件 */
/* stack 顺序存储的结构定义和接口声明 */

/* 存储空间的初始分配量 */
#define stack_init_size 100
/* 存储空间分配增量 */
#define stackincrement 10

#define true 1
#define false 0



/* 定义数据类型 */
typedef int datatype;

/* 栈的数据结构定义 */
typedef struct{
    /* 在构造之前和销毁之后base的值为null */
    datatype *base;
    /* 栈顶指针 */
    datatype *top;
    /* 当前已分配的存储空间 */
    int stacksize;
}stack,*sp_stack;

/* 基本操作的函数原型说明 */

/* 构造一个空栈s */
sp_stack stack_init(sp_stack s);

/* 销毁栈s,s不再存在 */
void stack_destroy(sp_stack s);

/* 置栈为空 */
void stack_clear(sp_stack s);

/* 判断栈是否为空
 * 若为空,返回true
 * 否则返回false
*/
int stack_empty(sp_stack s);


/* 返回栈中元素的个数 */
int stack_length(sp_stack s);

/* 若栈不空
 * 用e返回s的栈顶元素,并返回true
 * 否则返回false
*/
int get_top(sp_stack s, datatype *e);


/* 插入元素e为新的栈顶元素 */
void push(sp_stack s, datatype e);

/* 若栈不空
 * 删除栈顶元素,用e返回其值,并返回true
 * 否则返回false
*/
int pop(sp_stack s, datatype *e);



/* 从栈底到栈顶依次对栈中每个元素调用visit()函数.
 * 一旦visit()失败,则操作失败
*/
 void stack_traverse(sp_stack s, void(*visit)(sp_stack));

/* 遍历处理函数 */
void visit(sp_stack s);

 /* 接口的实现文件 */
 #include
#include
#include"sp_stack.h"



sp_stack stack_init(sp_stack s)
{
    /* 申请内存空间 */
    s -> base = (datatype *)malloc(sizeof(datatype) * stack_init_size);
    /* 申请内存失败 */
    if (!s -> base)
        exit(0);
    s -> stacksize = stack_init_size;
    s -> top = s -> base;
    return s;
}


void stack_destory(sp_stack s)
{
    free(s -> base);
    free(s);
    s = null;
}



void stack_clear(sp_stack s)
{
    s -> top = s -> base;
}


int stack_length(sp_stack s)
{
    int l = s -> top - s -> base;
    return l;
}


int get_top(sp_stack s, datatype *e)
{
    if (s -> top == s -> base)
        return false;
    *e = *(s -> top);
    return true;
}

void push(sp_stack s, datatype e)
{
    /* 内存已满 */
    if ( (s -> top - s -> base) >= s -> stacksize)
    {
        s -> base = (datatype *) realloc(s -> base, (s -> stacksize + stackincrement) * sizeof(datatype));
        /* 申请内存失败 */
        if (!s -> base)
            exit(0);
        s -> top = s -> base + s -> stacksize;
        s -> stacksize = s -> stacksize + stackincrement;

    }
    s -> top = s -> top + 1;
    *s -> top = e;
}


int pop(sp_stack s, datatype *e)
{
    /* 栈为空 */
    if(s -> top == s -> base)
        return false;
    *e = *s -> top;
    s -> top = s -> top - 1;
    return true;
}


void stack_traverse(sp_stack s, void (*visit)(sp_stack s))
{
    visit(s);
}


void visit(sp_stack s)
{
    datatype *temp = s -> base + 1;
    while(true)
    {
        if(temp  top)
        {
            printf("%d ", *temp);
            temp = temp + 1;
        }
        else
        {
            printf("\n");
            break;
        }
    }

}



int main()
{
    sp_stack s = (sp_stack)malloc(sizeof(stack));
    s = stack_init(s);
    printf("length:%d\n", stack_length(s));
    push(s, 1);
    printf("length:%d\n", stack_length(s));
    push(s, 2);
    printf("length:%d\n", stack_length(s));
    push(s, 3);
    printf("length:%d\n", stack_length(s));
    stack_traverse(s, visit);
    datatype *e;
    get_top(s, e);
    printf("get_top:%d\n", *e);
    stack_traverse(s, visit);   
    pop(s, e);
    printf("pop:%d\n", *e);
    stack_clear(s);
    printf("length:%d\n", stack_length(s));
    stack_traverse(s, visit);
}

链式栈

参考严蔚敏老师的《数据结构》（c语言版）的接口，接口的实现有自己完成。

/* 接口的定义文件 */
/* stack 链式存储的结构定义和接口声明 */


#define true 1
#define false 0



/* 定义数据类型 */
typedef int datatype;

/* 栈的数据结构定义 */
typedef struct stack{
    /* 数据域 */
    datatype data;
    /* 指针域 */
    struct stack *next;
}stack,*lp_stack;

/* 基本操作的函数原型说明 */

/* 构造一个空栈s */
lp_stack stack_init(lp_stack s);

/* 销毁栈s,s不再存在 */
void stack_destroy(lp_stack s);

/* 置栈为空 */
void stack_clear(lp_stack s);

/* 判断栈是否为空
 * 若为空,返回true
 * 否则返回false
*/
int stack_empty(lp_stack s);


/* 返回栈中元素的个数 */
int stack_length(lp_stack s);

/* 若栈不空
 * 用e返回s的栈顶元素,并返回true
 * 否则返回false
*/
int get_top(lp_stack s, datatype *e);


/* 插入元素e为新的栈顶元素 */
void push(lp_stack s, datatype e);

/* 若栈不空
 * 删除栈顶元素,用e返回其值,并返回true
 * 否则返回false
*/
int pop(lp_stack s, datatype *e);



/* 从栈底到栈顶依次对栈中每个元素调用visit()函数.
 * 一旦visit()失败,则操作失败
*/
 void stack_traverse(lp_stack s, void(*visit)(lp_stack));

/* 遍历处理函数 */
void visit(lp_stack s);


/* 接口的实现文件 */
#include
#include
#include"lp_stack.h"



lp_stack stack_init(lp_stack s)
{

    s -> next = null;
    return s;
}


void stack_destroy(lp_stack s)
{
    lp_stack temp = s;
    while(s)
    {
        s = s -> next;
        free(temp);
        temp = s;
    }
}



void stack_clear(lp_stack s)
{
    lp_stack temp = s -> next;
    while(s -> next)
    {
        s -> next = s -> next -> next;
        free(temp);
        temp = s -> next;
    }
}


int stack_empty(lp_stack s)
{
    if(s -> next = null)
        return true;
    return false;

}


int stack_length(lp_stack s)
{
    /* 栈的当前结点 */
    lp_stack top = s -> next;
    /* 计数器 */
    int count = 0;
    while(top)
    {
        count += 1;
        top = top -> next;
    }
    return count;
}

int get_top(lp_stack s, datatype *e)
{
    if (s -> next == null)
        return false;
    *e = s -> next -> data;
    return true;
}

void push(lp_stack s, datatype e)
{
    lp_stack new_node = (lp_stack)malloc(sizeof(stack));
    new_node -> data = e;
    new_node -> next = s -> next;
    s -> next = new_node;
}


int pop(lp_stack s, datatype *e)
{
    if(s -> next == null)
        return false;
    *e = s -> next -> data;
    lp_stack node = s -> next;
    s -> next = s -> next -> next;
    free(node);
    return true;
}

void stack_traverse(lp_stack s, void (*visit)(lp_stack))
{
    visit(s);
}


void visit(lp_stack s)
{
    lp_stack node = s -> next;
    while(node)
    {
        printf("%d ",node -> data);
        node = node -> next;
    }
}

int main()
{
    lp_stack s = (lp_stack)malloc(sizeof(stack));
    s = stack_init(s);
    printf("length:%d\n", stack_length(s));
    push(s, 1);
    printf("length:%d\n", stack_length(s));
    push(s, 2);
    printf("length:%d\n", stack_length(s));
    push(s, 3);
    printf("length:%d\n", stack_length(s));
    stack_traverse(s, visit);
    datatype *e;
    get_top(s, e);
    printf("get_top:%d\n", *e);
    stack_traverse(s, visit);   
    pop(s, e);
    printf("pop:%d\n", *e);
    stack_traverse(s, visit);
    stack_clear(s);
    printf("length:%d\n", stack_length(s));
    stack_traverse(s, visit);
}