java实现 数据结构：链表、 栈、 队列、优先级队列、哈希表

时间：2021-10-24 08:40:31
 

最近在准备找工作的事情，就复习了一下java。翻了一下书和网上的教材，发现虽然很多书是用java讲数据结构的，但是侧重于将数据结构本身的知识，利用java本身的类库来实现数据结构的系统性的讲解少之又少，所以在此做一下总结，方便各位正在准备工作的和用java实现数据结构的朋友们。

附：代码下载：http://download.csdn.net/detail/sunnyskyliu/4754827

栈：

  1. void m_stack()
  2. {
  3. //Stack
  4. Stack<String> st=new Stack<String>();
  5. //Stack<Integer> st=new Stack<Integer>();
  6. st.push("1a");
  7. st.push("2b");
  8. st.push("3c");
  9. st.push("4d");
  10. System.out.println("pop is:"+st.pop());
  11. System.out.println("size is:"+st.size());
  12. System.out.println("peek is:"+st.peek());
  13. System.out.println("isEmpty is:"+st.isEmpty());
  14. System.out.println("toString is:"+st.toString());
  15. System.out.println();
  16. }

队列：

  1. void m_queue()
  2. {
  3. //Queue
  4. Queue<String> qu=new LinkedList<String>();//wrong:Queue<String> qu=new Queue<String>();
  5. qu.add("1a");
  6. qu.add("2b");
  7. qu.add("3c");
  8. qu.add("4d");
  9. //qu.offer("4d");//equal to add,but no exception
  10. System.out.println("remove is:"+qu.remove());
  11. //System.out.println("poll is:"+qu.poll());//equal to remove,but no exception
  12. System.out.println("peek is:"+qu.peek());
  13. System.out.println(qu.toString());
  14. System.out.println();
  15. }

优先级队列：

  1. class m_priorityQueue extends PriorityQueue<m_priorityQueue>
  2. implements Comparable<m_priorityQueue>
  3. {
  4. private char primary;
  5. private int secondary;
  6. private String item;
  7. public m_priorityQueue(String td,char pri,int sec){
  8. item = td;
  9. primary = pri;
  10. secondary = sec;
  11. }
  12. //for comparable
  13. public int compareTo(m_priorityQueue arg) {
  14. if(primary > arg.primary)
  15. return +1;
  16. if(primary == arg.primary)
  17. if(secondary > arg.secondary)
  18. return +1;
  19. else if(secondary == arg.secondary)
  20. return 0;
  21. return -1;
  22. }
  23. public String toString()
  24. {
  25. return Character.toString(primary)+ secondary + ": " + item;
  26. }
  27. public void add(String td,char pri,int sec)
  28. {
  29. super.add(new m_priorityQueue(td,pri,sec));
  30. }
  31. public void run()
  32. {
  33. add("sixth",'C',4);
  34. add("second",'A',2);
  35. add("fourth",'B',7);
  36. add("fifth",'C',3);
  37. add("first",'A',1);
  38. add("third",'B',1);
  39. while(!isEmpty())
  40. System.out.println(remove());
  41. }
  42. }

链表：

  1. //link list
  2. void m_linkList()
  3. {
  4. LinkedList<String> head = new LinkedList<String>();
  5. head.add("1");
  6. head.add("3");
  7. head.add(1, "2");
  8. //鏈表會自動用遍歷的方式打印所有內容
  9. System.out.println(head);
  10. System.out.println("size is:"+head.size());
  11. //利用Vector或者是ArrayList等Collection往鏈表中加數據
  12. Vector<String> v = new Vector<String>();  //need to import java.util.Vector;
  13. //LinkedList<String> v=new LinkedList<String>();
  14. //向Vector中加入東西
  15. v.add("a");
  16. v.add("b");
  17. //將當前Vector加在當前鏈表的最后
  18. head.addAll(v);
  19. System.out.println(head);
  20. //將當前Vector加在當前鏈表的指定位置
  21. head.addAll(2, v);
  22. System.out.println(head);
  23. //打印指定位置的內容
  24. System.out.println("get(2) is："+head.get(2));
  25. System.out.println("index is:"+head.indexOf(head.get(2)));
  26. head.addFirst("fist");
  27. head.addLast("last");
  28. System.out.println(head);
  29. //刪除第一個
  30. head.remove(head.getFirst());
  31. head.remove(head.getLast());
  32. System.out.println(head);
  33. //再刪除第一個，采用下標的方式，下標從0開始
  34. head.remove(0);
  35. System.out.println(head);
  36. System.out.println();
  37. }

（ 鸣谢：http://wangyu.iteye.com/blog/190762）

哈希：

  1. void m_hash()
  2. {
  3. Hashtable<String, Integer> h=new Hashtable<String, Integer>();
  4. h.put("用户1",new Integer(90));
  5. h.put("用户2",new Integer(50));
  6. h.put("用户3",new Integer(60));
  7. h.put("用户4",new Integer(70));
  8. h.put("用户1",new Integer(80));
  9. System.out.println("用户1: "+h.get("用户1"));
  10. /*
  11. //枚举
  12. Enumeration<Integer> e=h.elements();
  13. while(e.hasMoreElements())
  14. {
  15. System.out.println(e.nextElement());
  16. }*/
  17. for(Iterator<String> itor=h.keySet().iterator(); itor.hasNext();)
  18. {
  19. String word=itor.next().toString();
  20. Integer in=(Integer)h.get(word);
  21. System.out.println("word: "+word+" time："+in);
  22. }
  23. }

main调用：

  1. public static void main(String[] args) {
  2. // TODO Auto-generated method stub
  3. dataStructure da=new dataStructure();
  4. da.m_stack();
  5. da.m_queue();
  6. da.m_linkList();
  7. da.m_hash();
  8. dataStructure.m_priorityQueue pqueue=da.new m_priorityQueue(null, '0', 0);
  9. pqueue.run();
  10. }

相关文章