数据结构“栈”简介与C语言实现

继续发水文，今天说说“栈”（stack）这一数据结构。

栈应该算是数据结构中比较简单的一种，其原理一句话就可以解释清楚，即元素是“先进后出”的。如果把栈想成一摞书，就很好理解了。每次放书都只能放到最上面，而每次取书也只能取最上面那一本。当然书架的空间是有限制的，当你需要放书的时候你需要判断这摞书是否到顶了，如果到顶了你就没有办法再往上面放了；而取书的时候，如果这摞书已经空了，就不能取书了。栈同样有自己的限制。为了更加方便地去判断这摞书还能不能放或者取，我们需要记录书的数目。同样，我们在栈里也需要一个记录栈中元素数目的变量，我们称之为栈顶（top）。

这样，我们就有了构建一个栈所需的必备的结构，接下来，我们需要明确的是对栈的操作。栈的两个基本操作分别是——压入（Push）和弹出（Pop），即元素进栈和元素出栈。每进入一个元素，栈顶+1，每弹出一个元素栈顶-1，当然这其中还需要增加对栈空与栈满的判断，这实际上已经很容易做到了。

接下来就是代码，用C语言实现，在Dev-C++ 5.7.1 + Windows 8.1 x64下面编译通过。

#include <stdio.h>
#define STACKLEN 50        //Define the length of the stack

/* Define the structure */

typedef struct _stack
{
    int array[STACKLEN];
    int top; 
} list;


/***********************************************************
    Function Name: init_stack
    Function Description: Initialize a stack.
    Inputs: Pointer of variable of structure _stack. Eg. init_stack(&example);
    Outputs: None.
    Notes: None.
************************************************************/ 


void init_stack(list *seqstack){
    int i=0;
    for (; i < STACKLEN; ++i)
    {
        seqstack->array[i]=0;
    }
    seqstack->top=0;
}

/***********************************************************
    Function Name: check_stack_empty
    Function Description: Check a stack if it is empty.
    Inputs: Pointer of variable of structure _stack. Eg. check_stack_empty(&example);
    Outputs: 1 means empty; 0 means not empty.
    Notes: None.
************************************************************/ 

int check_stack_empty(list *seqstack){
    if (seqstack->top==0){
        return 1;
    }else {
        return 0;
    }

}

/***********************************************************
    Function Name: check_stack_full
    Function Description: Check a stack if it is full.
    Inputs: Pointer of variable of structure _stack. Eg. check_stack_full(&example);
    Outputs: 1 means full; 0 means not full.
    Notes: None.
************************************************************/ 

int check_stack_full(list *seqstack){
    if (seqstack->top==STACKLEN-1){
        return 1;
    }else {
        return 0;
    }

}

/***********************************************************
    Function Name: push
    Function Description: Push an element into a stack.
    Inputs: Pointer of variable of structure _stack and value to input. 
            Eg. push(&example,value);
    Outputs: 1 means full and exit ; 0 means not full and success.
    Notes: Use Function check_stack_full.
************************************************************/ 

int push(list *seqstack,int x){
    if(check_stack_full(seqstack)){
        return 1;
    }else{
        
        seqstack->array[seqstack->top]=x;
        seqstack->top+=1;
        return 0;
    }
    
}

/***********************************************************
    Function Name: pop
    Function Description: Pop an element from a stack.
    Inputs: Pointer of variable of structure _stack. 
            Eg. pop(&example);
    Outputs: 1 means empty and exit ; 0 means not empty and success.
    Notes: Use Function check_stack_empty.
************************************************************/ 

int pop(list *seqstack){
    if (check_stack_empty(seqstack))
    {
        return 1;
    } else{
        seqstack->array[seqstack->top]=0;
        seqstack->top-=1;
        return 0;
    }
}

/***********************************************************
    Function Name: print_stack
    Function Description: Print all elements of a stack.
    Inputs: Pointer of variable of structure _stack and the length to print. 
            Eg. print_stack(&example,length);
    Outputs: None.
    Notes: Use Function check_stack_empty.
************************************************************/ 

void print_stack(list *seqstack,int l){
    int i=l-1;
     if (check_stack_empty(seqstack)){
        printf("========STACK========\n");
        printf("The stack is empty.\n");
        printf("=====================\n");
     }else{
        printf("========STACK========\n");
        for (; i>=0; i--)
            {
                printf("%d\n",seqstack->array[i]);
            }
            if (check_stack_full(seqstack)){
                printf("The stack is full.\n");
            }
        printf("=====================\n");
     }
}



int main(int argc, char const *argv[])
{
    int i=0;
    int cnt;
    list seqstack;
    int input=0;
    init_stack(&seqstack);
    int choice=0;
    printf("Now initializing the stack.(The stack length is 50.)\n");
    printf("Please input length of the stack:");
    scanf("%d",&cnt);
    do{
        printf("=========MENU========\n");
        printf("1:Push a element into the stack.\n");
        printf("2:Pop a element of the stack.\n");
        printf("3:Print all the element of the stack.\n");
        printf("0:Do nothing.\n");
        printf("Please select the option:");
        scanf("%d",&choice);
        switch(choice){
            case 1:{
                printf("Please input a number:");
                scanf("%d",&input);
                if (push(&seqstack,input))
                {
                    printf("The stack is FULL!\n");
                }else {
                    printf("Push success!\n");
                }
            };
            break;
            case 2:{
                if (pop(&seqstack))
                {
                    printf("The stack is EMPTY!\n");
                }else {
                    printf("Pop success!\n");
                }
            };
            break;
            case 3:{
                print_stack(&seqstack,cnt);
            };
            break;

        }
    }while (choice!=0);
    return 0;
}

代码中我把判断栈空或者栈满分别用一个函数来实现，压入弹出也写成了一个函数，可以方便未来的调用。当然这个例子也仅仅是实现一个栈的基本功能，仅仅是数字的输入输出，但是还是能够帮忙理解栈的原理。栈多应用于四则运算表达式的解析，当然还是这里留个坑。