Java模拟栈和队列数据结构的基本示例讲解

栈和队列:
一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建;
访问受限,在特定时刻,只有一个数据可被读取或删除;
是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组、链表来实现栈。

模拟栈结构
同时,只允许一个数据被访问,后进先出
对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快
例,使用数组作为栈的存储结构

public class StackS<T> {
  private int max;
  private T[] ary;
  private int top;  //指针,指向栈顶元素的下标 

  public StackS(int size) {
    this.max = size;
    ary = (T[]) new Object[max];
    top = -1;
  } 

  // 入栈
  public void push(T data) {
    if (!isFull())
      ary[++top] = data;
  } 

  // 出栈
  public T pop() {
    if (isEmpty()) {
      return null;
    }
    return ary[top--];
  } 

  // 查看栈顶
  public T peek() {
    return ary[top];
  } 

  //栈是否为空
  public boolean isEmpty() {
    return top == -1;
  } 

  //栈是否满
  public boolean isFull() {
    return top == max - 1;
  } 

  //size
  public int size() {
    return top + 1;
  } 

  public static void main(String[] args) {
    StackS<Integer> stack = new StackS<Integer>(3);
    for (int i = 0; i < 5; i++) {
      stack.push(i);
      System.out.println("size:" + stack.size());
    }
    for (int i = 0; i < 5; i++) {
      Integer peek = stack.peek();
      System.out.println("peek:" + peek);
      System.out.println("size:" + stack.size());
    }
    for (int i = 0; i < 5; i++) {
      Integer pop = stack.pop();
      System.out.println("pop:" + pop);
      System.out.println("size:" + stack.size());
    } 

    System.out.println("----"); 

    for (int i = 5; i > 0; i--) {
      stack.push(i);
      System.out.println("size:" + stack.size());
    }
    for (int i = 5; i > 0; i--) {
      Integer peek = stack.peek();
      System.out.println("peek:" + peek);
      System.out.println("size:" + stack.size());
    }
    for (int i = 5; i > 0; i--) {
      Integer pop = stack.pop();
      System.out.println("pop:" + pop);
      System.out.println("size:" + stack.size());
    }
  }
}

上面的例子,有一个maxSize的规定,因为数组是要规定大小的,若想无限制,可以使用其他结构来做存储,当然也可以new一个新的长度的数组。
例,使用LinkedList存储来实现栈

public class StackSS<T> {
  private LinkedList<T> datas; 

  public StackSS() {
    datas = new LinkedList<T>();
  } 

  // 入栈
  public void push(T data) {
    datas.addLast(data);
  } 

  // 出栈
  public T pop() {
    return datas.removeLast();
  } 

  // 查看栈顶
  public T peek() {
    return datas.getLast();
  } 

  //栈是否为空
  public boolean isEmpty() {
    return datas.isEmpty();
  } 

  //size
  public int size() {
    return datas.size();
  } 

  public static void main(String[] args) {
    StackS<Integer> stack = new StackS<Integer>(3);
    for (int i = 0; i < 5; i++) {
      stack.push(i);
      System.out.println("size:" + stack.size());
    }
    for (int i = 0; i < 5; i++) {
      Integer peek = stack.peek();
      System.out.println("peek:" + peek);
      System.out.println("size:" + stack.size());
    }
    for (int i = 0; i < 5; i++) {
      Integer pop = stack.pop();
      System.out.println("pop:" + pop);
      System.out.println("size:" + stack.size());
    } 

    System.out.println("----");
    for (int i = 5; i > 0; i--) {
      stack.push(i);
      System.out.println("size:" + stack.size());
    }
    for (int i = 5; i > 0; i--) {
      Integer peek = stack.peek();
      System.out.println("peek:" + peek);
      System.out.println("size:" + stack.size());
    }
    for (int i = 5; i > 0; i--) {
      Integer pop = stack.pop();
      System.out.println("pop:" + pop);
      System.out.println("size:" + stack.size());
    }
  }
}

例,单词逆序,使用Statck结构

public class WordReverse { 

  public static void main(String[] args) {
    reverse("株式会社");
  } 

