重構之路--代碼實作

git連結：

Operation3.1.1

代碼上次就已經實作了，這次加了一些新的功能，實作分數表達式。

棧

       棧是一種最常用的和最重要的資料結構，是一種隻能在一端進行插入或删除操作的線性表。表中允許進行插入、删除操作的一端稱為棧頂。棧頂目前位置是動态的，棧頂目前位置由一個稱為棧頂指針的位置訓示器表示。表的另一端稱為棧底。當棧中沒有資料元素時，稱為空棧，棧的插入操作通常稱為進棧或入棧，棧的删除操作通常稱為退棧或出棧。

       棧的主要特點是“後進先出”，即後入棧的元素先彈出。每次進棧的資料元素都放在原目前棧頂元素之前，成為新的棧頂元素，每次出棧的資料都是原目前棧頂元素。

棧的基本操作

• 初始化棧， init()
• 入棧，push()
• 出棧，pop()
• 取棧頂元素，gettop()
• 判斷棧是否為空 empty()
• 顯示棧元素 display()
• 釋放棧 setnull()

       當然，這些操作你可以直接用stl模闆，也可以自定義棧，比如數組仿真或者指針仿真。模闆的話可以自行百度，而我用的是數組仿真，下面例子就示範指針仿真的吧。

/*堆棧示範!*/
#include <iostream>
using namespace std;
typedef struct Stack *link;
typedef struct Stack Snode;

struct Stack
{
  int data;
  struct Stack *next;
};

link init()//初始化棧
{
  link p;
  p=NULL;
  return p;
}

link push(link Head,int x)//入棧
{
  link p;
  p=new Snode;
  if(p==NULL)
  {
    cout<<"\nMemory Error\n";
    return Head;
  }
  p->data=x;
  p->next=Head;
  return p;
}

link pop(link Head)//出棧
{
  link p;p=Head;
  if(p==NULL)
    cout<<"\nStack is Empty!\n";
  else
  {
    p=p->next;
    delete(Head);
  }
  return p;
}

link setnull(link Head)//釋放棧
{
  link p;p=Head;
  while(p!=NULL)
  {
    p=p->next;
    delete(Head);
    Head=p;
  }
  return Head;
}

int lenth(link Head)// 獲得棧内元素個數
{ 
  int len=0;
  link p;
  p=Head;
  while(p!=NULL)
  {
    len++;
    p=p->next;
  }
  return len;
}

int gettop(link Head)//獲得棧頂元素
{
  if(Head==NULL)
  {
    cout<<"\nStack is Empty!\n";
    return -1;
  }
  else
    return Head->data;
}

void display(link Head)//顯示棧内元素
{
  link p;p=Head;
  if(p==NULL)
    cout<<"\nStack is empty\n";
  else
    do
    {
       cout<<p->data<<" ";
       p=p->next;
    }while(p!=NULL);
}

int empty(link Head)//判斷棧是否為空
{
  if(Head==NULL)
    return 1;
  else
    return 0;
}

int main()
{ 
  int i,x;
  link head1;
  head1=init();
  while(i!=6)
  {
    system("cls");
    cout<<"\n 1.Input a stack data";
    cout<<"\n 2.Output a stack data";
    cout<<"\n 3.Empty or Not";
    cout<<"\n 4.Display a top of stack";
    cout<<"\n 5.Display the lenth of stack";
    cout<<"\n 6.Exit and Free Stack\n";
    cout<<"\n  Stack is:  ";
    display(head1);
    cout<<"\n";

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