【資料結構】堆疊
堆疊(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
=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-
請按任意鍵繼續 . . .
*/