【資料結構】堆疊 – 程式設計教育農場 by 陳富國

堆疊(Stack)是一種後進先出(Last In First Out, LIFO)的有序串列，亦即資料處理的方式都是在同一邊進行，也就是由相同的一端來進行插入與刪除動作。而我們日常生活中，也有一些是堆疊的例子，例如堆盤子、書本裝箱…等，都是一層一層的堆上去，如果想要取出箱子中某一本書，也只能從最上面開始取出。

【定義】

1.一群相同性質元素的組合，即有序串列(ordered List) 。

2.具有後進先出 (Last In First Out, LIFO) 的特性。

3.將一個項目放入堆疊的頂端，這個動作稱為Push(加入)。

4.從堆疊頂端拿走一個項目，這個動作稱為Pop(取出)。

5.Push/Pop的動作皆發生在同一端，則稱此端為Top(頂端)。

6.要取出資料時，則只能從Top(頂端)取出，不能從中間取出資料。

【堆疊的操作示範】

【堆疊常用的操作】

Push ：加入新項目到堆疊的頂端。
Pop ：取出堆疊頂端一個項目。
TopItem ：查看堆疊頂端的項目內容。
IsEmpty ：判斷堆疊是否為空，若為空則傳回真(True)，否則傳回假(False)。
IsFull ：判斷堆疊是否為滿，若為滿則傳回真(True)，否則傳回假(False)。

【C#-Stack類別】

Stack.Push 方法 (Object)

using System;
using System.Collections; //C#的Stack所在的命名空間
public class SamplesStack
{

    public static void Main()
    {

        // Creates and initializes a new Stack. 建立並初始化一個新的堆疊
        Stack myStack = new Stack();
        myStack.Push("The");
        myStack.Push("quick");
        myStack.Push("brown");
        myStack.Push("fox");

        // Displays the Stack. //印出堆疊內容
        Console.Write("堆疊元素：:");
        PrintValues(myStack, '\t'); //呼叫下方PrintValues方法

        // Removes an element from the Stack. 從堆疊裏移除一個元素
        Console.WriteLine("(Pop)\t\t{0}", myStack.Pop());

        // Displays the Stack. 印出堆疊內容
        Console.Write("堆疊元素：:");
        PrintValues(myStack, '\t');

        // Removes another element from the Stack. 從堆疊裏移除另一個元素
        Console.WriteLine("(Pop)\t\t{0}", myStack.Pop());

        // Displays the Stack. 印出堆疊內容
        Console.Write("堆疊元素：:");
        PrintValues(myStack, '\t');

        // Views the first element in the Stack but does not remove it.
        //檢視堆疊裏的第一個元素，但不移除該元素，注意動作與pop不同
        Console.WriteLine("(Peek)\t\t{0}", myStack.Peek());

        // Displays the Stack.
        Console.Write("堆疊元素：:");
        PrintValues(myStack, '\t');
    }


    public static void PrintValues(IEnumerable myCollection, char mySeparator)
    {
        foreach (Object obj in myCollection) //對每一個在myCollection集合裏的物件obj
            Console.Write("{0}{1}", mySeparator, obj);
        Console.WriteLine();
    }

}


/* 
程式輸出：
堆疊元素：:     fox     brown   quick   The
(Pop)           fox
堆疊元素：:     brown   quick   The
(Pop)           brown
堆疊元素：:     quick   The
(Peek)          quick
堆疊元素：:     quick   The
請按任意鍵繼續 . . .
*/

【堆疊在運算式上的應用】

在日常生活中，我們所使用的四則運算都屬於中序(infix order)運算式，亦即運算子位於兩個運算元之間的表示法。但是，此種表示法電腦並無法直接的處理，因為中序式可能會含有括號，並且運算子可能有不同的優先順序權。因此，若要使用電腦來處理運算式時，則必須要先將「中序式」轉換成「後序式」(postfix order)。

算術式表示的方式有三種：

中序(Infix)表示法： A+B
前序(prefix)表示法： +AB
後序(postfix)表示法： AB-

【中序(Infix)表示法】

【定義】數學上的表示方式，就是屬於中序式，它是把運算子放在兩個運算元的中間。

【表示式】<運算元1 > <運算子> <運算元2 >

【例如】A+B。

【缺點】電腦無法一次依序讀取運算式，因運算式可能含有括號，且未定義運算子優先順序。

【前序 (prefix)表示法】

【定義】指將中序表示法中的運算子和運算元重新調整順序，只是運算子的順序是在運算元前面。

【表示式】<運算子> <運算元1 > <運算元2 >

【例如】+AB。

【後序 (postfix)表示法】

【定義】後序表示法和前序表示法相類似，使得運算子放於運算元後面的表示法。

【表示式】<運算元1 > <運算元2 > <運算子>

【例如】AB+。

【優點】不必使用括號，方便電腦使用。

【運算式的轉換】

大部份的運算式(expression)都是由運算元(operand)與運算子(operator)所組成。

【例如】A*B+(C/D)-E 其中： A,B,C,D,E為運算元(operand)， +,-,*,/為運算子(operator)

【運算原則】

括號內先處理
優先權較高的運算子先執行
同優先權者，則由結合性，來決定是由左而右，還是由右而左執行。

