【Data】栈（1）

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<stdio.h>
#include<malloc.h>
#define STACK_INIT_SIZE 1
#define STACKINCREMENT 10
typedef 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 <iostream>
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"<<endl;
    return top;

}
//出栈函数
int Pop(LinkStack top)
{
    StackNode * temp;
    int t;
    if(StackEmpty(top))
        cout<<"the stack is empty"<<endl;
    else
    {
        temp=top->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"<<endl;
    else
    {
        while(top->next!=NULL)
        {
            cout<<top->next->data<<"  ";
            top=top->next;
        }
    }
}
//取栈顶元素
int StackTop(LinkStack top)
{
      if(StackEmpty(top))
           cout<<"the Stack is empty"<<endl;
      return top->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------退出程序"<<endl
        <<"1------入栈操作"<<endl
        <<"2------出栈操作"<<endl
        <<"3------取栈顶元素"<<endl
        <<"4------判断栈是否为空"<<endl
        <<"5------返回栈的元素个数"<<endl
        <<"6------####初始化栈###"<<endl
        <<"7------显示栈"<<endl
        <<"8------销毁栈"<<endl
        <<"9------退出程序"<<endl;
}
int main()
{
    LinkStack top;
    top = (LinkStack)malloc(sizeof(StackNode));    //注意    

    instruction();
    int i,value;
        cin>>i;
    while(i)    //输入0也可以退出循环
    {
        switch(i)
        {
            
            case 1:        //入栈操作
                InitStack(top);
                cout<<"Input an integer"<<endl;
                cin>>value;
                while(value!=0)
                {
                    Push(top,value);    //入栈
                    cin>>value;
                }
                PrintStack(top);    //打印栈
                cout<<endl;
                break;
            case 2:        //出栈操作
                if(top->next!=NULL)
                    cout<<"the popped value is:"<<Pop(top)<<endl;    //出栈
                else
                    cout<<"the stack is empty"<<endl;
                break;
            case 3:        //取栈顶元素
                if(StackEmpty(top)==1)
                    cout<<"is empty"<<endl;
                else
                    cout<<StackTop(top)<<endl;
                break;
            case 4:        //判断栈是否为空
                if(StackEmpty(top)==1)
                    cout<<"is empty"<<endl;
                else
                    cout<<"is not empty"<<endl;
                break;
            case 5:        //返回栈的元素个数
                if(StackEmpty(top)==1)
                    cout<<"is empty"<<endl;
                cout<<StackLen(top)<<endl;
                cout<<endl;
                break;
            case 6:        //初始化栈
                InitStack(top);break;
            case 7:        //显示栈
                PrintStack(top);
                cout<<endl;break;
            case 8:        //销毁栈
                DestroyStack(top);
                cout<<endl;break;
            case 9:
                goto end;
            default:
                cout<<"Invalid choice"<<endl;break;
        }
        instruction();    
        cin>>i;
    }
    end:;    //利用goto语句退出循环
    return 0;
}

//简短的出栈入栈函数，数组实现
/*
    #include <stdio.h>
    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() ) ;
    }
*/

原文链接: https://www.cnblogs.com/claire-study-note/archive/2013/05/08/3066894.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/87706

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

【Data】栈（1）

相关推荐