当前位置:首页 > 开发 > 编程语言 > Java > 正文

java栈和队列的实现

发表于: 2014-06-14   作者:bughope   来源:转载   浏览:
摘要: java栈实际上就像一个盒子模型.先放进去的要向拿出了必须先把后放进去的拿出来.先进后出. 实现比较简单.直接贴代码,没有什么好说的. //底层实现是一个数组 private long[] arr; private int top; /** * 默认的构造方法 */ public MyStack() { arr = new long[10]; to

java栈实际上就像一个盒子模型.先放进去的要向拿出了必须先把后放进去的拿出来.先进后出.

实现比较简单.直接贴代码,没有什么好说的.

//底层实现是一个数组
	private long[] arr;
	private int top;
	
	/**
	 * 默认的构造方法
	 */
	public MyStack() {
		arr = new long[10];
		top = -1;
	}
	
	/**
	 * 带参数构造方法,参数为数组初始化大小
	 */
	public MyStack(int maxsize) {
		arr = new long[maxsize];
		top = -1;
	}
	
	/**
	 * 添加数据
	 */
	public void push(int value) {
		arr[++top] = value;
	}
	
	/**
	 * 移除数据
	 */
	public long pop() {
		return arr[top--];
	}
	
	/**
	 * 查看数据
	 */
	public long peek() {
		return arr[top];
	}
	
	/**
	 * 判断是否为空
	 */
	public boolean isEmpty() {
		return top == -1;
	}
	
	/**
	 * 判断是否满了
	 */
	public boolean isFull() {
		return top == arr.length - 1;
	}

 对于队列呢?由于队列的实现特殊性,在添加最后一位元素后会出现假的溢出(实际上这个数组前面可能有空位),这里实现一个循环的队列.节约空间.

对于所有的数据结构都一样,必须有临界值的判断.

想了很久,要判断循环队列的空值或者是满了.直接判断队列的首尾坐标很难判断.

于是想到一个很简单又很容易理解的办法.创建一个变量来保存初始化的最大个数.

package org.masque.queue;

/**
 * QueueArray.java
 */
/**
 * 数组实现的循环队列
 * @author masque.java@gmail.com
 */
public class QueueArray {
	Object[] a;
	int front;  
	int rear;   
	
	private int size = 0;
	
	private int maxSize;
	
	public static final int DEFAULT_MAX_SIZE = 1000;
	
	public QueueArray(){
		this(DEFAULT_MAX_SIZE);
	}
    public QueueArray(int size){
		a = new Object[size];
		front = 0;
		rear =0;
		maxSize = size;
	}
    /**
     * 将一个对象追加到队列尾部
     * @param obj 对象
     * @return 队列满时返回false,否则返回true
     */
    public boolean insert(Object obj){
    	if(isFull()){
    		throw new RuntimeException("insert ["+obj+"] fail,the queue is full!");
    	}
    	a[rear]=obj;
    	rear = (rear+1)%(a.length);//若坐标到达最大就重置为0
    	size++;
    	return true;
    }
    /**
     * 队列头部的第一个对象出队
     * @return 出队的对象,队列空时返回null
     */
    public Object remove(){
    	if(isEmpty()){
    		throw new RuntimeException("remove fail,the queue is empty!");
    	}
    	size--;
    	Object obj = a[front];
    	front = (front+1)%(a.length);//若坐标到达最大就重置为0
    	return obj;
    }
    
    public boolean isEmpty(){
    	return size == 0;
    }
    
    public boolean isFull(){
    	return maxSize == size;
    }
    
	public static void main(String[] args) {
		QueueArray q = new QueueArray(4);
		/*System.out.println(q.isEmpty());*/
		System.out.println("----------------------------------");
		System.out.println(q.insert("张三"));
		
		System.out.println(q.insert("李斯"));
		System.out.println(q.insert("赵五"));
		System.out.println(q.insert("张三"));
		System.out.println(q.insert("赵五2"));
		/*System.out.println(q.isFull());*/
		System.out.println("----------------------------------");
		for(int i=0;i<5;i++){
			System.out.println(q.remove());
		}
		System.out.println(q.insert("张三"));
		System.out.println(q.insert("李斯"));
		System.out.println(q.insert("赵五"));
	}
}

 又更简洁的办法欢迎留言指导,谢谢!

java栈和队列的实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号