C语言算法:栈

时间：2010-11-21 来源：osullishuai80

一、栈的定义
(1)栈:限定只能在表的一端进行插入和删除的特殊的线性表(LIFO/FILO).
(2)LIFO:last in first out，后进先出
   FILO:first in last out，先进后出
(3)栈有两端，分别是栈顶(top)和栈底(bottom).

   top:允许插入和删除的一端.
   bottom:不允许插入和删除的一端.
   假定栈S=(A1,A2,...,An);则A1就是栈底元素，An就是栈顶元素. 二、栈的操作
(1)进栈
(2)出栈
(3)判断栈满
(4)判断栈空
【attention】凡是对数据的处理据有"后进先出"的特点，都可以用栈这种数据接哦股进行操作. 三、顺序栈
(1)顺序栈:用顺序存储结构表示的栈.
(2)顺序栈利用一组连续的存储单元(如数组)存放自栈底到栈顶的数据元素，通常用一维数组设计栈.
【约定】top始终指向新数据元素将要存放的位置
       1.当top=0时，表示栈空.当栈空时，若要退栈，称作"下溢".
       2.当top=stacksize时，表示栈满.当栈满时，若还有元素要进栈，栈将溢出，称作"上溢".
       3.常量stacksize表示栈的最大容量.
       4.注意，无论上溢还是下溢，程序中都要显示信息，以便处理.
【应用】数制转换、行编辑程序、树的遍历等
【例程】利用栈的思想进行数制转换
        #include <stdio.h>
        #include <stdlib.h>
        #define STACK_SIZE 10             /*栈的最大容量*/
        static int top=0;                /*栈中新元素可以存放的位置*/
        static int stack[STACK_SIZE]={0};   /*用一维数组模拟栈*/
        /*压栈函数*/
        int push(int argc)
       {
          if(top==STACK_SIZE)
         {
             printf("stack is full\n");
             return -1;
         }
         else
         {
             stack[top]=argc;
             top++;
         }
         return 0;
       }
       /*弹栈函数*/
      int pop(void)
      {
         if(top==0)
        {
            printf("stack is empty");
            return -1;
        }
        else
        {
            top--;
            return stack[top];
        }
      }
      /*栈为空函数*/
      int empty()
     {
         return (top==0?1:0);
     }
     /*栈为满函数*/
     int full()
     {
         return (top==STACK_SIZE?1:0);
     }      int main(int argc,char *argv[])
     {
         int temp;
         int ret;
         int var;
         int format;          printf("需要转换的数:");
         scanf("%d",&var);
         printf("需要转换进制:");
         scanf("%d",&format);
         printf("%d的%d进制数是:",var,format);
         do
        {
           temp=var%format;
            if(0==full())
               push(temp);
            var /= format;
        }
        while(var!=0);
        while(empty()==0)
        {
            ret=pop();
            printf("%d",ret);
        }
        printf("\n");

        return 0;
     }
    【执行结果】:
         需要转换的数:353
         需要转换进制:8
         353的8进制数是:541

         需要转换的数:353
         需要转换进制:2
         353的2进制数是:101100001