堆棧的多種實作方式

何謂堆棧

　　堆棧是一種隻能在一端進行插入或删除操作的線性表，屬于邏輯結構。有數組與指針兩種實作方式。

　　堆棧的主要特點為後進先出，每次進棧的新元素都在原來的棧頂元素之上，每次出棧的元素也是原來的棧頂元素。如下圖：

　　下面給出堆棧的兩種實作方式。

堆棧之指針實作：

#include<cstdio>
#include<cstdlib>
using namespace std;

typedef struct Stack *Link;
typedef struct Stack Snode;

struct Stack
{
    int data;
    Link next;
};

Link init()//初始化棧并傳回頭指針 
{
    Link p;
    p=NULL;
    return p;
}

Link push(Link Head,int x)//入棧 
{
    Link p;
    p=(Snode*)malloc(sizeof(Snode));
    if(p==NULL)
    {
        printf("\nMemory Error!\n");
        return Head;
    }
    else {
        p->data=x;
        p->next=Head;
        return p;
    }
}
Link pop(Link Head)//出棧 
{
    Link p=Head; 
    if(p==NULL)
    {
        printf("\nStack is Empty!\n");
        return Head;
    }
    Head=Head->next;
    free(p);
    return Head;
}
int gettop(Link Head)//取棧頂元素的值 
{
    if(Head==NULL)
    {
        printf("\nStack is Empty!\n");
        return -1;
    }
    return Head->data;
}

bool empty(Link Head)
{
    if(Head==NULL) return 1;
    return 0;
}

void display(Link Head)
{
    if(Head==NULL)
    {
        printf("\nStack is Empty!\n");
        return;
    }
    Link p;
    p=Head;
    while(p!=NULL)
    {
        printf("%d",p->data);
        p=p->next;
    }
    return;
}

int lenth(Link Head)
{
    Link p=Head;
    int sum=0;
    while(p!=NULL)
    {
        sum++;
        p=p->next;
    }
    return sum;
}
Link Set_NULL(Link Head)
{
    if(Head==NULL)
    {
        printf("\nStack is Already Empty!\n");
        return Head;
    }
    Link p;
    p=Head;
    while(Head!=NULL)
    {
        p=Head;
        Head=Head->next;
        free(p);
    }
    return Head;
}
int main()
{ 
  int i,x;
  Link head1;
  head1=init();
  while(i!=6)
  {
    system("cls");
    printf("\n 1.Input a stack data");
    printf("\n 2.Output a stack data");
    printf("\n 3.Empty or Not");
    printf("\n 4.Display a top of stack");
    printf("\n 5.Display the lenth of stack");
    printf("\n 6.Exit and Free Stack\n");
    printf("\n  Stack is:  ");
    display(head1);
    printf("\n");

    scanf("%d",&i);
    switch(i)
    {
      case 1: while(1)
              {     
                system("cls");
                printf("\n -.Input a stack data");
                printf("\n -.Output a stack data");
                printf("\n -.Empty or Not");
                printf("\n -.Display a top of stack");
                printf("\n -.Display the lenth of stack");
                printf("\n -.Exit and Free Stack\n");
                printf("\n  Stack is:  ");
                display(head1);
                printf("\n");
                printf("\ninput a number: until enter -1:\n");
                scanf("%d",&x);
                if(x==-1)
                  break;
                head1=push(head1,x);
              }
              break;
     case 2: head1=pop(head1);
             break;
     case 3: if(empty(head1))
               printf("\nStack is empty\n");
             else
               printf("\nStack is not empty\n");
             system("pause");
             break;
     case 4: printf("\n The top is  %d\n",gettop(head1));
             system("pause");
             break;
     case 5: printf("\n The length of stack is %d\n",lenth(head1));
             system("pause");
             break;
    }
  }
  system("cls");;
  head1=Set_NULL(head1);
  display(head1);
  system("pause");
  return 0;
}      

View Code

 堆棧之數組實作：

//簡單數組模拟棧 
#include<iostream>
#include<cstdlib>
#define MAXN 1000//棧能容納的最多元素個數
using namespace std;

int stack[MAXN];
int top = -1;//初始化棧頂指針為-1 

int pop()//棧頂元素出棧并擷取出棧的元素值 
{
  int temp;
  if(top<0)
  {
    cout<<"\nThe stack is empty!\n";
    return -1;
  }
  temp=stack[top--];
  return temp;
}

void push(int value)
{ 
  if(top>=MAXN)
    cout<<"\nThe stack is full!\n";
  else
    stack[++top]=value;
}

void display()//顯示棧中元素
{
  for(int tmp = top ; tmp >= 0 ; -- tmp)
    cout<<stack[tmp]<<" ";
  cout<<"\n";
}

int main()
{
  int ins;
  while(1)
  {
    cout<<"Please enter a value,(0=exit,-1=pop)\n";
    cin>>ins;
    if(ins==0)
      exit(0);
    else if(ins!=-1)
      push(ins);
    else if(ins==-1)
      pop();
    system("cls");
    display();
  }  
  return 0;
}      

View Code

　　其實，堆棧還有其他實作方式，我們可以通過字元串來實作字元棧呀！此時的插入與删除操作隻需對串首（尾）進行添加或删除字元就OK了！

　　就這些了，若有不足，請指正！