轉載請注明出處
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