  static void reverse(String word) {
    if (word == null) return;
    StackSS<Character> stack = new StackSS<Character>();
    char[] charArray = word.toCharArray();
    int len = charArray.length;
    for (int i = 0; i <len; i++ ) {
      stack.push(charArray[i]);
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
      sb.append(stack.pop());
    }
    System.out.println("反转后:" + sb.toString());
  }
}

打印:

反转后:社会式株

模拟队列(一般队列、双端队列、优先级队列)
队列:
先进先出,处理类似排队的问题,先排的,先处理,后排的等前面的处理完了,再处理
对于插入和移除操作的时间复杂度都为O(1),从后面插入,从前面移除
双端队列:
即在队列两端都可以insert和remove:insertLeft、insertRight,removeLeft、removeRight
含有栈和队列的功能,如去掉insertLeft、removeLeft,那就跟栈一样了;如去掉insertLeft、removeRight,那就跟队列一样了
一般使用频率较低,时间复杂度 O(1)
优先级队列:
内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置,时间复杂度O(N), 删除O(1)

/*
 * 队列  先进先出,一个指针指示插入的位置,一个指针指示取出数据项的位置
 */
public class QueueQ<T> {
  private int max;
  private T[] ary;
  private int front; //队头指针 指示取出数据项的位置
  private int rear; //队尾指针 指示插入的位置
  private int nItems; //实际数据项个数 

  public QueueQ(int size) {
    this.max = size;
    ary = (T[]) new Object[max];
    front = 0;
    rear = -1;
    nItems = 0;
  }
  //插入队尾
  public void insert(T t) {
    if (rear == max - 1) {//已到实际队尾,从头开始
      rear = -1;
    }
    ary[++rear] = t;
    nItems++;
  }
  //移除队头
  public T remove() {
    T temp = ary[front++];
    if (front == max) {//列队到尾了,从头开始
      front = 0;
    }
    nItems--;
    return temp;
  }
  //查看队头
  public T peek() {
    return ary[front];
  } 

  public boolean isEmpty() {
    return nItems == 0;
  } 

  public boolean isFull() {
    return nItems == max;
  } 

  public int size() {
    return nItems;
  } 

  public static void main(String[] args) {
    QueueQ<Integer> queue = new QueueQ<Integer>(3);
    for (int i = 0; i < 5; i++) {
      queue.insert(i);
      System.out.println("size:" + queue.size());
    }
    for (int i = 0; i < 5; i++) {
      Integer peek = queue.peek();
      System.out.println("peek:" + peek);
      System.out.println("size:" + queue.size());
    }
    for (int i = 0; i < 5; i++) {
      Integer remove = queue.remove();
      System.out.println("remove:" + remove);
      System.out.println("size:" + queue.size());
    } 

    System.out.println("----"); 

    for (int i = 5; i > 0; i--) {
      queue.insert(i);
      System.out.println("size:" + queue.size());
    }
    for (int i = 5; i > 0; i--) {
      Integer peek = queue.peek();
      System.out.println("peek:" + peek);
      System.out.println("size:" + queue.size());
    }
    for (int i = 5; i > 0; i--) {
      Integer remove = queue.remove();
      System.out.println("remove:" + remove);
      System.out.println("size:" + queue.size());
    }
  } 

}
/*
 * 双端队列<span style="white-space:pre"> </span>两端插入、删除
 */
public class QueueQT<T> {
  private LinkedList<T> list; 

  public QueueQT() {
    list = new LinkedList<T>();
  } 

  // 插入队头
  public void insertLeft(T t) {
    list.addFirst(t);
  } 

  // 插入队尾
  public void insertRight(T t) {
    list.addLast(t);
  } 

  // 移除队头
  public T removeLeft() {
    return list.removeFirst();
  } 

  // 移除队尾
  public T removeRight() {
    return list.removeLast();
  } 

  // 查看队头
  public T peekLeft() {
    return list.getFirst();
  } 

  // 查看队尾
  public T peekRight() {
    return list.getLast();
  } 

  public boolean isEmpty() {
    return list.isEmpty();
  } 

  public int size() {
    return list.size();
  } 

}
/*
 * 优先级队列  队列中按优先级排序,是一个有序的队列
 */
