【数据结构】栈与队列（二）

3.5 栈的应用

3.5.1 大数加法

p76

9992992347234947324732498327427342472987427427984724274

+

  9990920943824283492834824820984028348204209384029293

• 思路：9293 + 978
  

3.5.2 后缀表达式

p79

• 中序表达式：日常生活中编写的都是中序表达式。

a + b - c

后缀表达式：把运算符写在后面的表达式，也称为逆波兰记法

中序：a+b              后缀：ab+

中序：a + b - c        后缀：ab+c-

中序：a + b * c        后缀：abc*+

• 除运算符之外的内容，依次填写
  
• 使用一个栈记录运算符

• 入栈：新入栈的运算符比栈里的运算符优先级要高。如果是(进行入栈操作
  
• 出栈：新入栈的运算符没有栈里的运算符优先级高，栈里的运算符需要出栈，新运算符入栈。如果是)出栈直到(
  

将以下中序表达式转换成后续表达式

中序：8-(3+2*6)/5+2^2          后缀：8326*+5/-22^+

中序：2*9+3-2*(10-3)/14        后缀：29*3+2103-*14/-

中序：A+B*(C*D-E)              后缀：ABCD*E-*+

中序：a+b*c+(d*e+f)*g          后缀：abc*+de*f+g*+

中序：9+(3-1)*3+10/2           后缀：931-3*+102/+

3.5.3 汉诺塔 Hanoi

• 游戏规则 （P84）
  

共3个柱子，在一根柱子上，从下往上按照大小顺序摞着N片圆盘。把圆盘开始按大小顺序重新摆放在另一根柱子上

规定：在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

算法：

packagehanoi;
​/*** @author 桐叔* @email liangtong@itcast.cn*/publicclassTestHanoi {
privatestaticintcount=0;
/**** @param n 需要移动的盘子数* @param x 第一个柱子 起始* @param y 第二个柱子 过渡* @param z 第三个柱子 最后*/publicstaticvoidhanoi(intn, charx, chary , charz) {
if(n==1) {      //只有一个盘子move(x, 1, z);
        } else {
hanoi(n-1, x, z ,y);     // n上面的盘子，从x柱子，通过z柱子，移动到y柱子move(x, n, z);              //n盘子，从x柱子，移动到z柱子hanoi(n-1, y, x, z);    // n上面的盘子目前在y柱子，从y柱子，通过x柱子，移动到z柱子。        }
    }
​/**** @param x 第一个柱子* @param n 需要移动的盘子号* @param z 第三个柱子*/privatestaticvoidmove(charx, intn, charz) {
count++;
System.out.println("第"+count+"次移动"+n+"号盘子，从"+x+"柱子到"+z+"柱子");
    }
​publicstaticvoidmain(String[] args) {
hanoi(4,'x','y','z');
    }
}
​

3.6 队列

3.6.1 定义

• 队列是一个特殊的线性表。

• 只允许在表尾进行插入操作
  

• 只允许在表头进行删除操作
  

• 队列操作特点：

• 先进先出（FIFO，First In First Out）
  
• or 后进后出（LILO，Last In Last Out）
  

• 术语：

• 队尾rear：进行插入操作的一端。
  
• 队首front：进行删除操作的一端。
  
• 入队offer：进行插入操作，称为入队。
  
• 出队poll：进行删除操作，称为出队。
  

• 队列两种存储结果分类：

• 使用顺序存储的称为顺序队列
  
• 使用链式存储称为链队列。
  

3.7 顺序队列

3.7.1 顺序队列

• 顺序队列的存储结构中，需要分配一块地址连续的存储区域来一次存放队列中从队首到队尾的所有元素。
  
• 操作总结：
  

• front表示队首，进行出队操作时，front进行计数。
  
• rear表示队尾，进行入队操作时，rear进行计数。
  
• front == rear == 0 空队列。
  

• 操作步骤：

• 入队操作：
  

3.7.2 循环顺序队列

• 循环顺序队列：就是在逻辑上队首和队尾连接在一起。
  
• 存在问题：队首front和队尾rear重叠时，无法表示队列是满了，还是空的。
  
• 解决方案：
  
• 方案1：设计一个计数器（整数变量num，入队+1，出队-1，如果num=0就是空）
  
• 方案2：设计一个标识变量（flag=0出队，flag=1入队，重叠后0表示空，1表示满）
  
• 方案3：少用一个存储单位
  

// 队列空front==rear;
// 队列满(rear+1) %maxSize==front;
​//余数操作5%5=0;
2%5=2;  

3.7.3 循环顺序队列类

• 循环顺序队列，在逻辑上是一个循环，也就是队首和队尾连接。
  
  

publicClassCircleQueue {
privateObject[] queueElem;     //物理数组privateintfront;              //队首privateintrear;               //队尾}

3.7.4 算法：循环顺序队列入队【重点】

publicvoidoffer(Objectx) {
if( (rear+1) %queueElem.length==front ) {  // 1.判断，如果已经满了，抛异常thrownewRuntimeException('队列满了');
    } else {
queueElme[ rear ] =x;                   // 2.没有满进行入队操作rear= (rear+1) %queueElem.length;    // 3.队尾rear累加1，但最后时需要归零    }
}

3.7.5 算法：循环顺序队列出队【重点】

publicObjectpoll() {
if( front==rear ) {                       // 判断 空 返回nullreturnnull;
    } 
Objectdata=queueElem[front];             // 如果不为空，获得队首front元素front= (front+1) %queueElem.length;     // 队首+1，且需要归零  returndata;
}