3.2 棧典型題例

【例3-3】若某堆棧的輸入序列為1,2,3,…,n-1,n，輸出序列的第1個元素為n，問第i個輸出元素是什么?

【分析與解答】堆棧的輸入序列為1,2,3,…,n-1,n，堆棧的特性是后進先出，輸出序列的第1個元素為n，那么第2個元素為n-1，第3個元素為n-2，依次類推，第i個輸出元素是n-i+1。

【例3-4】簡述以下算法的功能。

void Reverse (SeqStack s)

{

n=0;

while (!StackEmpty (s))

{
a[n]=Pop(s);
n++;
}
for(i=0;i<n;i++)
Push(s,a[i]);
} /*Reverse*/
void Remove (LinkStack s,ElementType e)
{
while (!StackEmpty (s))
{
d=Pop(s);
if (d!=e) Push(t,d);
}
while (!StackEmpty (t))
     {
        d=Pop(t);
        Push(s,d);
     }
} /* Remove */

【分析與解答】算法Reverse中，堆棧s的元素從棧底到棧頂?shù)男蛄性O為e1,e2,…,en，while循環(huán)將s的元素出棧，存入a數(shù)組，a數(shù)組中各元素的值如表3-1所示，for循環(huán)將a數(shù)組元素依a[0],a[1],…,a[n-1]（即en,en-1,…,e1）的順序入s棧，從棧底到棧頂?shù)男蛄袨閑n,en-1,…,e1。因此，該算法借助數(shù)組a實現(xiàn)了堆棧s的逆置。

表3-1 數(shù)組a中元素的值

算法Remove中，第1個while循環(huán)將s的元素（除元素e）出棧進入t棧，t棧是s棧不包括e元素的逆置；第2個while循環(huán)則將t的元素出棧后又進入s棧，s棧是t棧的逆置，最終s經(jīng)過兩次逆置又恢復成原來的元素序列（不包括元素e），因此該算法借助堆棧t將堆棧s中的數(shù)據(jù)元素e刪除。

【例3-5】圖3-5所示是一組n條帶頭結(jié)點的鏈表表示的堆棧（n個鏈棧），top[0],top[1],…, top[n-1]分別是各堆棧棧頂指針，試給出該組堆棧的數(shù)據(jù)類型定義，并寫一算法對這組堆棧初始化。

【分析與解答】數(shù)據(jù)類型（鏈表中結(jié)點類型StackNode與鏈指針類型LinkStack）定義如下。

#define MaxSize 棧頂指針數(shù)組的最大長度
typedef struct snode
    { ElementType data;
      struct snode *next;
    }StackNode;
typedef StackNode *LinkStack;
    / * LinkStack為指向StackNode的指針類型* /

構(gòu)成n個棧頂指針的數(shù)組數(shù)據(jù)類型定義如下。

LinkStack top[MaxSize];

堆棧組初始化算法如下。

void StackInit(LinkStack top[],int n)
{
    for (i=0;i<n;i++)
    {
        p=(LinkStack)malloc(sizeof(StackNode));/*生成堆棧頭結(jié)點*/
        p->next=NULL;/*堆棧頭結(jié)點指針為空*/
        top[i]=p;/*各數(shù)組元素為指向頭結(jié)點的頭指針*/
    }
}/* StackInit */

【例3-6】寫一算法，將十進制數(shù)轉(zhuǎn)換為十進制以下進制的數(shù)。

【分析與解答】將十進制數(shù)轉(zhuǎn)換成其他進制數(shù)有一種簡單的方法，即利用公式：

N=(N div d)*d+N mod d

其中div為整除運算，mod為求余運算，N是十進制數(shù)，d表示要轉(zhuǎn)換到的目標進制（其他進制）。公式中十進制數(shù)N轉(zhuǎn)換為d進制數(shù)的過程就是，N除以d取其余數(shù)，最先得到的余數(shù)就是最低位，依次到最高位。

例如，將十進制數(shù)67轉(zhuǎn)換為二進制數(shù)，其轉(zhuǎn)換過程如下。

67 div 2=33余數(shù)為1

33 div 2=16余數(shù)為1

16 div 2=8余數(shù)為0

8 div 2=4余數(shù)為0

4 div 2=2余數(shù)為0

2 div 2=1余數(shù)為0

1 div 2=0余數(shù)為1

結(jié)果為余數(shù)的逆序1000011，即(67)10=(1000011)2。

算法描述如下。

int Conversion(int n,int d)
/*將十進制數(shù)n轉(zhuǎn)換為d進制（十進制以下進制）數(shù)*/
{
    SeqStack s;
    result=0;
    s.top=-1;
    while (n)
    {
       Push(s,n%d); /*余數(shù)入棧*/
       n=n/d;
    }
    while (!StackEmpty (s))
       result=result*10+Pop(s);
    return(result);
} /*conversion */

【例3-7】一個簡單的行編輯程序的功能是接收用戶的終端輸入，并允許用戶對輸入的錯誤及時修改。約定“#”為退格符，表示前一個輸入的字符無效，“@”為退行符，表示當前行的輸入無效。若用戶的終端輸入為while##le (s1#!=0)，則對應的有效輸入為while(s!=0)。寫一模擬行編輯程序的算法。

【分析與解答】可借用兩個堆棧s、t來模擬行編輯程序的工作過程。

（1）堆棧s用來接收用戶輸入的普通字符，如果輸入的是特殊字符“#”或“@”，則對s棧做一次出棧或清空操作。

（2）當一行字符輸入結(jié)束后，將s棧中的字符依次出棧并壓入t棧，t棧中存放有s棧字符的逆序列。

（3）將t棧中的字符依次出棧存放在數(shù)組str中，數(shù)組str中存放有t棧字符的逆序列，即s棧字符的正序列，并且每行字符都存入str。

（4）當輸入結(jié)束時，輸出字符數(shù)組str的值，也就輸出了用戶輸入、編輯后的有效字符。

void LineEdit()
/*行編輯程序模擬算法*/
{  s=StackInit ();
   t=StackInit ();
   strlen=0；
   ch=getchar();
   while(ch!=EOF) /*EOF表示輸入結(jié)束符*/
      {  while(ch!=EOF && ch!='\n') /*接收一行字符*/
        {  switch(ch)
        {  case '#' : ch=Pop(s);break;
           case '@' : StackClear (s);break;/*將s棧置空*/
           default : Push(s,ch);break;  /*輸入字符存入s棧*/
         }
         ch=getchar();
      }
      if (ch=='\n') Push(s,ch);/*換行符進棧*/
      while(!StackEmpty(s))
      {  x=Pop(s);
         Push(t,x);/* t棧存放s棧中字符序列的逆序*/
      }
      while(!Empty(t))
      {  x=Pop(t);
         str[strlen++]=x;
      }
      if (ch!=EOF) ch=getchar();
     }
     str[strlen]='\0';
     printf(str);
} /* LineEdit */