public class QueueQP {
  private int max;
  private int[] ary;
  private int nItems; //实际数据项个数 

  public QueueQP(int size) {
    this.max = size;
    ary = new int[max];
    nItems = 0;
  }
  //插入队尾
  public void insert(int t) {
    int j;
    if (nItems == 0) {
      ary[nItems++] = t;
    } else {
      for (j = nItems - 1; j >= 0; j--) {
        if (t > ary[j]) {
          ary[j + 1] = ary[j]; //前一个赋给后一个 小的在后    相当于用了插入排序,给定序列本来就是有序的,所以效率O(N)
        } else {
          break;
        }
      }
      ary[j + 1] = t;
      nItems++;
    }
    System.out.println(Arrays.toString(ary));
  }
  //移除队头
  public int remove() {
    return ary[--nItems]; //移除优先级小的
  }
  //查看队尾 优先级最低的
  public int peekMin() {
    return ary[nItems - 1];
  } 

  public boolean isEmpty() {
    return nItems == 0;
  } 

  public boolean isFull() {
    return nItems == max;
  } 

  public int size() {
    return nItems;
  } 

  public static void main(String[] args) {
    QueueQP queue = new QueueQP(3);
    queue.insert(1);
    queue.insert(2);
    queue.insert(3);
    int remove = queue.remove();
    System.out.println("remove:" + remove); 

  } 

}
时间: 2016-04-10

java 数据结构之栈与队列

java 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e

Java数据结构之循环队列简单定义与用法示例