【中序式→前序式】

假設有一個中序式為：A×B+C×D，欲轉換成前序式，其步驟如下：

1.先用括號將優先順序分出來

((A×B)＋(C×D))

2.將運算子移到左括號右邊

((×AB)＋(×CD))

(＋(×AB)(×CD))

3.把括弧全部拿掉，即為所得。

＋×AB×CD

【中序式→後序式】

假設有一個中序式為：A×B+C×D，欲轉換成後序式，其步驟如下：

1.先用括號將優先順序分出來

((A×B)＋(C×D))

2.將運算子移到右括號左邊

((AB×)＋(CD×))

((AB×)(CD×)＋)

3.把括弧全部拿掉，即為所得。

AB×CD×＋

練習：

1. A+B*C-D/E

Ans: 依優先順序括上括弧

(A+(B*C))-(D/E))

後序式係將運算子移到右括號左邊

(A(BC*)+)(DE/)-)

去掉括弧：

**ABC*+DE/-**

2. (A+B)*C/(D-E/F)

Ans: 依優先順序括上括弧

(((A+B)*C)/(D-(E/F)))

後序式係將運算子移到右括號左邊

(((AB+)C*)(D(EF/)-)/)

去掉括弧：

AB+C*DEF/-/

後序式求解：

設A=1, B=2, C=3, D=4, E=5, F=2，求下面後序式的值為何？

1．AB*C-DE**

=(((AB*)C-)(DE*)*)

=(((A*B)-C)*(D*E))

=(((1*2)-3)*(4*5))

=-20

2．ABC*+DE/-

=((A(BC*)+)(DE/)-)

=((A+(B*C))-(D/E))

=((1+(2*3))-(4/5))

=1+6-0.8

=6.2

3．AB+C*DEF/-/

=(((AB+)C*)(D(EF/)-)/)

=(((A+B)*C)/(D-(E/F)))

=(((1+2)*3)/(4-(5/2)))

=3*3/(4-2.5)

=9/1.5

以上方法是我們人員用來進行的中序轉後序/前序的快速方法，應付考試相當快捷，但是，若要用程式來實現轉換方法，需要特定的資料結構來協助，一般來說有二種作法：堆疊與二元樹。

考試時，一般不會考程式，所以不用特別注意堆疊的演算法，大家要記得的是去括弧法與二元樹法。(考試必考！)

【C# – 中序到後序的轉換程式】

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Infix
{
   class Program
   {
 
      static bool InfixToPostfixConvert(ref string infixBuffer, out string postfixBuffer)
      {
         int priority = 0;
         postfixBuffer = "";
 
         Stack<Char> s1 = new Stack<char>();
 
         for (int i = 0; i < infixBuffer.Length; i++)
         {
            char ch = infixBuffer[i];
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
            {
               // check the precedence
               if (s1.Count <= 0)
                  s1.Push(ch);
               else
               {
                  if (s1.Peek() == '*' || s1.Peek() == '/')
                     priority = 1;
                  else
                     priority = 0;
                  if (priority == 1)
                  {
                     if (ch == '+' || ch == '-')
                     {
                        postfixBuffer += s1.Pop();
                        i--;
                     }
                     else
                     { // Same
                        postfixBuffer += s1.Pop();
                        i--;
                     }
                  }
                  else
                  {
                     if (ch == '+' || ch == '-')
                     {
                        postfixBuffer += s1.Pop();
                        s1.Push(ch);
                     }
                     else
                        s1.Push(ch);
                  }
               }
            }
            else
            {
               postfixBuffer += ch;
            }
         }
         int len = s1.Count;
         for (int j = 0; j < len; j++)
            postfixBuffer += s1.Pop();
         return true;
      }
 
      static void Main(string[] args)
      {
         string infixBuffer = "";
         string postfixBuffer = "";
 
         if (args.Length == 1)
         {
            infixBuffer = args[0];
           
            InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
            System.Console.WriteLine("InFix  :\t" + infixBuffer);
            System.Console.WriteLine("PostFix:\t" + postfixBuffer);
         }
         else
         {
            infixBuffer = "a+b*c";
 
            InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
            System.Console.WriteLine("InFix  :\t" + infixBuffer);
            System.Console.WriteLine("PostFix:\t" + postfixBuffer);
            System.Console.WriteLine();
           
            infixBuffer = "a+b*c/d-e";
            InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
            System.Console.WriteLine("InFix  :\t" + infixBuffer);
            System.Console.WriteLine("PostFix:\t" + postfixBuffer);
            System.Console.WriteLine();
           
            infixBuffer = "a+b*c/d-e+f*h/i+j-k";
            InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
            System.Console.WriteLine("InFix  :\t" + infixBuffer);
            System.Console.WriteLine("PostFix:\t" + postfixBuffer);
            System.Console.WriteLine();
         }        
      }
   }
}

/* 程式輸出
中序  : a+b*c
後序:   abc*+

中序  : a+b*c/d-e
後序:   abc*d/+e-

中序  : a+b*c/d-e+f*h/i+j-k
後序:   abc*d/+e-fh*i/+j+k-

請按任意鍵繼續 . . .

*/