数据结构与算法_02堆栈
堆栈
1、堆栈的数组实现
public class StackByArray {
/**
* 用数组模拟堆栈并实现方法
*/
private int[] stack;
private int top;
public StackByArray(int stackSize) {
stack = new int[stackSize];
top = -1;//建立数组
}
//存放顶端数据，并更新堆栈的内容
public boolean push(int data){
if(top > stack.length){
System.out.println("堆栈已满，无法添加数据~");
return false;
}else {
stack[++top] = data;
return true;
}
}
//判断是否为空
public boolean isEmpty(){
return top == -1;
}
//从堆栈中弹出数据
public int pop(){
if(this.isEmpty()){
System.out.println("堆栈已空，无内容");
return -1;
}else {
return stack[top--];
}
}
}
2、堆栈的链表实现
public class StackByLink {
/**
* 堆栈的链表实现
* 随时可以改变链表的长度
*/
private Node front;//指向堆栈底端的指针
private Node rear;//指向堆栈顶端的指针
//判断堆栈是否为空
public boolean isEmpty(){
return front == null;
}
//在堆栈顶端加入数据
public void push(int data){
Node node = new Node(data);
if (this.isEmpty()){
front = node;
rear = node;
}else {
rear.next = node;
rear = node;
}
}
//从堆栈弹出数据
public int data(){
Node newNode;
if(this.isEmpty()){
System.out.println("堆栈已空，无内容~");
return -1;
}
newNode = front;
if(newNode == rear){
front = null;
rear = null;
System.out.println("空堆栈，无内容~");
return -1;
}else {
while (newNode.next != rear){
newNode = newNode.next;
}
newNode.next = rear.next;
rear = newNode;
return rear.data;
}
}
}
class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
3、堆栈的应用
汉诺塔问题
问题描述：
- 有三根木桩，第一根上有n 个盘子，最底层的盘子最大，最上层的最小。汉诺塔问题就是将所有的盘子从第一根木桩开始，以第二根为桥梁，全部搬到第三根木桩。
游戏规则：
- 每次只能从最上面移动一个盘子；
- 任何盘子可以从任何木桩搬到其他木桩
- 直径较小的盘子必须永远放在较大的盘子上
/**三个木桩分别A B C
*输入盘子的数量
*输出对应在哪根木桩进行操作
*/
public class HanoiTest {
/**
* 汉诺塔问题
*/
public static void main(String[] args) {
int m;
System.out.println("input the number of diskes:");
Scanner scanner = new Scanner(System.in);
m = scanner.nextInt();
System.out.println("The step to move %d diskes is--->>>" + m);
hanoi(m,'A','B','C');
}
public static void hanoi(int n,char one,char two,char three)
{
if(n==1)
{
move(one,three);
}
else {
hanoi(n-1,one,three,two);
HanoiTest.move(one,three);
hanoi(n-1,two,one,three);
}
}
public static void move(char x,char y)
{
System.out.println(x + "-->" + y + "\t");
}
}
算数表达式的求法
表达式的种类依据运算符在表达式中的位置。分为三种
- 中序法：<操作数1> <运算符> <操作数2>
- 前序法：<运算符> <操作数1> <操作数2>
- 后序法：<操作数1> <操作数2> <运算符>
1、中序法求值
- 建立两个堆栈，分别存放运算符及操作数
- 取出运算符时，必须先比较堆栈内的运算符优先权，若堆栈内运算符放入优先权较高，则计算堆栈内的运算符的值
- 计算时，取出一个运算符和两个操作数进行计算，运算结果直接存回操作数堆栈中，成为一个独立的操作数
- 当表达式处理完毕后，一步一步清除运算符堆栈，知道栈空为止
- 取出操作数堆栈中的值就是计算结果
2、前序法求值
前序法求值的优点是不需要考虑括号及优先权的问题 - 从堆栈中取出元素
- 从堆栈中取出元素，遇到运算符进行运算，结果存回操作数栈
- 从堆栈中取出元素，
- 从堆栈中取出元素，遇到运算符进行运算，结果存回操作数栈
- 完成：把堆栈中的最后一个运算符取出，从操作数堆栈中取出两个操作数进行运算，运算结果存回操作数栈，最后取出的值就是运算结果
3、后序法求值
后序法求值的优点是没有优先权的问题，后序表达式可以直接在计算机上面进行运算，而不需先将全部数据放入堆栈在进行运算，使用循环直接读取表达式
中序法转为前后序法
1、括号法
中序转为前序
- 将中序表达式根据顺序完全括起来
- 移动所有的运算法来代替所有的左括号，并以最近者为原则
- 将所有左括号去掉
中序转为后序 - 将中序表达式根据顺序完全括起来
- 移动所有的运算法来代替所有的右括号，并以最近者为原则
- 将所有右括号去掉
2、堆栈法
ISP 堆栈内优先权 ICP 输入优先权
中序转为前序
- 由右至左读进中序表达式的每个字符
- 如果输入为操作数则直接输出
- “)” 在堆栈内的优先权最小，但在堆栈外的优先权最大
- 如果遇到“(” ，则弹出堆栈内的运算符，直至弹到“)” 为止
- 如果ISP > ICP, 则将堆栈内的运算符弹出，否则就加入到堆栈内
中序转为后序
- 由左至右读进中序表达式的每个字符
- 如果输入为操作数则直接输出
- 如果ISP >= ICP, 则将堆栈内的运算符弹出，否则就加入到堆栈内
- “(” 在堆栈内的优先权最小，但在堆栈外的优先权最大
- 如果遇到“)” ，则弹出堆栈内的运算符，直至弹到“(” 为止
中序转为后序的算法
class 类{
static int MAX=50;
static char[] infix_q = new char[MAX];
//构造函数
CH04_07 ()
{
int i=0;
for (i=0; i<MAX; i++)
infix_q[i]='\0';
}
// 运算符优先权的比较，若输入运算符小于堆栈中运算符，则返回值为1，否则为0
public static int compare(char stack_o, char infix_o){
// 在中序表示法队列及暂存堆栈中，运算符的优先级表，其优先权值为INDEX/2
char[] infix_priority = new char[9] ;
char[] stack_priority = new char[8] ;
int index_s=0, index_i=0;
infix_priority[0]='q';infix_priority[1]=')';
infix_priority[2]='+';infix_priority[3]='-';
infix_priority[4]='*';infix_priority[5]='/';
infix_priority[6]='^';infix_priority[7]=' ';
infix_priority[8]='(';
stack_priority[0]='q';stack_priority[1]='(';
stack_priority[2]='+';stack_priority[3]='-';
stack_priority[4]='*';stack_priority[5]='/';
stack_priority[6]='^';stack_priority[7]=' ';
while (stack_priority[index_s] != stack_o)
index_s++;
while (infix_priority[index_i] != infix_o)
index_i++;
return ((int)(index_s/2) >= (int)(index_i/2) ? 1 : 0);
}
//中序转为后序的算法
public static void infix_to_postfix(){
new DataInputStream(System.in);
int rear=0, top=0, flag=0,i=0;
char[] stack_t = new char[MAX];
for (i=0; i<MAX; i++)
stack_t[i]='\0';
while (infix_q[rear] !='\n') {
System.out.flush();
try {
infix_q[++rear] = (char)System.in.read();
} catch (IOException e) {
System.out.println(e);
}
}
infix_q[rear-1] = 'q'; // 在队列中加入q为结束符号
System.out.print("\t后序表示法 : ");
stack_t[top] = 'q'; // 在堆栈中加入#为结束符号
for (flag = 0; flag <= rear; flag++) {
switch (infix_q[flag]) {
// 输入为)，则输出堆栈内运算符，直到堆栈内为(
case ')':
while(stack_t[top]!='(')
System.out.print(stack_t[top--]);
top--;
break;
// 输入为q，则将堆栈内还未输出的运算符输出
case 'q':
while(stack_t[top]!='q')
System.out.print(stack_t[top--]);
break;
// 输入为运算符，若小于TOP在堆栈中所指运算符，则将堆栈所指运算符输出
// 若大于等于TOP在堆栈中所指运算符，则将输入的运算符放入堆栈
case '(':
case '^':
case '*':
case '/':
case '+':
case '-':
while (compare(stack_t[top], infix_q[flag])==1)
System.out.print(stack_t[top--]);
stack_t[++top] = infix_q[flag];
break;
// 输入为操作数，则直接输出
default :
System.out.print(infix_q[flag]);
break;
}
}
}
//主函数测试
public static void main (String args[]){
new 本类();
System.out.print("\t==========================================\n");
System.out.print("\t本程序会将其转成后序表达式\n");
System.out.print("\t请输入中序表达式\n");
System.out.print("\t例如:(9+3)*8+7*6-12/4 \n");
System.out.print("\t可以使用的运算符包括:^,*,+,-,/,(,)等\n");
System.out.print("\t==========================================\n");
System.out.print("\t请开始输入中序表达式: ");
本类.infix_to_postfix();
System.out.print("\t==========================================\n");
}