数据结构-栈

栈的实现及其应用

 

1, 数组实现的简单的栈，摘自《C程序设计语言》

 

/*
 ...    <----100
|   |
-----
|   |
-----
|   | 3  <----sp
-----
|0.3| 2
-----
|0.2| 1
-----
|0.1| 0
-----
*/

#define MAXVAL 100          //栈最大深度

static int sp = 0;          //下一个空栈的位置
static double val[MAXVAL];

void push(double f)
{
    if (sp < MAXVAL)   
        val[sp++] = f;
    else
        printf("error: stack full, can't push %g\n", f);
}

 

double pop(void)
{
    if (sp > 0) {
        return val[--sp];
    } else {
        printf("error: staack empty");
        return 0;
    }
}

 

 

2，栈的动态数组实现

 

struct stack_record {
    int maxlen;     //栈最大的深度
    int sp;         //栈顶指针
    int *arr;       //栈体
};

typedef struct stack_record Stack;


Stack *create(int max_num)
{
    Stack *ss;

    ss = (Stack *)malloc(sizeof(Stack));   
    if (!ss) {
        return NULL;
    }
    ss->arr = (int *)malloc(max_num*sizeof(int));
    if (!ss->arr)  
        return NULL;
    ss->sp = 0;             //表示空栈
    ss->maxlen = max_num;  
    return ss;
}



int push(Stack *s, int val)
{
    assert(s && s->arr);

    if (s->sp < s->maxlen) {
        s->arr[s->sp++] = val; 
        return 0;
    } else {
        printf("error: stack full!\n");
        return -1; 
    }
}


int pop(Stack *s)
{
    assert(s && s->arr);
   
    if (s->sp > 0) {            //必须>0，若=0，表示空栈
        return s->arr[--s->sp];
    } else {
        return -1;
    }
}

void print_stack(Stack *s)
{
    assert(s && s->arr);
    int i; 
   
    for (i = 0; i < s->sp; i++) {
        printf("%d ", s->arr[i]);
    }
}

//测试例程
#define MAXLEN 20
int main(void)
{
    char a[MAXLEN] = {'\0'};
    Stack *s;
    char *p;
    int v;

    fgets(a, MAXLEN, stdin);
    a[strlen(a)-1] = '\0';
    printf("a=[%s]\n", a);

    s = create(MAXLEN);
    if (!s) {
        printf("create stack error!\n");
        return 1;
    }

    p = a; 
    while ('\0' != *p) {
        push(s, *p);
        p++;
    }
       
    printf("\n-----pop-----\n");
    while (-1 != (v=pop(s))) {
        printf("%c ", v);
    }
    printf("\nend\n");

    return 0;
}

 

3, 栈的链表实现

/*
 * 栈的链表实现
 * 其算法思想是：
 *      压栈：从链表的头指针添加结点
 *      出栈：从链表的头结点删除结点，并弹出该结点的值
 *
 */
#include "all.h"


struct node {
    int data;
    struct node *next;
};

typedef struct node Stack;

/*
 * 创建一个栈 : 实际上是创建一个链表的头结点
 */
Stack *creat_stack(void)
{
    Stack *s;

    s = (Stack *)malloc(sizeof(Stack));
    if (!s) {
        fprintf(stderr, "malloc error!\n");
        return NULL;
    }
    s->next = NULL;
    return s;
}


int is_empty(Stack *s)
{
    return s->next == NULL;
}


/*
 * 从链表的头部插入来实现压栈
 */
void push(Stack *s, int val)
{
    struct node *node;
   
    node = (struct node *)malloc(sizeof(struct node));
    if (!node) {
        fprintf(stderr, "malloc error!\n");
        return ;   
    }

    node->data = val;
    node->next = s->next;   //从链表头部插入
    s->next = node;
}


/*
 * 返回链表的第一个元素:出栈
 */
int pop(Stack *s)
{
    Stack *sp;
    int val;

    if (is_empty(s))        //空栈
        return -1;
   
    sp = s->next;  
    s->next = s->next->next;
    val = sp->data;
    free(sp);
    return val;
}

//测试例程
#define MAXLEN 20

int main(void)
{
    char a[MAXLEN] = {'\0'};
    Stack *s;
    char *p;
    int v;

    fgets(a, MAXLEN, stdin);
    a[strlen(a)-1] = '\0';
    printf("a=[%s]\n", a);

    s = creat_stack();
    if (!s) {
        printf("create stack error!\n");
        return 1;
    }

    p = a; 
    while ('\0' != *p) {
        push(s, *p);
        p++;
    }
       
    printf("\n-----pop-----\n");
    while (-1 != (v=pop(s))) {
        printf("%c ", v);
    }
    printf("\nend\n");

    return 0;
}

4,栈的应用