本文实例讲述了Java数据结构之循环队列简单定义与用法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 与普通队列的区别在于循环队列添加数据时,如果其有效数据end == maxSize - 1(最大空间)的话,end指针又移动到-1的位置 删除数据时,如果head== maxSize时 head指针移动到0的位置 2.示例图: 二.实现代码: package com.java.queue; /** * @描述 对列 * @项目名称 Java_DataStruct * @包名 com.

Java数据结构之队列的简单定义与使用方法

本文实例讲述了Java数据结构之队列的简单定义与使用方法.分享给大家供大家参考,具体如下: 一.概述: 1.说明: 队列的原则时先进先出,就像生活中排队取票一样,谁排在前面谁先得到 2.有五个属性: 1)数组元素 2)最大空间 3)长度 4)队头 5)队尾 3.示例图: 二.代码实现 /** * @描述 对列 * @项目名称 Java_DataStruct * @包名 com.java.stack * @类名 Queue * @author chenlin * @version 1.0 * @S

java数据结构与算法之双向循环队列的数组实现方法

本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

Java数据结构之有效队列定义与用法示例

本文实例讲述了Java数据结构之有效队列定义与用法.分享给大家供大家参考,具体如下: /** * @描述 有序对列 * 从任何位置插入数据都是有序的 * @项目名称 Java_DataStruct * @包名 com.java.stack * @类名 Queue * @author chenlin */ public class SequeQueue { private long[] arr; private int maxSize;// 最大空间 private int len;// 有效长度

Java数据结构之队列(动力节点Java学院整理)

队列的定义: 队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表. (1)允许删除的一端称为队头(Front). (2)允许插入的一端称为队尾(Rear). (3)当队列中没有元素时称为空队列. (4)队列亦称作先进先出(First In First Out)的线性表,简称为FIFO表. 队列的修改是依先进先出的原则进行的.新来的成员总是加入队尾,每次离开的成员总是队列头上的(不允许中途离队). 队列的存储结构及实现 队列的顺序存储结构 (1) 顺序队列的定义: 队列

java 数据结构中栈和队列的实例详解

java 数据结构中栈和队列的实例详解 栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据.与线性表相比,它们的插入和删除操作收到更多的约束和限定,又被称为限定性的线性表结构.栈是先进后出FILO,队列是先进先出FIFO,但是有的数据结构按照一定的条件排队数据的队列,这时候的队列属于特殊队列,不一定按照上面的原则. 实现栈:采用数组和链表两种方法来实现栈 链表方法: package com.cl.content01; /* * 使用链表来实现栈 */ public cl

Java数组模拟优先级队列数据结构的实例

优先级队列 如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了.这样,我们就引入了优先级队列 这种数据结构. 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 .对于优先权相同的元素,可按先进先出次序处理或按任意优先

基于Java数组实现循环队列的两种方法小结

用java实现循环队列的方法: 1.添加一个属性size用来记录眼下的元素个数. 目的是当head=rear的时候.通过size=0还是size=数组长度.来区分队列为空,或者队列已满. 2.数组中仅仅存储数组大小-1个元素,保证rear转一圈之后不会和head相等.也就是队列满的时候.rear+1=head,中间刚好空一个元素. 当rear=head的时候.一定是队列空了. 队列(Queue)两端同意操作的类型不一样: 能够进行删除的一端称为队头,这样的操作也叫出队dequeue: 能够进行插

Java数组集合的深度复制代码实例

这篇文章主要介绍了Java数组集合的深度复制代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java当我们想要对一个数组进行一些操作,同时又不希望对原来的数组数据有影响的时候,使用引用是不能满足我们的需求的, 这时候我们可以使用System.arraycopy()方法实现,对用这两种复制方式,我们习惯称前者为浅复制,后者为深复制.深复制的 实现方法如下: public static void arraycopyTest() { int[

解析Java中PriorityQueue优先级队列结构的源码及用法

一.PriorityQueue的数据结构 JDK7中PriorityQueue(优先级队列)的数据结构是二叉堆.准确的说是一个最小堆. 二叉堆是一个特殊的堆, 它近似完全二叉树.二叉堆满足特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆. 当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆. 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆. 下图是一个最大堆 priorityQueue队头就是给定顺序的最小元素. prio

Java数组传递及可变参数操作实例详解

本文实例讲述了Java数组传递及可变参数操作.分享给大家供大家参考,具体如下: 方法可以操作传递和返回基本数据类型,但是方法中也可用来传递和返回数组.如果要向方法中传递一个数组,则方法的接收参数处必须是符合其类型的数组.而且数组属于引用数据类型,所以在把数组传递进方法之后,如果方法对数组本身做了任何修改,修改结果都是会保存下来的. 向方法中传递数组 在java中,所有对象都是通过引用进行操作的.而数组也是一种对象,当把数组作为参数传递给方法时,传递的实际上就是数组对象的引用.在方法中对数组的所有

关于Java数组查询的相关问题及实例 原创

在做数组查询的过程中,我们有时候会遇到一些问题,下面就跟随作者一起解答这些问题. Arrays 类的 binarySearch() 方法,可使用二分搜索法来搜寻指定数组,以获得指定对象.该方法返回要搜索元素的索引值. binarySearch()方法提供了多种重载形式,用于满足各种类型数组的查找需要. binarySearch()方法有两种参数类型. (1)binarySearch(Object[] a.Object key) 其中a 代表要所搜的数组,key 表示要搜索的值.如果key 包含在

Java 数组获取最大和最小值的实例实现

以下实例演示了如何通过 Collections 类的 Collections.max() 和 Collections.min() 方法来查找数组中的最大和最小值: Main.java 文件: import java.util.Arrays; import java.util.Collections; public class Main { public static void main(String[] args) { Integer[] numbers = { 8, 2, 7, 1, 4, 9

Java数组队列概念与用法实例分析

本文实例讲述了Java数组队列概念与用法.分享给大家供大家参考,具体如下: 一.队列的概念 (1)队列也是一种线性结构 (2)相比数组,队列对应的操作是数组的子集 (3)只允许在一端插入数据操作,在另一端进行删除数据操作,进行插入操作的一端称为队尾(入队列),进行删除操作的一端称为队头(出队列) (4)队列是一种先进先出的数据结构(FIFO) 此处我们先来学习一下顺序队列 ,顺序队列 就是用数组实现:比如有一个n个元素的队列,数组下标0的一端是队头,入队操作就是通过数组下标一个个顺序追加,不需要

Java用数组实现循环队列的示例

复习了下数据结构,用Java的数组实现一下循环队列. 队列的类 //循环队列 class CirQueue{ private int QueueSize; private int front; private int rear; private int[] queueList ; public CirQueue(int QueueSize){ this.QueueSize = QueueSize; queueList = new int[QueueSize]; front = 0; rear =