//* * * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :3  (3_3)                     *
//*PROGRAM          :鏈?zhǔn)蕉褩?                    *
//*CONTENT          :初始化,入棧,出棧,取棧頂元素  *
//* * * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
enum BOOL{False,True};
typedef struct Lnode       //定義節(jié)點(diǎn)結(jié)構(gòu)
{char  data;               //數(shù)據(jù)域
 struct Lnode *next;       //后向指針
}LNode,*LPoint;
void initial(LPoint&);    //初始化一個(gè)堆棧
void  push_linkstack(LPoint&,char);       //將一個(gè)元素入棧
BOOL pop_linkstack(LPoint&,char &);        //將一個(gè)元素出棧
void print_linkstack(LPoint); //顯示棧中所有元素
void main()
{LPoint ls,p;
 char ch,j;
 int flag=1;
 BOOL temp;
 textbackground(3);  //設(shè)定屏幕顏色
 textcolor(15);
 clrscr();
 //---------------------程序解說-----------------------
 printf("本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)的堆棧操作。\n");
 printf("鏈?zhǔn)蕉褩２粫?huì)產(chǎn)生溢出問題。\n");
 printf("可以進(jìn)行入棧，出棧，取棧頂元素等操作。\n");
 //----------------------------------------------------
 
 initial(ls);       //初始化堆棧S
 while(flag)
    { printf("請(qǐng)選擇:\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("請(qǐng)輸入要入棧的元素(一個(gè)字符):");
		  scanf(" %c",&ch);   //輸入要入棧的字符
		  push_linkstack(ls,ch);//入棧
		  print_linkstack(ls);
		  break;
	 case '3':temp=pop_linkstack(ls,ch);  //出棧
		  if(temp==True)
		      {printf("出棧一個(gè)元素:%c\n",ch);//若棧不空，顯示出棧的元素
		       print_linkstack(ls);
		      }
		else printf("堆棧已空!\n");//否則堆棧為空
		break;
	 default:flag=0;printf("程序結(jié)束，按任意鍵退出!\n");
	}
    }
 getch();
}

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

void push_linkstack(LPoint &pi,char ch)
{//入棧，由于采用鏈?zhǔn)浇Y(jié)構(gòu)，一般不會(huì)產(chǎn)生棧滿的情況
 LPoint po;
 po=(LPoint)malloc(sizeof(LNode));//生成一個(gè)新節(jié)點(diǎn)
 po->data=ch;                     //賦值
 po->next=pi;                  //新節(jié)點(diǎn)的后向指針指向原棧頂節(jié)點(diǎn)
 pi=po;                          //站頂指針指向新節(jié)點(diǎn)
}

BOOL pop_linkstack(LPoint &pi,char &e)
{//出棧，成功返回True，并用e返回該元素值，失敗返回False
 LPoint po;
 po=pi;
 pi=po->next;                  //棧頂指針指向下一個(gè)節(jié)點(diǎn)
 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");
       }
}