转载请注明出处
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，每次的余数就是结果的当中一个因子，注意先出来的因子是低位的数。能够考虑用栈来保存每次取余的结果。那么出栈的顺序就是实际的结果顺序。代码非常easy：
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] = { '>','>','<','<','<','>','>', // + '>','>','<','<','<','>','>', // - '>','>','>','>','<','>','>', // * '>','>','>','>','<','>','>', // / '<','<','<','<','<','=',' ', // ( '>','>','>','>',' ','>','>', // ) '<','<','<','<','<',' ','=', // #};// + - * / ( ) # 然后实现依据上面的思路，实现起来就比較easy了：
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