Java ArrayDeque实现Stack的功能

在J2SE6引入了ArrayDeque类，它继承了Deque(双向队列)接口，使用此类可以自己实现java.util.Stack类的功能，去掉了java.util.Stack的多线程同步的功能。

例如创建一个存放Integer类型的Stack，只要在类中创建一个ArrayDeque类的变量作为属性，之后定义的出栈、入栈，观察栈顶元素的操作就直接操作ArrayDeque的实例变量即可。

import java.util.ArrayDeque;
import java.util.Deque; 

public class IntegerStack {
  private Deque<Integer> data = new ArrayDeque<Integer>(); 

  public void push(Integer element) {
    data.addFirst(element);
  } 

  public Integer pop() {
    return data.removeFirst();
  } 

  public Integer peek() {
    return data.peekFirst();
  } 

  public String toString() {
    return data.toString();
  } 

  public static void main(String[] args) {
    IntegerStack stack = new IntegerStack();
    for (int i = 0; i < 5; i++) {
      stack.push(i);
    }
    System.out.println(stack);
    System.out.println("After pushing 5 elements: " + stack);
    int m = stack.pop();
    System.out.println("Popped element = " + m);
    System.out.println("After popping 1 element : " + stack);
    int n = stack.peek();
    System.out.println("Peeked element = " + n);
    System.out.println("After peeking 1 element : " + stack);
  }
}

java.util.ArrayDeque的源码：

private transient E[] elements;
 private transient int head;
 private transient int tail; 

/*此处存放e的位置是从elements数组最后的位置开始存储的*/
 public void addFirst(E e) {
    if (e == null)
      throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//首次数组容量默认为16，head=（0-1）&(16-1)=15
    if (head == tail)
      doubleCapacity();
  } 

/*每次扩容都按插入的先后顺序重新放入一个新的数组中，最新插入的放在数组的第一个位置。*/
  private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
      throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = (E[])a;
    head = 0;
    tail = n;
  } 

  public E removeFirst() {
    E x = pollFirst();
    if (x == null)
      throw new NoSuchElementException();
    return x;
  } 

  public E pollFirst() {
    int h = head;
    E result = elements[h]; // Element is null if deque empty
    if (result == null)
      return null;
    elements[h] = null;   // 重新设置数组中的这个位置为null，方便垃圾回收。
    head = (h + 1) & (elements.length - 1);//将head的值回退，相当于将栈的指针又向下移动一格。例如，12--〉13
    return result;
  } 

  public E peekFirst() {
    return elements[head]; // elements[head] is null if deque empty
  }

以上就是本文的全部内容，希望对大家学习java程序设计有所帮助。

赞 (0)

