//* * * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :3  (3_3)                     *
//*PROGRAM          :鏈式堆棧                     *
//*CONTENT          :初始化,入棧,出棧,取棧頂元素  *
//* * * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
enum BOOL{False,True};
typedef struct Lnode       //定義節點結構
{char  data;               //數據域
 struct Lnode *next;       //后向指針
}LNode,*LPoint;
void initial(LPoint&);    //初始化一個堆棧
void  push_linkstack(LPoint&,char);       //將一個元素入棧
BOOL pop_linkstack(LPoint&,char &);        //將一個元素出棧
void print_linkstack(LPoint); //顯示棧中所有元素
void main()
{LPoint ls,p;
 char ch,j;
 int flag=1;
 BOOL temp;
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //---------------------程序解說-----------------------
 printf("本程序實現鏈式結構的堆棧操作。\n");
 printf("鏈式堆棧不會產生溢出問題。\n");
 printf("可以進行入棧，出棧，取棧頂元素等操作。\n");
 //----------------------------------------------------
 
 initial(ls);       //初始化堆棧S
 while(flag)
    { printf("請選擇:\n");
      printf("1.顯示棧中所有元素\n");
      printf("2.入棧       \n");
      printf("3.出棧       \n");
      printf("4.退出程序   \n");
      scanf(" %c",&j);
      switch(j)
	{case '1':print_linkstack(ls);
		  break;
	 case '2':printf("請輸入要入棧的元素(一個字符):");
		  scanf(" %c",&ch);   //輸入要入棧的字符
		  push_linkstack(ls,ch);//入棧
		  print_linkstack(ls);
		  break;
	 case '3':temp=pop_linkstack(ls,ch);  //出棧
		  if(temp==True)
		      {printf("出棧一個元素:%c\n",ch);//若棧不空，顯示出棧的元素
		       print_linkstack(ls);
		      }
		else printf("堆棧已空!\n");//否則堆棧為空
		break;
	 default:flag=0;printf("程序結束，按任意鍵退出!\n");
	}
    }
 getch();
}

void initial(LPoint &pi)
{pi=NULL;   //棧頂指針初始化為NULL
}

void push_linkstack(LPoint &pi,char ch)
{//入棧，由于采用鏈式結構，一般不會產生棧滿的情況
 LPoint po;
 po=(LPoint)malloc(sizeof(LNode));//生成一個新節點
 po->data=ch;                     //賦值
 po->next=pi;                  //新節點的后向指針指向原棧頂節點
 pi=po;                          //站頂指針指向新節點
}

BOOL pop_linkstack(LPoint &pi,char &e)
{//出棧，成功返回True，并用e返回該元素值，失敗返回False
 LPoint po;
 po=pi;
 pi=po->next;                  //棧頂指針指向下一個節點
 if(po==NULL) return False;    //棧已空
 else {e=po->data;
       return True;  
      }                    
}

void print_linkstack(LPoint p)     
{//顯示棧中所有元素
 if(p==NULL) printf("堆棧已空!\n");//棧為空
 else  {printf("堆棧所有元素:");
	while(p!=NULL)                       //否則顯示棧中所有元素
	    {printf("%c ",p->data);
	     p=p->next;
	    }
	printf("\n");
       }
}