栈

        栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作“栈顶(top)”，不允许插入和删除的另一端称作“栈底(bottom)”。

      通常称往栈顶插入元素的操作为“入栈”，称删除栈顶元素的操作为“出栈”。因为后入栈的元素先于先入栈的元素出栈，故被称为是一种“后进先出”的结构，因此又称 LIFO 表（Last In First Out的缩写）。

      和线性表类似，栈也有两种存储表示：顺序栈和链栈。

　　顺序存储结构简称为顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间。用图表示顺序栈如下：

 

链栈即为栈的链式存储结构。

顺序栈的实现依靠数组，而数组需要事先声明长度，一次性地静态地分配内存空间。这样就给我们带来很多不便。因为我们事先并不能精确地估计栈所需的大小，估计大了浪费空间，估计小了后果就严重了，导致程序无法正常运行。所以我们通常使用链栈这种数据结构。

链栈用链表作为存储结构，栈初始化时仅需给栈顶指针分配内存空间，而后每当有数据入栈时再为该数据分配空间，这样实现了内存空间的动态分配。理论上栈的大小可以是无限大的（小心撑爆你的内存 o(∩_∩)o）。不存在顺序栈的诸多问题。

模板：

#include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 struct node
 {
     int data;
     struct node *next;
 };
 int push(node *top,int e)           //进栈
 {
     node *p;
     p=(node *)malloc(sizeof(node));
     p->data=e;
     p->next=top->next;
     top->next=p;
     return (1);
 }
 int gettop(node *top)              //栈顶元素
 {
     if(top->next==NULL)
     {
         printf("栈是空的
");
         return 0;
     }
     return (top->next->data);
 }
 int pop(node *top)             //出栈
 {
     node *p;
     int y;
     p=top->next;
     if(p==NULL)
     {
         printf("出栈失败，栈是空栈
");
         return (0);
     }
     y=p->data;
     top->next=p->next;
     free(p);
     return (y);
 }
 int main()
 {
     node *top;
     int e,a;
     top=(node *)malloc(sizeof(node));
     if(!top)
     printf("error
");
     top->next=NULL;
     printf("   /***********************/
");
     printf("   /*  链栈的表示和实现   */
");
     printf("   /***********************/

");
     do
     {
         printf("   /**********************/
");
         printf("   /*       菜单         */
");
         printf("       1、进栈
       2、取栈顶元素
       3、出栈
       0、结束
");
         printf("   /**********************/
");
         printf("   请输入你的选择：
");
         scanf("%d",&a);
         switch(a)
         {
             case 1:{
                      printf("请输入你要进栈的元素：
");
                       scanf("%d",&e);
                       push(top,e);
                       break;
                     }
             case 2:
             {
                 printf("栈顶元素为：%d
",gettop(top));
                 break;
             }
             case 3:
             {
                 printf("出栈返回值为%d:
",pop(top));
                 break;
             }
             default:
             {
                 printf("输入不符合要求，请重新输入：
");
                 break;
             }
         }
     }while(a!=0);
     return 0;
 }
 

例题：（sdut   1479）

   

数据结构实验之栈：行编辑器

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

 一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。 

 

由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符"#"，以表示前一个字符无效； 

 

如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符"@"，以表示当前行中的字符均无效。 

 

如果已经在行首继续输入'#'符号无效。 

输入

 输入一个多行的字符序列。但行字符总数（包含退格符和退行符）不大于250。 

输出

 按照上述说明得到的输出。 

示例输入

whli##ilr#e(s#*s)
outcha@putchar(*s=#++);

示例输出

while(*s)
putchar(*s++);

#include<stdio.h>   
 #include<string.h>   
 #include<stdlib.h>   
 typedef struct Node   
 {   
     char data;   
     struct Node *next;   
 }node;   
 void push(node *top,char e)   
 {   
     node *p;   
     p=(node *)malloc(sizeof(node));   
     p->data=e;   
     p->next=top->next;   
     top->next=p;   
 }   
 void  pop(node *top)   
 {   
     node *p;   
     p=top->next;   
     top->next=p->next;   
     free(p);   
 }   
 void list(node *top)   
 {   
     node *p;   
     p=top->next;   
     while(p->next!=NULL)   
     {   
         printf("%c",p->data);   
         p=p->next;   
     }   
      printf("%c",p->data);   
 }   
 node *popt(node *top)   
 {   
     node *p,*q;   
     p=top->next;   
     top->next=NULL;   
     q=p->next;   
     while(p!=NULL)   
     {   
         p->next=top->next;   
         top->next=p;   
         p=q;   
         if(q!=NULL) q=q->next;   
     }   
     return top;   
 }   
 int main()   
 {   
     node *top;   
     int len,i;   
     char b[10000];   
     while(~scanf("%s",b))   
     {   
         top=(node *)malloc(sizeof(node));   
         top->next=NULL;   
         len=strlen(b);   
         for(i=0;i<len;i++)   
         {   
             if(b[i]=='@')   
               top->next=NULL;   
             else if(b[i]=='#')   
             {   
                 if(top->next!=NULL)   
                    pop(top);   
             }   
              else push(top,b[i]);   
         }   
         if(top->next!=NULL)   
         {   
             top=popt(top);   
            list(top);   
             printf("
");   
         }   
     }   
     return 0;   
 }