相关推荐

  • Java ArrayDeque使用方法详解

    题目要求为: 卡拉兹(Callatz)猜想: 对任何一个自然数n,如果它是偶数,那么把它砍掉一半:如果它是奇数,那么把(3n+1)砍掉一半.这样一直反复砍下去,最后一定在某一步得到n=1.当我们验证卡拉兹猜想的时候,为了避免重复计算,可以记录下递推过程中遇到的每一个数.例如对n=3进行验证的时候,我们需要计算3.5.8.4.2.1,则当我们对n=5.8.4.2进行验证的时候,就可以直接判定卡拉兹猜想的真伪,而不需要重复计算,因为这4个数已经在验证3的时候遇到过了,我们称5.8.4.2是被3"覆盖

  • Java集合ArrayDeque类实例分析

    Java集合ArrayDeque类实例分析 前言 ArrayDeque类是双端队列的实现类,类的继承结构如下面,继承自AbastractCollection(该类实习了部分集合通用的方法,其实现了Collection接口),其实现的接口Deque接口中定义了双端队列的主要的方法,比如从头删除,从尾部删除,获取头数据,获取尾部数据等等. public class ArrayDeque<E> extends AbstractCollection<E> implements Deque&

  • java.util.ArrayDeque类使用方法详解

    本文为大家介绍了java.util.ArrayDeque类使用方法,供大家参考,具体内容如下 1. ArrayDeque有两个类属性,head和tail,两个指针. 2. ArrayDeque通过一个数组作为载体,其中的数组元素在add等方法执行时不移动,发生变化的只是head和tail指针,而且指针是循环变化,数组容量不限制. 3. offer方法和add方法都是通过其中的addLast方法实现,每添加一个元素,就把元素加到数组的尾部,此时,head指针没有变化,而tail指针加一,因为指针是

  • Java ArrayDeque实现Stack的功能

    在J2SE6引入了ArrayDeque类,它继承了Deque(双向队列)接口,使用此类可以自己实现java.util.Stack类的功能,去掉了java.util.Stack的多线程同步的功能. 例如创建一个存放Integer类型的Stack,只要在类中创建一个ArrayDeque类的变量作为属性,之后定义的出栈.入栈,观察栈顶元素的操作就直接操作ArrayDeque的实例变量即可. import java.util.ArrayDeque; import java.util.Deque; pub

  • 深入分析JAVA Vector和Stack的具体用法

    深入分析JAVA Vector和Stack的具体用法

    前面我们已经接触过几种数据结构了,有数组.链表.Hash表.红黑树(二叉查询树),今天再来看另外一种数据结构:栈. 什么是栈呢,我们先看一个例子:栈就相当于一个很窄的木桶,我们往木桶里放东西,往外拿东西时会发现,我们最开始放的东西在最底部,最先拿出来的是刚刚放进去的.所以,栈就是这么一种先进后出(FirstInLastOut,或者叫后进先出)的容器,它只有一个口,在这个口放入元素,也在这个口取出元素.那么我们接下来学习JDK中的栈. 一.Vector&Stack的基本介绍和使用 我们先看下JDK

  • javascript实现Java中的Map对象功能的实例详解

    javascript  自定义对象实现Java中的Map对象功能 Java中有集合,Map等对象存储工具类,这些对象使用简易,但是在JavaScript中,你只能使用Array对象. 这里我创建一个自定义对象,这个对象内包含一个数组来存储数据,数据对象是一个Key,可以实际存储的内容! 这里Key,你要使用String类型,和Java一样,你可以进行一些增加,删除,修改,获得的操作. 使用很简单,我先把工具类给大家看下: /** * @version 1.0 * @author cuisuqia

  • Java模拟QQ桌面截图功能实现方法

    本文实例讲述了Java模拟QQ桌面截图功能实现方法.分享给大家供大家参考.具体如下: QQ的桌面截图功能非常方便,去年曾用Java模拟过一个,现整理出来. 本方法首先需要抓到屏幕的整个图象,将图象显示在一个JFrame中,再将JFrame全屏显示,这样就模拟出了一个桌面,Java也就可以获得鼠标的作用区域从而实现桌面中的小范围截屏. import javax.swing.*; import java.awt.*; import java.awt.event.ActionEvent; import

  • Java编程调用微信分享功能示例

    本文实例讲述了Java编程调用微信分享功能.分享给大家供大家参考,具体如下: 这篇文章介绍如何使用java开发微信分享功能,因为工作,已经开发完成,可使用. 如果想要自定义微信的分享功能,首先在自己的页面内首先使用AJAX.下面我具体举例. 首先是在页面内写入请求后台的AJAX /** * 调用微信分享接口 * */ public void WXConfig(){ String url = getPara("href"); WXConfigController scan = new W

  • java实现的图片裁剪功能示例

    本文实例讲述了java实现的图片裁剪功能.分享给大家供大家参考,具体如下: PicCut.java: package Tsets; import java.awt.Rectangle; import java.awt.image.BufferedImage; import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.util.Iterator; import javax

  • java web中图片验证码功能的简单实现方法

    用户在注册网站信息的时候基本上都要数据验证码验证.那么图片验证码功能该如何实现呢? 大概步骤是: 1.在内存中创建缓存图片 2.设置背景色 3.画边框 4.写字母 5.绘制干扰信息 6.图片输出 废话不多说,直接上代码 package com.lsgjzhuwei.servlet.response; import java.awt.Color; import java.awt.Font; import java.awt.Graphics; import java.awt.image.Buffer

  • java web实现自动登录功能

    本文实例为大家分享了java web实现自动登录功能的具体代码,供大家参考,具体内容如下 主要思路就是:当用户访问网站的首页时,浏览器端会先检擦浏览器中存在的cookie中是否又登录的用户的用户名,如果有,则直接跳转至用户登录好的界面,如果没有,则重定向至登录界面,在服务器端创建该用户登录的cookie,响应时,将创建的cookie返回至浏览器端保存. 一.用户访问首页时检查cookie是否存在. package ahpudong.com; import java.io.IOException;

  • Java案例之随机验证码功能实现实例

    Java案例之随机验证码功能实现实例

    实现的功能比较简单,就是随机产生了四个字符然后输出.效果图如下,下面我会详细说一下实现这个功能用到了那些知识点,并且会把 这些知识点详细的介绍出来.哈哈 ,大神勿喷,对于初学Java的人帮助应该蛮大的.嘿嘿. 先上效果图: 源代码: RandomGen.java(实现产生验证码功能的类) package verificationcode; import java.util.Random; public class RandomGen { //生成四位不重复的验证码 public static S

  • Java Socket实现多线程通信功能示例

    本文实例讲述了Java Socket实现多线程通信功能的方法.分享给大家供大家参考,具体如下: 前面的文章<Java Socket实现单线程通信的方法示例>说到怎样写一个最简单的Java Socket通信,但是文章中的例子有一个问题就是Server只能接受一个Client请求,当第一个Client连接后就占据了这个位置,后续Client不能再继续连接,所以需要做些改动,当Server没接受到一个Client连接请求之后,都把处理流程放到一个独立的线程里去运行,然后等待下一个Client连接请求

随机推荐