1、栈的定义

 

栈是限定仅在表尾进行插入和删除操作的

线性表。

栈的表尾称为栈顶，表头称为栈底，不含元素的栈称为空栈。

 

 

 

2、栈的抽象数据类型定义：

ADT Stack{

数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}

数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n }

           约定an端为栈顶，a1端为栈底。

基本操作：

   InitStack( &S )

     操作结果：构造一个空栈S。

   DestroyStack ( &S )

     初始条件：栈S已存在。

     操作结果：销毁栈S。

   ClearStack( &S )

     初始条件：栈S已存在。

     操作结果：将S清为空栈。

   StackEmpty( S )

     初始条件：栈S已存在。

     操作结果：若S为空栈，则返回TRUE，否则返回FALSE。

   StackLength( S )

     初始条件：栈S已存在。

     操作结果：返回S的数据元素个数，即栈的长度。

   GetTop( S, &e )

     初始条件：栈S已存在且非空。

     操作结果：用e返回S的栈顶元素。

   Push( &S, e )

     初始条件：栈S已存在。

     操作结果：插入元素e为新的栈顶元素。

   Pop( &S, &e )

     初始条件：栈S已存在且非空。

     操作结果：删除S的栈顶元素，并用e返回其值。

    VisitStack( S, visit() )

     初始条件：栈S已存在且非空。

     操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

}ADT Stack 

 

 

 

3、栈的存储方式：

（1）顺序栈：利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素

在顺序栈中的位置。

（2）链栈：利用链表实现  

（原来还有这种！孤陋寡闻了）

 

顺序栈的C语言表示

#include
      
       #include
       
        #define STACK_INIT_SIZE 1#define STACKINCREMENT 10typedef char ElemType;struct SqStack{     ElemType *elem;     ElemType   *top;     int stacksize;};int InitStack(struct SqStack *S){     S->elem=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));     if(!S->elem)     {         printf("初始化栈失败");          return 0;     }     else     {         S->top=S->elem;         S->stacksize= STACK_INIT_SIZE;         printf("初始化栈成功\n");         return 1;     }}int Push(struct SqStack *S,ElemType x){      if(S->top-S->elem>=S->stacksize)      {         S->elem=(ElemType *)realloc(S->elem,(S->stacksize+STACKINCREMENT) * sizeof(ElemType));         if(!S->elem)         {      printf("开辟空间失败\n");              return 0;         }          else          {             S->top=S->elem+S->stacksize;             S->stacksize+=STACKINCREMENT;          }     }     *S->top=x;     S->top++;     return x;}int Pop(struct SqStack *S,ElemType x){     if(S->top==S->elem)     {         printf("栈空\n");         return 0;     }     else     {            S->top--;         x=*S->top;         return x;     }}int GetTop(struct SqStack *S,ElemType x){     if(S->top==S->elem)     {         printf("栈空\n");         return 0;     }     else     {         x=*(S->top-1);         return x;     }}int StackLength(struct SqStack *S){     int n;     n=S->top-S->elem;     return(n);}void StackEmpty(struct SqStack *S){     if(S->top==S->elem)             printf("栈为空\n");     else         printf("栈不为空\n");}int VisitStack(struct SqStack *S){     int k=0;     while(S->top!=S->elem)     {         --S->top;         k++;         printf("%c ",*S->top);     }         S->top+=k;         return 1;}int ClearStack(struct SqStack *S){   if(S->top==S->elem)       return 0;   else   {   S->top=S->elem;      return 1;   }}int DestroyStack(struct SqStack *S){     free(S->elem);     S->elem=NULL;     S->top=NULL;     S->stacksize=0;     return 1;}void main(){     int y;     struct SqStack A;     ElemType x=0;     ElemType e;     int cmd;     printf("*******************************************************************************\n");     printf("1－初始化栈      2－进栈         3－取栈顶元素       4－求栈长     5－销毁栈\n");     printf("6－判空          7－遍历栈       8－出栈             9－清空栈     0-退出\n");     printf("*******************************************************************************\n");  do{     printf("enter your choice ");     scanf("%d",&cmd);      e=getchar();     switch(cmd)     {case 1:   InitStack(&A);              break;     case 2:   printf("e=");              e=getchar();              y=Push(&A,e);printf("进栈元素为>>%c\n",y);              break;     case 3:   y=GetTop(&A,x);              if(!y)              printf("没有栈顶元素>>\n");              else              printf("栈顶元素为>>%c\n",y);break;     case 4:   y=StackLength(&A);              printf("栈中元素个数为>>%d\n",y);break;     case 5:   if(DestroyStack(&A));              printf("栈销毁成功>>\n");break;     case 6:   StackEmpty(&A);break;     case 7:   printf("出栈序列为>>");              VisitStack(&A);              printf("\n");              break;     case 8:   y=Pop(&A,x);              if(!y)              printf("没有栈顶元素可出>>\n");              else              printf("出栈元素为>>%c\n",y);               break;     case 9:   y=ClearStack(&A);              if(!y)                  printf("栈本身为空>>\n");              else                   printf("栈成功清空>>\n");              break;     default: break;     }}while(cmd!=0);}
       
      

