【資料結構】堆疊

  堆疊(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(頂端)取出，不能從中間取出資料。    

【堆疊的操作示範】

 

【堆疊常用的操作】

1.  Push  ：加入新項目到堆疊的頂端。
2. Pop  ：取出堆疊頂端一個項目。
3. TopItem  ：查看堆疊頂端的項目內容。
4. IsEmpty  ：判斷堆疊是否為空，若為空則傳回真(True)，否則傳回假(False)。
5. 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)tt{0}", myStack.Pop());
        // Displays the Stack. 印出堆疊內容
        Console.Write("堆疊元素：:");
        PrintValues(myStack, 't');
        // Removes another element from the Stack. 從堆疊裏移除另一個元素
        Console.WriteLine("(Pop)tt{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)tt{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)。

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

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

【中序(Infix)表示法】

【定義】數學上的表示方式，就是屬於中序式，它是把運算子放在兩個運算元的中間。 【表示式】<運算元1 > <運算子> <運算元2 > 【例如】A+B。 【缺點】電腦無法一次依序讀取運算式，因運算式可能含有括號，且未定義運算子優先順序。  

【前序 (prefix)表示法】

【定義】指將中序表示法中的運算子和運算元重新調整順序，只是運算子的順序是在運算元前面。 【表示式】<運算子> <運算元1 > <運算元2 > 【例如】+AB。  

【後序 (postfix)表示法】

【定義】後序表示法和前序表示法相類似，使得運算子放於運算元後面的表示法。 【表示式】<運算元1 > <運算元2 > <運算子> 【例如】AB+。 【優點】 不必使用括號，方便電腦使用。  

【運算式的轉換】

大部份的運算式(expression)都是由運算元(operand)與運算子(operator)所組成。 【例如】AB+(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+BC-D/E Ans:  依優先順序括上括弧 (A+(BC))-(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)) =(((AB)-C)(DE)) =(((12)-3)(4*5)) =-20

2．ABC*+DE/-

=((A(BC)+)(DE/)-) =((A+(BC))-(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))) =33/(4-2.5) =9/1.5 =6

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

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

【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-
請按任意鍵繼續 . . .
*/