什么是棧？

? ? 棧是限制插入和刪除只能在同一個位置上進(jìn)行的表，這個位置就是棧的頂端，對于棧的操作主要有三種形式：入棧(將元素插入到表中)，出棧(將表最后的元素刪除，也就是棧頂?shù)脑?，返回棧頂元素。棧有時又叫LIFO(后進(jìn)先出)表。

棧的實(shí)現(xiàn)

棧可以有兩種實(shí)現(xiàn)方式：1）數(shù)組實(shí)現(xiàn) 2）鏈表實(shí)現(xiàn)

棧的雙向鏈表實(shí)現(xiàn)

public class StackForLinked<T>{private int num = 0;public int count { get{return num;} }private Node<T> root = null;private class Node<T>{public T data; public Node<T> prev;public Node<T> next;public Node(T value){this.data = value;this.prev=null;this.next=null;} public Node(T value,Node<T> prev,Node<T> next):this(value){this.prev = prev;this.next=next;}}public void Push(T value){Node<T> node = new Node<T>(value);if(root==null){root = node;}else{var last= GetLastNode();last.next = node;node.prev= last;}num++;}public T Pop(){var node=GetLastNode();if(node==null)throw new Exception();node.prev.next=null;num--;return node.data;}public T GetTop(){var node =GetLastNode();if(node==null)throw new Exception();return node.data;}private Node<T> GetLastNode(){Node<T> p = root;if(root==null){return null;}while(true){if(p.next!=null){p=p.next;}else break;}return p;}}

棧的數(shù)組實(shí)現(xiàn)

public class StackForArray<T>{private static int length = 100;private T[] objList = new T[length]; private int currentIndex = 0；public int count { get { return this.currentIndex;} }private void ensureCapcity(int capcity){if(capcity < currentIndex){return;}T[] old = objList;objList = new T[capcity];for(int i=0;i<old.Length;i++){objList[i] = old[i];}}public void Push(T value){if(currentIndex == length){ensureCapcity(currentIndex * 2 +1);}objList[currentIndex] = value;currentIndex++;}public T Pop(){if(currentIndex == 0)throw new Exception();currentIndex--;return objList[currentIndex];}public T GetTop(){if(currentIndex == 0){throw new Exception();}return objList[currentIndex -1];}}

PS：對于鏈表在添加和刪除方面是O(1), 但是在查找方面則是O(N)；數(shù)組在查找方面是O(1)操作,但是在插入或者是刪除方面涉及到表的中元素的位置上的移動，若數(shù)據(jù)中的元素較多會帶來性能上的損失。所以在考慮使用鏈表還是使用數(shù)組進(jìn)行存儲數(shù)據(jù)的時候，應(yīng)該考慮上述所說(數(shù)據(jù)量大小，插入和刪除多還是查找的多)。當(dāng)前這與棧的關(guān)系不太大，因?yàn)闂６际窃谝欢诉M(jìn)行操作，不會涉及元素移動的問題。

棧的應(yīng)用

棧的應(yīng)用有很多，這里只舉一些簡單的例子：
1.平衡符號：例如判斷括號是否成對出現(xiàn)，通過將括號入棧然后碰見成對的括號就出棧，最后判斷棧中的元素是否為空，為空則是成對出現(xiàn)，反之則不成對
2.中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式：
? ? 中綴表達(dá)式和后綴表達(dá)式: 例如表達(dá)式 a + b c 這就是我們平時所見的正常的數(shù)學(xué)計(jì)算表達(dá)式，在數(shù)學(xué)上我們也知道怎么計(jì)算，但是你把這一段表達(dá)式告訴計(jì)算機(jī)，然后計(jì)算出結(jié)果，那么這個結(jié)果是怎么計(jì)算出來的呢？這里就涉及一個概念叫做后綴表達(dá)式，首先 a + b c 會先通過棧轉(zhuǎn)化為 a b c * + 然后再通過棧進(jìn)行計(jì)算從而得出結(jié)果，前者通常叫做中綴表達(dá)式。隨后會有一段代碼的例子，可以讓你真正的了解數(shù)學(xué)表達(dá)式是如何通過棧進(jìn)行計(jì)算的
3.方法調(diào)用：類似于平衡符號的檢測，所有的方法調(diào)用和返回都是成對的，在開始調(diào)用的時候需要在棧內(nèi)存儲一些信息(位置,對應(yīng)變量的名字和返回地址等)，方法完成后需要從棧中出棧拿到當(dāng)初存儲的信息然后做一些操作,這也正好印證了，當(dāng)遞歸調(diào)用的時候，不當(dāng)?shù)倪f歸會出現(xiàn) Stackoverflow 異常，也就是說在棧(在window下，默認(rèn)大小是1M )中已經(jīng)存儲不下每一次遞歸的信息了，就會報(bào)這個錯誤。

