大话数据结构-栈与队列.docx

文章知识点来至于大话数据结构里边章节知识， 这篇主要介绍栈与队列在计算机中存储形式， 以及在某些算法领域中对栈和队列的相关应用。章节最后介绍了著名的逆波兰表达式， 以及通过算法来实现该表达式的运算过程。 在实现代码的同时添加了流程图。相关代码源码请查看文章最后。栈与队列1 栈结构定义2 栈的顺序存储3 两栈共享空间 思路：他们是在数组的两端，向中间靠拢top1和top2是两个栈的栈顶指针， 只要两个指针不碰头就可以 图解4 栈的链式存储5 栈的顺序存储和链式存储区别 如果栈使用过程中元素变化不可预测， 有时候小， 有时候非常大， 那么推荐用栈的链式存储。 如果一直栈的的元素变化在可控范围内， 推荐使用栈的顺序存储。6 后缀表达式 表达式：9 3 1 3 * + 10 2 / + 规则：从左到右遍历表达式中的每个数字和符号， 遇到是数字就进栈， 遇到事符号就就将栈顶两个数字取出进行计算， 运算结果进栈， 一直到最终获得结果。5 中缀表达式转后缀表达式 中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1 3 3 * + 10 2 / +” 规则：从左到右遍历表达式的每个数字和符号，若是数字就输出，就成为后缀表达式的一部分；若是符号，则判断与其栈顶符号的优先级，是右括号或者优先级低于栈顶元素则栈顶元素以此出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式。6 队列 定义：只允许在一段进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出的线性表，简称FIFO。允许插入的一段陈为队尾，允许删除的一段称为对头 循环队列 定义：我们把队列头尾相接的顺序存储结构称为循环队列7 队列的链式存储 队列的链式存储结构其实就是线性表的单链表，只不过它只能头出尾进，我们把它简称为队列。8 接下来开始对以上知识点实践运用，我们已计算器为例来说明算法对于堆栈的使用。目的是计算表达式9+(3-1)*3+10/2的运行结果首先我们熟悉下后缀表达式9 3 1 3 3 * + 10 2 / +， 他是通过中缀表达式9+(3-1)*3+10/2的来的。 关于中缀表达式转后缀表达式：中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1 3 3 * + 10 2 / +” 规则：从左到右遍历表达式的每个数字和符号，若是数字就输出，就成为后缀表达式的一部分；若是符号，则判断与其栈顶符号的优先级，是右括号或者优先级低于栈顶元素则栈顶元素以此出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式。关于后缀表达式计算： 表达式：9 3 1 3 * + 10 2 / + 规则：从左到右遍历表达式中的每个数字和符号， 遇到是数字就进栈， 遇到事符号就就将栈顶两个数字取出进行计算， 运算结果进栈， 一直到最终获得结果。9 中缀表达式转后缀表达式流程图：后缀表达式计算结果流程图：10中缀表达式转后缀表达式实现代码：public static string GetSufficExpression(string expression) var expressionArray = expression.Split( ); var operateStack = new StackLinkList(); var sufficExpression = string.Empty; for (var i = 0; i expressionArray.Length; i+) var input = expressionArrayi; if (string.IsNullOrEmpty(input) continue; if (IsNumber(input) sufficExpression += string.Format(0 , input); continue; else if (input = ) while (true) var popValue = operateStack.Pop(); if (popValue = () break; sufficExpression += string.Format(0 , popValue); else if (IsOperationChar(input) while (true) if (operateStack.IsEmpty() operateStack.Push(input); break; var popValue = operateStack.Pop(); if (!IsOperationChar(popValue) operateStack.Push(popValue); operateStack.Push(input); break; if (ComparePriority(input, popValue) = 0) sufficExpression += string.Format(0 , popValue); else operateStack.Push(popValue); operateStack.Push(input); break; else operateStack.Push(input); while (true) if (operateStack.IsEmpty() break; sufficExpression += string.Format(0 , operateStack.Pop(); return sufficExpression; 后缀表达式计算结果代码： public static string GetCalculateResult(string sufficExpression) var operateStack = new StackLinkList(); var expressionArray = sufficExpression.Split( ); for (int i = 0; i expressionArray.Length; i+) var inputChar = expressionArrayi; if (string.IsNullOrEmpty(inputChar) continue; if (!IsOperationChar(inputChar) & !IsNumber(inputChar) throw new ArgumentException(); if (IsNumber(inputChar) operateStack.Push(inputChar); else int stackTopLeft; int stackTopRight; if (!int.TryParse(operateStack.Pop(), out stackTopRight) | !int.TryParse(operateStack.Pop(), out stackTopLeft) throw new InvalidOperationException(); operateStack.Push(Caculator(inputChar, stackTopLeft, stackTopRight).ToString(CultureInfo.InvariantCulture); return operateStack.Pop(); 单元测试：private static void TestCaculator() var sufficExpression = Calculator.GetSufficExpression(9 + ( 3 - 1 ) * 3 + 10 / 2); Assert.IsEqual(sufficExpression.Trim( ), 9 3 1 - 3 * + 10 2 / +); var caculateResult = Calculator.GetCalculateResult(sufficExpression); Assert.IsEqual(caculateResult, 20); var sufficExpression1 = Calculator.GetSufficExpression(9 + ( 3 - 1 ); Assert.IsEqual(sufficExpression1.Trim( ), 9 3 1 - +); var caculateResult1 = Calculator.GetCalculateResult(sufficExpression1); Assert.IsEqual(caculateResult1, 11); var sufficExpression2 = Calculator.GetSufficExpression(9 + ( 3 - 1 ) * 2 + 8 / 2 * 3); Assert.IsEqual(sufficExpr