本文主要是介绍数据结构与算法_02堆栈，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数据结构与算法_02堆栈

• 堆栈
• • 1、堆栈的数组实现
  • 2、堆栈的链表实现
  • 3、堆栈的应用
  • • 汉诺塔问题
    • 算数表达式的求法
    • 中序法转为前后序法

堆栈

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");
	}
	

这篇关于数据结构与算法_02堆栈的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！