您的位置: 首页  >  文章  >  堆栈和队列的实现

堆栈和队列的实现

分类: 文章 • 2025-05-28 22:49:22

1.使用数组实现,代码和结果如下所示:

要求：

写Stack.java，实现堆栈功能，使用int数组保存数据特点：先进后处 后进先出   

写Queue.java，实现队列功能，使用int数组保存数据特点：先进先出 后进后出  使用Test.java对堆栈和队列进行测试

如下所示，分别为实现方法：

首先实现stack.java类，其代码如下所示：

[java] view plain copy
  1. package ex.md05;  
  2. public class Stack  
  3. {  
  4.     private int[] a=new int[1000];  
  5.     private int i=0;  
  6.     public void push(int m)  
  7.     {  
  8.       a[++i]=m;  
  9.     }  
  10.     public int pop()  
  11.     {  
  12.       if(i>0)  
  13.       {  
  14.          return  a[i--];  
  15.       }  
  16.            else return  -1;  
  17.     }  
  18. }  
接着实现队列Queue.java代码，具体如下所示：

[java] view plain copy
  1. package ex.md05;  
  2. public class Queue  
  3. {  
  4.     int[] a=new int[1000];  
  5.     private int i=1;  
  6.     public void in(int m)  
  7.     {  
  8.        a[i++]=m;  
  9.     }  
  10.     public int out()  
  11.     {  
  12.        int k=1;  
  13.        int index=0;  
  14.        int temp=a[k];  
  15.        for(int j=k;j<i;j++)  
  16.        {  
  17.          a[j-1]=a[j];  
  18.          index++;  
  19.        }  
  20.          i=index;  
  21.        return temp;  
  22.     }  
  23. }  
最后，我们实现测试类Test.java，观察逻辑是否正确

[java] view plain copy
  1. package ex.md05;  
  2.   
  3. public class Test   
  4. {  
  5.     public static void main(String[] args)   
  6.     {  
  7.         Stack stack = new Stack();  
  8.         //stack.pop();  
  9.         System.out.println("Stack push()---1-200--------");  
  10.         for(int i=1; i<=200; i++){  
  11.             stack.push(i);  
  12.         }  
  13.         System.out.println("Stack pop()---1-100--------");  
  14.         for(int i=1; i<=100; i++){  
  15.             System.out.println("pop:" + stack.pop());  
  16.         }  
  17.         System.out.println("Stack push()---201-300--------");  
  18.         for(int i=201; i<=300; i++){  
  19.             stack.push(i);  
  20.         }  
  21.         System.out.println("Stack pop()---1-200--------");  
  22.         for(int i=1; i<=200; i++){  
  23.             System.out.println("pop:" + stack.pop());  
  24.         }  
  25.   
  26.         Queue queue = new Queue();  
  27.         //queue.out();  
  28.         System.out.println("Queue in()---1-200--------");  
  29.         for(int i=1; i<=200; i++){  
  30.             queue.in(i);  
  31.         }  
  32.         System.out.println("Queue out()---1-100--------");  
  33.         for(int i=1; i<=100; i++){  
  34.             System.out.println("out:" + queue.out());  
  35.         }  
  36.         System.out.println("Queue in()---201-300--------");  
  37.         for(int i=201; i<=300; i++){  
  38.             queue.in(i);  
  39.         }  
  40.         System.out.println("Queue out()---1-200--------");  
  41.         for(int i=1; i<=200; i++){  
  42.             System.out.println("out:" + queue.out());  
  43.         }  
  44.     }  
  45. }  

编译运行之后，我们能够看到运行结果如下所示：

堆栈和队列的实现

根据分析，我们的运行结果是正确的（以上只是部分结果，下面是运行后的所有结果，请下载查看http://download.****.net/my）

2.使用list来实现功能,代码如下所示:

写MyStack类，实现堆栈功能。在类中使用ArrayList保存数据。
写MyQueue类，实现队列功能。在类中使用ArrayList保存数据。
使用Test.java测试堆栈和队列

首先实现MyStack.java代码:

[java] view plain copy
  1. package sample;  
  2. import java.util.*;  
  3. public class MyStack  
  4. {  
  5.     List<Integer> list = new ArrayList<Integer>();  
  6.         Iterator it=list.iterator();  
  7.     int index=0;  
  8.     public MyStack(){}  
  9.     public void push(Integer i)  
  10.     {  
  11.           list.add(i);  
  12.           index++;  
  13.     }  
  14.     public Integer pop()  
  15.     {  
  16.        if(!(list.isEmpty()))  
  17.        {  
  18.            index--;  
  19.          return (Integer)list.remove(index);  
  20.        }  
  21.        return null;  
  22.     }  
  23. }  
实现MyQueue.java类:

[java] view plain copy
  1. package sample;  
  2. import java.util.*;  
  3. public class MyQueue  
  4. {  
  5.     List<Integer> list = new ArrayList<Integer>();  
  6.         Iterator it=list.iterator();  
  7.     int index=0;  
  8.     public MyQueue(){}  
  9.     public void in(Integer i)  
  10.     {  
  11.           list.add(i);  
  12.           index++;  
  13.     }  
  14.     public Integer out()  
  15.     {  
  16.        if(!(list.isEmpty()))  
  17.        {  
  18.           Integer temp=0;  
  19.               temp=(Integer)list.get(0);  
  20.          list.remove(0);  
  21.              index--;  
  22.          return temp;  
  23.        }  
  24.        return null;  
  25.     }  
  26. }  
使用Test类进行测试,代码如下所示:

[java] view plain copy
  1. package sample;  
  2.   
  3. public class Test   
  4. {  
  5.     public static void main(String[] args)   
  6.     {  
  7.         MyStack stack = new MyStack();  
  8.         stack.push(new Integer(1));  
  9.         stack.push(new Integer(2));  
  10.         stack.push(new Integer(3));  
  11.         System.out.println(stack.pop());  
  12.         stack.push(new Integer(4));  
  13.         System.out.println(stack.pop());  
  14.         System.out.println(stack.pop());  
  15.         System.out.println(stack.pop());  
  16.         System.out.println(stack.pop());  
  17.         stack.push(new Integer(5));  
  18.         System.out.println(stack.pop());  
  19.         System.out.println(stack.pop());  
  20.         System.out.println("------------------------");  
  21.         MyQueue queue = new MyQueue();  
  22.         queue.in(new Integer(1));  
  23.         queue.in(new Integer(2));  
  24.         queue.in(new Integer(3));  
  25.         System.out.println(queue.out());  
  26.         queue.in(new Integer(4));  
  27.         System.out.println(queue.out());  
  28.         System.out.println(queue.out());  
  29.         System.out.println(queue.out());  
  30.         System.out.println(queue.out());  
  31.         queue.in(new Integer(5));  
  32.         System.out.println(queue.out());  
  33.         System.out.println(queue.out());  
  34.     }  
  35. }  
结果如下所示:

堆栈和队列的实现

以上就是堆栈的两种实现方法

相关推荐