　　链栈的C++实现：

#include 
      
       using namespace std;typedef struct stacknode{    int data;    struct stacknode * next;}StackNode,* LinkStack;//判栈空int StackEmpty(LinkStack top){      if(top->next==NULL)          return 1;      else          return 0;}//入栈函数LinkStack Push(LinkStack top,int value){    StackNode * newp = (StackNode *)malloc(sizeof(StackNode));    if(newp != NULL)    {        newp->data=value;        newp->next=top->next;        top->next=newp;    }    else        cout<<"No memory available"<
       
        next;        t=temp->data;        top->next = temp->next;        free(temp);    }    return t;}//打印函数void PrintStack(LinkStack top){    if(top->next==NULL)        cout<<"the stack is empty"<
        
         next!=NULL)        {            cout<
         
          next->data<<"  ";            top=top->next;        }    }}//取栈顶元素int StackTop(LinkStack top){      if(StackEmpty(top))           cout<<"the Stack is empty"<
          
           next->data;}//栈的长度int StackLen(LinkStack top){    int len=0;        while(top->next!=NULL)        {            len++;            top=top->next;        }    return len;}//销毁栈void DestroyStack(LinkStack top){     LinkStack q;     while(top)     {          q=top->next;          delete top;          top=q;     }     printf("销毁成功");}//栈初始化void InitStack(LinkStack top){      top->next=NULL; }//前导函数void instruction(void){    cout<<"0------退出程序"<
           
            <<"1------入栈操作"<
            
             <<"2------出栈操作"<
             
              <<"3------取栈顶元素"<
              
               <<"4------判断栈是否为空"<
               
                <<"5------返回栈的元素个数"<
                
                 <<"6------####初始化栈###"<
                 
                  <<"7------显示栈"<
                  
                   <<"8------销毁栈"<
                   
                    <<"9------退出程序"<
                    
                     >i; while(i) //输入0也可以退出循环 { switch(i) { case 1: //入栈操作 InitStack(top); cout<<"Input an integer"<
                     
                      >value; while(value!=0) { Push(top,value); //入栈 cin>>value; } PrintStack(top); //打印栈 cout<
                      
                       next!=NULL) cout<<"the popped value is:"<
                       
                        <
                        
                         >i; } end:; //利用goto语句退出循环 return 0;}//简短的出栈入栈函数，数组实现/* #include 
                         
                           int stack[100]; //100个栈空间 int* sp = stack; //栈指针指向栈底 #define push( i ) { *sp++ = i; } //push一个数 #define pop() (*--sp) //pop一个数并返回 int main() { int i; for ( i = 0; i < 10; ++i )//push 0~9 push( i ); for ( i = 0; i < 10; ++i )//输出9~0 printf( "%d ", pop() ) ; }*/