数据结构C语言实现系列[2]——栈

转载于 http://blog.csdn.net/dl88250/article/details/1496575

#include <stdio.h>
#include <stdlib.h>

typedef int elemType;
/************************************************************************/
/*                      以下是关于栈顺序存储操作的6种算法                            */
/************************************************************************/
struct stack{
    elemType *stack;        /* 存储栈元素的数组指针 */
    int top;                /* 存储栈顶元素的下标位置 */
    int maxSize;            /* 存储stack数组的长度 */
};

void againMalloc(struct stack *s)
{
    /* 空间扩展为原来的2倍，原内容被自动拷贝到p所指向的存储空间中 */
    elemType *p;
    p = realloc(s->stack, 2 * s->maxSize * sizeof(elemType));
    if(!p){
        printf("内在分配失败！ ");
        exit(1);
    }
    s->stack = p;        /* 使stack指向新的栈空间 */
    s->maxSize = 2 * s->maxSize;        /* 把栈空间的大小修改新的长度 */
    return;
}

/* 1.初始化栈s为空 */
void initStack(struct stack *s, int ms)
{
    if(ms <=0){
        printf("ms的值非法！ ");
        exit(1);
    }
    s->maxSize = ms;
    s->stack = malloc(ms * (sizeof(elemType)));
    if(!s->stack){
        printf("内在分配失败！ ");
        exit(1);
    }
    s->top = -1;        /* 初始置栈为空 */
    return;
}

/* 2.新元素进栈，即把它插入到栈顶 */
void push(struct stack *s, elemType x)
{
    /* 若栈空间用尽则重新分配更大的存储空间 */
    if(s->top == s->maxSize - 1){
        againMalloc(s);
    }
    s->top++;        /* 栈顶指针后移一个位置 */
    s->stack[s->top] = x;        /* 将新元素插入到栈顶 */
    return;
}

/* 3.删除(弹出)栈顶元素并返回其值 */
elemType pop(struct stack *s)
{
    /* 若栈空则退出运行 */
    if(s->top == -1){
        printf("栈空，无元素出栈！ ");
        exit(1);
    }
    s->top--;        /* 栈顶指针减1表示出栈 */
    return s->stack[s->top+1];        /* 返回原栈顶元素的值 */
}

/* 4.读取栈顶元素的值 */
elemType peek(struct stack *s)
{
    /* 若栈空则退出运行 */
    if(s->top == -1){
        printf("栈空，无元素可读取！ ");
        exit(1);
    }
    return s->stack[s->top];        /* 返回原栈顶元素的值 */ 
}

/* 5.判断s是否为空，若是则返回1表示真，否则返回0表示假 */
int emptyStack(struct stack *s)
{
    if(s->top == -1){
        return 1;
    }else{
        return 0;
    }
}

/* 6.清除栈s中的所有元素，释放动态存储空间 */
void clearStack(struct stack *s)
{
    if(s->stack){
        free(s->stack);
        s->stack = NULL;
        s->top = -1;
        s->maxSize = 0;
    }
    return;
}

/************************************************************************/

int main()
{
    struct stack s;
    int a[8] = {3, 8, 5, 17, 9, 30, 15, 22};
    int i;
    initStack(&s, 5);
    for(i = 0; i < 8; i++){
        push(&s, a[i]);
    }
    printf("%d ", pop(&s)); printf("%d  ", pop(&s));
    push(&s, 68);
    printf("%d ", peek(&s));    printf("%d  ", pop(&s));
    while(!emptyStack(&s)){
        printf("%d ", pop(&s));
    }
    printf(" ");
    clearStack(&s);
    system("pause");
    return 0;
}

 

 

/************************************************************************/
/*                      以下是关于栈链接存储操作的6种算法                 */
/************************************************************************/

struct sNode{
    elemType data;
    struct sNode *next;
};

/* 1.初始化链栈为空 */
void initStack(struct sNode* *hs)
{
    *hs = NULL;    
    return;
}

/* 2.向链中插入一个元素（入栈） */
void push(struct sNode* *hs, elemType x)
{
    struct sNode *newP;
    newP = malloc(sizeof(struct sNode));
    if(newP == NULL){
        printf("内在空间分配失败！ ");
        exit(1);
    }
    newP->data = x;        /* 给新分配的结点赋值 */
    /* 向栈顶插入新结点 */
    newP->next = *hs;
    *hs = newP;
    return;
}

/* 3.从链栈中删除一个元素并返回它（出栈） */
elemType pop(struct sNode* *hs)
{
    struct sNode *p;
    elemType temp;
    if(*hs == NULL){
        printf("栈空无法删除！ ");
        exit(1);
    }
    /* 暂存栈顶结点指针，并使栈顶指针指向下一个结点 */
    p = *hs;
    *hs = p->next;
    /* 暂存原栈顶元素以便返回，同时回收原栈顶结点 */
    temp = p->data;
    free(p);
    return temp;        /* 返回原栈顶元素 */
}

/* 4.读取栈顶元素 */
elemType peek(struct sNode* *hs)
{
    /* 对于空栈则退出运行 */
    if(*hs == NULL){
        printf("栈空，无栈顶元素！ ");
        exit(1);
    }
    return (*hs)->data;        /* 返回栈顶结点的值 */
}

/* 5.判断链栈是否为空，为空返回1，否则返回0 */
int emptyStack(struct sNode* *hs)
{
    if(*hs == NULL){
        return 1;
    }else{
        return 0;
    }
}

/* 6.清除链栈为空 */
void clearStack(struct sNode* *hs)
{
    struct sNode *cp, *np;
    cp = *hs;        /* 使cp指向栈顶结点 */
    /* 从栈底依次删除每个结点 */
    while(cp != NULL){
        np = cp->next;
        free(cp);
        cp = np;
    }
    *hs = NULL;        /* 置链栈为空 */
    return;
}