1. 栈

数据结构与算法分析java——栈和队列-LMLPHP

1.1 分类

  顺序栈:顺序线性表实现

  链式栈:单向链表存储堆栈

1.2栈的应用

1)数制转换

数据结构与算法分析java——栈和队列-LMLPHP

import java.util.Scanner;

import java.util.Stack;

public class Tran{

    public static void main(String arg[]){

     Scanner y=new Scanner(System.in);

     System.out.println("请输入十进制数");

     int b=y.nextInt();

     Tran j=new  Tran();

     j.ErJinZhi(b);

     j.BaJinZhi(b);

     j.ShiLiuJinZhi(b);

    }

  //转化成二进制

  void ErJinZhi(int a){

    Stack<Integer> s=new Stack<Integer>();

    String str="";

    while(a>0)

    {

     s.push(a%2);

     a=a/2;

    }

    while(!s.isEmpty()){

     str=str+s.pop();

    }

  System.out.println("二进制是"+str);

  }

  //转化成八进制

  void BaJinZhi(int a){

  Stack<Integer> s=new Stack<Integer>();

    String str="";

    while(a>0)

    {

     s.push(a%8);

     a=a/8;

    }

    while(!s.isEmpty()){

     str=str+s.pop();

    }

   System.out.println("八进制是"+str);

  }

  //转化成十六进制

  void ShiLiuJinZhi(int a){

   int c=0;

   String str="";

   Stack<Character> s=new Stack<Character>();

   while(a>0)

   {

    c=a%16;

    switch(c){

    case(10):s.push('A');break;

    case(11):s.push('B');break;

    case(12):s.push('C');break;

    case(13):s.push('D');break;

    case(14):s.push('E');break;

    case(15):s.push('F');break;

    default:s.push((char)(a%16+48));

    }

    a=a/16;

   }

   while(!s.isEmpty()){

    str=str+s.pop();

   }

   System.out.println("十六进制是"+str);

  }

}

2)表达式的转换

中缀表达式: a+b*c ;  前缀表达式: +a*bc;  后缀表达式: acb*+

数据结构与算法分析java——栈和队列-LMLPHP

参考:  http://blog.csdn.net/antineutrino/article/details/6763722/

3)递归

4)递归的非递归实现

2. 队列

2.1 队列基本操作

数据结构与算法分析java——栈和队列-LMLPHP

2.2 顺序队列 和链式队列

3. Stack类

数据结构与算法分析java——栈和队列-LMLPHP

import java.util.*;

public class StackDemo {

   static void showpush(Stack st, int a) {
st.push(new Integer(a));
System.out.println("push(" + a + ")");
System.out.println("stack: " + st);
} static void showpop(Stack st) {
System.out.print("pop -> ");
Integer a = (Integer) st.pop();
System.out.println(a);
System.out.println("stack: " + st);
} public static void main(String args[]) {
Stack st = new Stack();
System.out.println("stack: " + st);
showpush(st, 42);
showpush(st, 66);
showpush(st, 99);
showpop(st);
showpop(st);
showpop(st);
try {
showpop(st);
} catch (EmptyStackException e) {
System.out.println("empty stack");
}
}
}
stack: [ ]
push(42)
stack: [42]
push(66)
stack: [42, 66]
push(99)
stack: [42, 66, 99]
pop -> 99
stack: [42, 66]
pop -> 66
stack: [42]
pop -> 42
stack: [ ]
pop -> empty stack
05-11 22:17
查看更多