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

继续发水文,今天说说“栈”(stack)这一数据结构。

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

stack-1

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

stack-push
压入元素

 

stack-pop
弹出元素

接下来就是代码,用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;
}

 

 

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

发布者

hcl

TechOtaku 站长。

《数据结构“栈”简介与C语言实现》上有3条评论

  1. 您好,您的程序在判满时明显有问题,您实现的应该是空递增栈(姑且这么认为吧),简单的入栈出栈就出错了。

    Google Chrome 40.0.2214.111 Google Chrome 40.0.2214.111 Mac OS X  10.9.5 Mac OS X 10.9.5
    1. 您说的问题应该是指判断栈满的代码有问题(调试了一下确实如此),总之感谢大神指导,我当初写的时候加上写完调试的时候没有注意到这一点,感谢指出。

      Google Chrome 42.0.2305.3 Google Chrome 42.0.2305.3 Windows 8.1 x64 Edition Windows 8.1 x64 Edition

发表评论

电子邮件地址不会被公开。 必填项已用*标注