当前位置:首页 > 开发 > 编程语言 > 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

    震惊

    震惊

编辑推荐
一、 栈 1、概念 栈是一种特殊的线性表,它只能在栈顶(top)进行插入(push)和删除(pop)操作。   栈
栈实现代码: /** * 自定义栈 * @author zm * 注意体会 pop()的arr[top--] 和 push(long num)方法的
数据结构与算法是程序设计的两大基础,大型的IT企业面试时也会出数据结构和算法的题目, 它可以说明
栈的定义:栈是一种特殊的表这种表只在表头进行插入和删除操作。因此,表头对于栈来说具有特殊的意
Java集合之队列 队列Queue Queue是Java中的一个接口,继承自Collection接口。 public interface Que
栈的Java实现--顺序栈 栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按
栈的Java实现--链栈 链栈,顾名思义,就是以链表的形式实现的栈的相关操作,其实是功能弱化了的链表
题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 输入:
实现无锁的栈与队列(4) 现在我们来尝试解决前一篇文章提到的问题。 (一) 首先是内存释放的问题。 这
栈和队列----功能弱化的线性表(功能受到限制,比方说增删只能在首尾) (广度优先遍历的时候用到队列
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号