数据结构::栈

栈
限定仅在表尾进行 插入 或 删除 操作的线性表。
栈顶：表尾端。
栈底：表头端。
应用：数制转换，行编辑程序，树的遍历等。
凡是对数据的处理具有“后进先出/LIFO”的特点，都可以用栈这种数据结构来操作。

通过链表实现栈

/*=========================================================================
  工程名称：    通过链表实现栈：后进先出
  组成文件：    main.c
  功能描述：    通过链表管理栈，通过栈顶指针进行进出栈操作
  程序分析：    有关栈的链表，它的指针域应该是向前指的，即通过最后节点往前遍历    
=========================================================================*/
 
//进栈算法
#include "stdio.h"
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *link;
}NODE;
 
//栈底
NODE *top;
 
int push(int x)
{   
    NODE *temp = (NODE *) malloc(sizeof(NODE));
    //将数据插入节点
    temp->data=x;                
    
    //得到上一个节点地址，第一次top为NULL所以栈底的link指向NULL
    temp->link = top;        
    top = temp;
    return 0;
}
 
int pop(int *py)
{
    NODE *temp=top;
 
    if (top == NULL)                //判断是否栈空
    {
        printf("stach empty!");
        return -1;
    }
    else
    {
        *py = top->data;        //将栈中数据读出
        top = top->link;        //如果是栈底，则link=top=NULL
        free (temp);
        return 0;
    }
 
}
int main()
{
    int result,y;
    int i,op,value;
 
    top=NULL;
     while(1)
     {
        printf("1:push 2:pop 3:clearstack input:");
        scanf("%d",&op);
        switch(op)
        {
            case 1:
                scanf("%d",&value);
                if(push(value) == -1)
                    printf("insert error
");
                break;
            case 2:
                if(pop(&y) == -1)
                    printf("pop error
");
                printf("%d
",y);
                break;
            case 3:
                break;
            default:
                break;
        }
        printf("top = %d
",top);
    }
}