轉載請注明出處 http://blog.csdn.net/pony_maggie/article/details/30802249 作者:小馬 作為一種常用的數據結構, 了解棧對于算法的學習是非常必要的。棧有先進后出的特點，棧底指向數據表中的第一個元素，棧頂指向最后一個元素的下一個位置。如下圖所示:  棧和線性表類似，也是有兩種存儲結構，分別為順序結構和鏈式結構。大部分情況下，棧使用前者，這和它的使用場景有關，因為通常情況下我們不會對棧進行頻繁地，隨機地插入，刪除操作。下面是我用順序結構實現的棧，這個棧有個特點就是它的通用性，因為我并沒有限制它所存儲的數據類型，代碼如下: ~~~ //void**其為雙指針，意味入棧和出棧的將只是對應數據的地址，而不需要對數據本身進行拷貝 typedef struct { char *base; char *top; int elementSize; //元素所點字節大小 int stackSize; //當前已分配的空間(注意不是元素的實際個數) }ponyStack; int InitStack(ponyStack *stack, int elementSize) { stack->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char)*elementSize); if (!stack->base) { return RET_ERROR; } stack->top = stack->base; //為空 stack->stackSize = STACK_INIT_SIZE; stack->elementSize = elementSize; return RET_OK; } int ClearStack(ponyStack *stack) { stack->top = stack->base; return RET_OK; } bool IsEmptyStack(ponyStack stack) { if (stack.top == stack.base) { return true; } return false; } ~~~ 這里沒有貼出全部的代碼，更完整的可以從最后的地址那里下載。注意elementSize,這個是棧可以做到通用的核心。不理解的可以再研究一下代碼。 看一個棧的使用示例，數制轉換。十進制轉八進制。例如(1348)十進制= (2504)八進制,它基于如下的原理: N ? ? ? ? ? ? N/8???????????? N%8 1348 ? ? ? ?168 ? ? ? ? ? ? ? 4 168 ? ? ? ? ? 21 ? ? ? ? ? ? ? ?0 ?21 ? ? ? ? ? ? 2 ? ? ? ? ? ? ? ? ?5 ?2 ? ? ? ? ? ? ? 0 ? ? ? ? ? ? ? ? ? 2 所以很明顯，N不斷的除8，每次的余數就是結果的其中一個因子，注意先出來的因子是低位的數，可以考慮用棧來保存每次取余的結果，那么出棧的順序就是實際的結果順序。代碼很簡單： ~~~ int decimalToOctonary(int decimalNumber) { double octNumber = 0; int nCount = 0; int nTemp = 0; ponyStack numberStack; InitStack(&numberStack, 4); while (decimalNumber) { nTemp = (int)decimalNumber%8; Push(&numberStack, &nTemp); decimalNumber = decimalNumber/8; } nCount = CountOfStack(numberStack);//元素個數也就是位數 while(!IsEmptyStack(numberStack)) { Pop(&numberStack, &nTemp); octNumber += (nTemp*pow(10.0, --nCount)); } DestroyStack(&numberStack); return (int)octNumber; } ~~~ 再來看一個行編輯程序的示例，用戶在終端輸入字符，完成后保存用戶的數據區， 因為在輸入的過程中可能出錯，需要修改，所以不可能每輸入一個字符就存入數據區。比較好的做法是先在內存里開一個輸入的緩沖區，當用戶輸入完成一行后，再存入數據區。在行內可以修改。例如，當用戶發現剛輸入的一個字符是錯的之后，可以再輸入一個'#',表示前一個字符是錯的，如果發現當前行輸入的錯誤太多，可以輸入一個退行符'@',表示當前行都無效，舉個例子: whli#ilr#e(s#*s) outcha@putchar(*s=#++) 實際有效的字符是這樣的: while(*s) putchar(*s++) 可以把內存里這個輸入緩沖區定為棧,正常情況下每輸入一個字符直接入棧，如果發現字符是'#',就棧頂pop一次，如果是'@'就清空棧.代碼實現如下: ~~~ void lineEdit() { char ch = 0; char chTemp = 0; ponyStack lineStack; InitStack(&lineStack, 1); ch = getchar(); while (ch != EOF) { while (ch != EOF && ch != '\n') { switch (ch) { case '#': Pop(&lineStack, &chTemp); break; case '@': ClearStack(&lineStack); break; default: Push(&lineStack, &ch); break; } ch = getchar(); } writeToFile(lineStack);//存數據 ClearStack(&lineStack);//準備接收下一行 if (ch != EOF) { ch = getchar(); } } DestroyStack(&lineStack); } ~~~ 最后一個例子是表達式求值的算法，這個在計算器應用中比較多用到。比如， 求+4*9-16/4 建兩個棧，一個存操作數，一個存運算符.為簡單起，在運算符棧會預先存一個'#',表示表達式開始，然后以'#'結束。運算規則是這樣的: 輸入字符，如果是'#'，則結束，如果是操作數，直接進操作數棧。如果是運算符，則跟棧頂的運算符比較，如果棧頂的優先級低,直接進棧，接收下一字符，如果相等，脫括號，接收下一個字符，如果棧頂的優先級高，pop兩個操作數，pop棧內操作符，運算，然后運算的結果進操作數棧。當前運算符繼續跟棧頂比較。 要實現這個代碼，首先要有一個表格，存儲我們操作符之間的優先級關系，如下所示: ~~~ static char priority[7][7] = { '>','>','<','<','<','>','>', // + '>','>','<','<','<','>','>', // - '>','>','>','>','<','>','>', // * '>','>','>','>','<','>','>', // / '<','<','<','<','<','=',' ', // ( '>','>','>','>',' ','>','>', // ) '<','<','<','<','<',' ','=', // # };// + - * / ( ) # ~~~ 然后實現根據上面的思路，實現起來就比較容易了： ~~~ int evaluateExpression() { char chCurrent = 0; char chOnTop = 0; char chTemp = 0; int nResult = 0; int nTemp = 0; int a,b; int nOperandFlag = 0; ponyStack operatorStack;//運算符棧 ponyStack operandStack; //操作數棧 InitStack(&operatorStack, 1); chTemp = '#'; Push(&operatorStack, &chTemp); InitStack(&operandStack, 4); chCurrent = getchar(); GetTop(operatorStack, &chOnTop); while ((chCurrent != '#')||(chOnTop != '#')) { if (!isOperator(chCurrent))//是操作數,要考慮多位整型數的情況 { nTemp = nTemp * (int)pow(10.0, nOperandFlag); nTemp += (int)(chCurrent - '0'); chCurrent = getchar(); nOperandFlag = 1; } else { if (nOperandFlag == 1) { Push(&operandStack, &nTemp);//操作數輸入結束，入棧 nOperandFlag = 0; nTemp = 0; } GetTop(operatorStack, &chOnTop); switch (precede(chOnTop, chCurrent))//比較優先級 { case '<': //棧頂的優先級小 Push(&operatorStack, &chCurrent); chCurrent = getchar(); GetTop(operatorStack, &chOnTop); break; case '=': //脫括號，接收下個字符 Pop(&operatorStack, &chTemp); chCurrent = getchar(); GetTop(operatorStack, &chOnTop); break; case '>': //棧頂的優先級大，出棧運算，結果入棧 { Pop(&operandStack, &a); Pop(&operandStack, &b); Pop(&operatorStack, &chTemp); nTemp = operate(a, chTemp, b); Push(&operandStack, &nTemp); nTemp = 0;//重置 GetTop(operatorStack, &chOnTop); } break; default: break; } } } GetTop(operandStack, &nResult); DestroyStack(&operatorStack); DestroyStack(&operandStack); return nResult; } ~~~ 代碼下載地址: https://github.com/pony-maggie/StackDemo 或 http://download.csdn.net/detail/pony_maggie/7499167