PS： 我這里說的都是同步方法，存在一個方法的調(diào)用需要等待另一個方法的完成，異步方法還不太了解，期待后續(xù)學(xué)習(xí)會有更多的收獲

棧實(shí)現(xiàn)基本操作的運(yùn)算

? ? 用棧來實(shí)現(xiàn)簡單的基本數(shù)學(xué)運(yùn)算：+ ，- ，* ， ／ 和（ ）在數(shù)學(xué)中我們都知道這幾種符號的優(yōu)先級，那么計(jì)算機(jī)時怎么做到的呢？ 下面我們以一個表達(dá)式為例子來實(shí)現(xiàn)一下計(jì)算機(jī)的計(jì)算過程
? ? 表達(dá)式：a + b c + ( d e + f ) * g ，除棧外，我們還需要一個輸出字符串用來存儲生成的后綴表達(dá)式，默認(rèn)情況下為空，出于方便我會使用 [] 代表一個棧，[ 代表?xiàng)５?#xff0c;] 代表?xiàng)ｍ?#xff0c;用 | 分割每個元素。

原理

1.對常數(shù)輸出，對操作符號入棧操作，根據(jù)優(yōu)先級別判斷是出棧還是入棧；
2.優(yōu)先級低的不允許出現(xiàn)在優(yōu)先級高的后面(棧中存在一個優(yōu)先級高的符號，此時來了一個低優(yōu)先級符號，需要進(jìn)行先把高優(yōu)先級的符號出棧，然后將低優(yōu)先級的符號入棧)；
3.同優(yōu)先級的符號先出棧再入棧；
4.對于存在括號的情況，當(dāng)前棧頂?shù)脑厥?( 那么接下來的一個符號不比較優(yōu)先級直接入棧，接下來的操作遵循前3條規(guī)則;
5.當(dāng)遇見 ）的時候，執(zhí)行出棧操作直到遇見出棧的第一個（ 為止；
6.得到后綴表達(dá)式之后再次使用棧進(jìn)行計(jì)算，將后綴表達(dá)式中的值入棧，碰見操作符，出棧兩個元素執(zhí)行運(yùn)算符計(jì)算，將計(jì)算的結(jié)果插入到棧中，直到后綴表達(dá)式的盡頭，最終結(jié)果位于棧頂，出棧即可得到

步驟：

1.將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式

Step 1 : 我們第一次讀取的是常數(shù) a ，直接輸出，此時輸出的字符串中的值為 a
Step 2 : 繼續(xù)讀取，接下來讀取的是操作符號 + ，入棧操作，此時棧中的元素為 [ + ]
Step 3 : 繼續(xù)讀取，接下來讀取的是常數(shù) b , 直接輸出，此時輸出的字符串中的值為 a b
Step 4 : 繼續(xù)讀取，接下來讀取的是操作符號 , 入棧操作，此時棧中的元素為 [ + | ]
Step 5 : 繼續(xù)讀取，接下來讀取的是常數(shù) c , 直接輸出，此時輸出的字符串中的值為 a b c
Step 6 : 繼續(xù)讀取，接下來讀取的是操作符號 + , 棧頂元素 的優(yōu)先級高于 + ，將 出棧，之后發(fā)現(xiàn)棧頂元素為 +，優(yōu)先級相同，繼續(xù)出棧，然后將 + 進(jìn)棧，此時棧中的元素為[ + ]，輸出字符串中的值為 a b c * +
Step 7 : 繼續(xù)讀取，接下來讀取的是操作符號 ( , 入棧操作，此時棧中的元素為 [ + | ( ]
Step 8 : 繼續(xù)讀取，接下來讀取的是常數(shù) d , 直接輸出，此時輸出的字符串中的值為 a b c * + d
Step 9 : 繼續(xù)讀取，接下來讀取的是操作符號 , 入棧操作，此時棧中的元素為[ + | ( | ]
Step 10 : 繼續(xù)讀取，接下來讀取的是常數(shù) e , 直接輸出，此時輸出的字符串中的值為 a b c * + d e
Step 11 : 繼續(xù)讀取，接下來讀取的是操作符號 + , 棧頂元素 的優(yōu)先級高于 + ，先執(zhí)行出棧操作，在執(zhí)行 + 入棧操作，此時棧中的元素為[ + | ( | +] , 輸出字符串中的值為 a b c + d e *
Step 12 : 繼續(xù)讀取，接下來讀取的是常數(shù) f , 直接輸出，此時輸出的字符串中的值為 a b c + d e f
Step 13 : 繼續(xù)讀取，接下來讀取的是操作符號 ) , 開始執(zhí)行出棧操作，直到遇見第一個出棧的元素為 ( 停止，此時棧中的元素為[ + ] , 輸出字符串中的值為 a b c + d e +
Step 14 : 繼續(xù)讀取，接下來讀取的是操作符號 , 入棧操作，此時棧中的元素為[ + | ]
Step 15 : 繼續(xù)讀取，接下來讀取的是常數(shù) g , 直接輸出，此時輸出的字符串中的值為 a b c + d e f + g
Step 16: 繼續(xù)讀取，到達(dá)了末端，開始執(zhí)行中出棧操作，直到棧為空，此時輸出的字符串中的值為 a b c + d e f + g + ，從而得出后綴表達(dá)式為：a b c + d e f + g +

2.計(jì)算后綴表達(dá)式 (Step中的括號的使用是起到輔助清晰的作用，因?yàn)椴]給字符實(shí)際的值)

Step 1 : 讀取后綴表達(dá)式，第一個遇到的是 a 執(zhí)行入棧操作，此時棧中的元素為 [ a ]
Step 2 : 繼續(xù)讀取，解下來遇到的是 b ，執(zhí)行入棧操作，此時棧中的元素為 [ a | b ]
Step 3 : 繼續(xù)讀取，解下來遇到的是 c ，執(zhí)行入棧操作，此時棧中的元素為 [ a | b | c ]
Step 4 : 繼續(xù)讀取，解下來遇到的是 ，出棧兩個元素，計(jì)算 b c ，然后在執(zhí)行入棧， 此時棧中的元素為 [ a | b * c ]
Step 5 : 繼續(xù)讀取，解下來遇到的是 + ，出棧兩個元素，計(jì)算 a + b c，然后執(zhí)行入棧操作，此時棧中的元素為 [ a + b c ]
Step 6 : 繼續(xù)讀取，解下來遇到的是 d ，執(zhí)行入棧操作，此時棧中的元素為 [ a + b * c | d ]
Step 7 : 繼續(xù)讀取，解下來遇到的是 e ，執(zhí)行入棧操作，此時棧中的元素為 [ a + b * c | d | e ]
Step 8 : 繼續(xù)讀取，解下來遇到的是 ，出棧兩個元素，計(jì)算 d e ，然后執(zhí)行入棧操作，此時棧中的元素為 [ a + b c | d e ]
Step 9 : 繼續(xù)讀取，解下來遇到的是 f ，執(zhí)行入棧操作，此時棧中的元素為 [ a + b c | d e | f ]
Step 10 : 繼續(xù)讀取，解下來遇到的是 + ，出棧兩個元素，計(jì)算 d e + f ，然后執(zhí)行入棧操作，此時棧中的元素為 [ a + b c | d * e + f ]
Step 11 : 繼續(xù)讀取，解下來遇到的是 g ，執(zhí)行入棧操作，此時棧中的元素為 [ a + b c | d e + f | g ]
Step 12 : 繼續(xù)讀取，解下來遇到的是 ，出棧兩個元素，計(jì)算 ( d e + f ) g ，然后執(zhí)行入棧操作，此時棧中的元素為 [ a + b c | ( d e + f ) g ]
Step 13 : 繼續(xù)讀取，解下來遇到的是 + ，出棧兩個元素，計(jì)算 a + b c + ( d e + f ) g ，然后執(zhí)行入棧操作，此時棧中的元素為 [ a + b c + ( d e + f ) g ]
Step 14 : 繼續(xù)讀取，到達(dá)了末端，執(zhí)行出棧操作，出棧的結(jié)果就是計(jì)算的結(jié)果 a + b c + ( d e + f ) * g

實(shí)現(xiàn)代碼

class Program {static List<Priority> priority = new List<Priority>(){new Priority() { level = 0 , symbal ="+" },new Priority() { level = 0 , symbal ="-" },new Priority() { level = 1 , symbal ="*" },new Priority() { level = 1 , symbal ="/" },new Priority() { level = int.MaxValue , symbal ="(" },new Priority() { level = int.MaxValue , symbal =")" }};static void Main(string[] args){//string expression = "a + b * c + ( d * e + f ) * g";//string expression ="10 + 1 * 10 + ( 2 * 3 + 4 ) * 10"; // 120 //string expression ="1 + 2 + 3 ";string expression ="3 * ( ( 2 - 4 ) / ( 2 - 1 ) ) ";GenerateExpression(expression);Console.WriteLine(OutputStr);Console.WriteLine(CalculateValue());}///生成后綴表達(dá)式的棧static StackForArray<Priority> symbalStack = new StackForArray<Priority>();/// 輸出字符串static string OutputStr=string.Empty;/// 生成后綴表達(dá)式static void GenerateExpression(string expression){string[] symbals = expression.Split(' ');foreach(string symbal in symbals){RecursionExpression(symbal);}while(true){try{var popElement = symbalStack.Pop();OutputStr += popElement.symbal +" ";}catch(Exception ex){break;}}}// 計(jì)算表達(dá)式的值static int CalculateValue(){StackForArray<int> valueStack = new StackForArray<int>();string[] symbals = OutputStr.Split(new char[]{' '},StringSplitOptions.RemoveEmptyEntries);foreach(var symbal in symbals){var temp = priority.Where(x=>x.symbal ==symbal).FirstOrDefault();if(temp!=null){var t = 0;var second = valueStack.Pop();var first = valueStack.Pop();switch (symbal){case "*":t = first * second;break;case "/":t = first / second;break;case "+":t = first + second;break;case "-":t = first - second;break;default:throw new Exception();}valueStack.Push(t);}else{valueStack.Push(int.Parse(symbal));}}return valueStack.Pop();}/// 遞歸表達(dá)式static void RecursionExpression(string symbal){var temp = priority.Where(x=>x.symbal == symbal).FirstOrDefault();if(temp==null) {OutputStr+= symbal + " ";return;}var stackCount = symbalStack.count;if(stackCount==0 || temp.symbal =="("){symbalStack.Push(temp);return;}if(temp.symbal ==")"){while(true){var popElement = symbalStack.Pop();OutputStr += popElement.symbal +" ";if(popElement.symbal=="("){OutputStr=OutputStr.Substring(0,OutputStr.Length -2);break;}}return;}var topElement = symbalStack.GetTop();if(temp.level > topElement.level || topElement.symbal=="("){symbalStack.Push(temp);return;}if(temp.level <= topElement.level && topElement.symbal != "("){var popElement= symbalStack.Pop();OutputStr += popElement.symbal +" ";RecursionExpression(temp.symbal);return;}} }public class Priority{public string symbal { get; set; }public int level { get; set; }} }

PS：測試的代碼比較簡單，主要看思路吧

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的数据结构基础：栈(Stack)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。