java实现二项队列,java两个栈实现队列

发布时间：2022-11-17

本文目录一览：

  1. java怎么实现n个队列
  2. 在JAVA中怎么实现消息队列
  3. 怎样用java代码实现一个队列
  4. 用java编一个队列
  5. 关于java合并两个队列
  6. java 队列

java怎么实现n个队列

public class QueueE {
    private Object[] data = null;
    private int maxSize; // 队列容量
    private int front; // 队列头，允许删除
    private int rear; // 队列尾，允许插入
    // 构造函数
    public Queue() {
        this(10);
    }
    public Queue(int initialSize) {
        if (initialSize >= 0) {
            this.maxSize = initialSize;
            data = new Object[initialSize];
            front = rear = 0;
        } else {
            throw new RuntimeException("初始化大小不能小于0：" + initialSize);
        }
    }
    // 判空
    public boolean empty() {
        return rear == front ? true : false;
    }
    // 插入
    public boolean add(E e) {
        if (rear == maxSize) {
            throw new RuntimeException("队列已满，无法插入新的元素！");
        } else {
            data[rear++] = e;
            return true;
        }
    }
    // 返回队首元素，但不删除
    public E peek() {
        if (empty()) {
            throw new RuntimeException("空队列异常！");
        } else {
            return (E) data[front];
        }
    }
    // 出队
    public E poll() {
        if (empty()) {
            throw new RuntimeException("空队列异常！");
        } else {
            E value = (E) data[front]; // 保留队列的front端的元素的值
            data[front++] = null; // 释放队列的front端的元素
            return value;
        }
    }
    // 队列长度
    public int length() {
        return rear - front;
    }
}

在JAVA中怎么实现消息队列

import java.util.*;
public class MsgQueue {
    private Vector queue = null;
    public MsgQueue() {
        queue = new Vector();
    }
    public synchronized void send(Object o) {
        queue.addElement(o);
    }
    public synchronized Object recv() {
        if (queue.size() == 0)
            return null;
        Object o = queue.firstElement();
        queue.removeElementAt(0); // or queue[0] = null 也可以工作
        return o;
    }
}

因为Java中是通过对象锁定的，所以添加 synchronized 就可以用于线程同步锁定对象。 可以作为多线程处理多任务的存放任务队列。它的客户端包括封装好的任务类以及线程类。

Java的多线程-线程间的通信

  1. 线程的几种状态 线程有四种状态，任何一个线程肯定处于这四种状态中的一种：
  1. 产生（New）：线程对象已经产生，但尚未被启动，所以无法执行。例如通过 new 产生了一个线程对象后，没有调用 start() 函数之前。
  2. 可执行（Runnable）：每个支持多线程的系统都有一个排程器，排程器会从线程池中选择一个线程并启动它。当一个线程处于可执行状态时，表示它可能正处于线程池中等待排程器启动它；也可能它已正在执行。例如执行了一个线程对象的 start() 方法后，线程就处于可执行状态，但显而易见的是此时线程不一定正在执行中。
  3. 死亡（Dead）：当一个线程正常结束，它便处于死亡状态。例如一个线程的 run() 函数执行完毕后线程就进入死亡状态。
  4. 停滞（Blocked）：当一个线程处于停滞状态时，系统排程器就会忽略它，不对它进行排程。当处于停滞状态的线程重新回到可执行状态时，它有可能重新执行。例如通过对一个线程调用 wait() 函数后，线程就进入停滞状态，只有当两次对该线程调用 notify 或 notifyAll 后它才能两次回到可执行状态。

class Thread 下的常用函数

1. suspend()、resume()

  1. 通过 suspend() 函数，可使线程进入停滞状态。通过 suspend() 使线程进入停滞状态后，除非收到 resume() 消息，否则该线程不会变回可执行状态。
  2. 当调用 suspend() 函数后，线程不会释放它的“锁标志”。

2. sleep()

  1. sleep() 函数有一个参数，通过参数可使线程在指定的时间内进入停滞状态，当指定的时间过后，线程则自动进入可执行状态。
  2. 当调用 sleep() 函数后，线程不会释放它的“锁标志”。

3. yield()

  1. 通过 yield() 函数，可使线程进入可执行状态，排程器从可执行状态的线程中重新进行排程。所以调用了 yield() 的函数也有可能马上被执行。
  2. 当调用 yield() 函数后，线程不会释放它的“锁标志”。

4. sleep() 和 yield() 的区别

  1. sleep() 使当前线程进入停滞状态，所以执行 sleep() 的线程在指定的时间内肯定不会执行；yield() 只是使当前线程重新回到可执行状态，所以执行 yield() 的线程有可能在进入到可执行状态后马上又被执行。
  2. sleep() 可使优先级低的线程得到执行的机会，当然也可以让同优先级和高优先级的线程有执行的机会；yield() 只能使同优先级的线程有执行的机会。

5. join()

使调用 join() 的线程执行完毕后才能执行其它线程，在一定意义上，它可以实现同步的功能。

class Object 下常用的线程函数

wait()、notify() 和 notifyAll() 这三个函数由 java.lang.Object 类提供，用于协调多个线程对共享数据的存取。

1. wait()、notify() 和 notifyAll()

  1. wait() 函数有两种形式：第一种形式接受一个毫秒值，用于在指定时间长度内暂停线程，使线程进入停滞状态。第二种形式为不带参数，代表 wait() 在 notify() 或 notifyAll() 之前会持续停滞。
  2. 当对一个对象执行 notify() 时，会从线程等待池中移走该任意一个线程，并把它放到锁标志等待池中；当对一个对象执行 notifyAll() 时，会从线程等待池中移走所有该对象的所有线程，并把它们放到锁标志等待池中。
  3. 当调用 wait() 后，线程会释放掉它所占有的“锁标志”，从而使线程所在对象中的其它 synchronized 数据可被别的线程使用。

2. wait()、notify() 和 synchronized

wait() 和 notify() 因为会对对象的“锁标志”进行操作，所以它们必须在 synchronized 函数或 synchronized 块中进行调用。如果在非 synchronized 函数或非 synchronized 块中进行调用，虽然能编译通过，但在运行时会发生 IllegalMonitorStateException 的异常。

wait()、notify()、notifyAll() 和 suspend()、resume()、sleep() 的讨论

1. 这两组函数的区别

  1. wait() 使当前线程进入停滞状态时，还会释放当前线程所占有的“锁标志”，从而使线程对象中的 synchronized 资源可被对象中别的线程使用；而 suspend() 和 sleep() 使当前线程进入停滞状态时不会释放当前线程所占有的“锁标志”。
  2. 前一组函数必须在 synchronized 函数或 synchronized 块中调用，否则在运行时会产生错误；而后一组函数可以在非 synchronized 函数和 synchronized 块中调用。

2. 这两组函数的取舍

Java 2 已不建议使用后一组函数。因为在调用 suspend() 时不会释放当前线程所取得的“锁标志”，这样很容易造成“死锁”。

怎样用java代码实现一个队列

class Stack<T> {
    private Vector<T> v;
    public Stack() {
        v = new Vector<T>();
    }
    public T pop() {
        if (v.size() == 0) return null;
        return v.get(v.size() - 1);
    }
    public void push(T t) {
        v.add(t);
    }
    public boolean isEmpty() {
        return v.size() == 0;
    }
}
class Queue<T> {
    private Vector<T> v;
    public Queue() {
        v = new Vector<T>();
    }
    // 入队列
    public void enqueue(T t) {
        v.add(t);
    }
    // 出队列
    public T dequeue() {
        if (v.size() == 0) return null;
        return v.get(0);
    }
    public boolean isEmpty() {
        return v.size() == 0;
    }
}

用java编一个队列

自己写了个简单的实现：

class Queue<E> {
    private Object[] integerQueue; // 用来当队列
    public int tail; // 队尾
    public int size; // 队的长度，也可以设置一个默认值，溢出时从新申请
    public Queue(int size) {
        integerQueue = new Object[size];
        this.size = size;
        tail = -1;
    }
    /**
     * 将元素插入队列
     * @return 如果该元素已添加到此队列，则返回 true；否则返回 false
     */
    public boolean offer(E e) {
        if (tail < size - 1) {
            tail++;
            this.integerQueue[tail] = e;
            return true;
        } else {
            return false;
        }
    }
    /**
     * 获取并移除此队列的头，如果此队列为空，则返回 null。
     */
    public E poll() {
        Object tmp;
        if (tail >= 0) {
            tmp = this.integerQueue[tail];
            tail--;
            return (E) tmp;
        } else {
            return null;
        }
    }
}

关于java合并两个队列

新建一个队列依次往里放就是了。就这样：

ArrayList a; // 你已经有的a
ArrayList b; // 你已经有的b
ArrayList c = new ArrayList();
int e = Math.max(a.size(), b.size());
int q = Math.min(a.size(), b.size());
for (int i = 0; i < e; i++) {
    if (i < q) {
        c.add(a.get(i));
        c.add(b.get(i));
    }
    if (i == q) {
        c.add(b.get(i));
    }
}

写的这样也差不多了吧。

java 队列

通过 LinkedList 实现队列

package 队列和堆栈;
import java.util.*;
public class LinkedListQueueTest {
    // 字段
    private LinkedList list;
    // 无参数构造
    public LinkedListQueueTest() {
        list = new LinkedList();
    }
    // 队列元素的个数
    public int size() {
        return list.size();
    }
    // 进入队列
    public void enqueue(Object obj) {
        list.addLast(obj);
    }
    // 对头出来
    public Object dequeue() {
        return list.removeFirst();
    }
    // 浏览对头元素
    public Object front() {
        return list.peekFirst();
    }
    // 判断队列是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        LinkedListQueueTest llq = new LinkedListQueueTest();
        System.out.println(llq.isEmpty());
        llq.enqueue("147");
        llq.enqueue("258");
        llq.enqueue("369");
        System.out.println(llq.size());
        System.out.println("移除队列头元素：" + llq.dequeue());
        System.out.println(llq.size());
        llq.enqueue("abc");
        llq.enqueue("def");
        System.out.println(llq.size());
        System.out.println("查看队列的头元素：" + llq.front());
        System.out.println(llq.size());
        System.out.println(llq.isEmpty());
    }
}

通过数组实现

package 队列和堆栈;
import java.util.NoSuchElementException;
// 通过数组来实现队列
public class ArrayQueue {
    // 字段
    public static Object[] data;
    // 队列的元素个数
    protected int size;
    // 队列头
    protected int head;
    // 队列尾
    public static int tail;
    // 无参数构造函数
    public ArrayQueue() {
        final int INITIAL_LENGTH = 3;
        data = new Object[INITIAL_LENGTH];
        size = 0;
        head = 0;
        tail = -1;
    }
    // 队列元素个数方法
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    // 得到队列头元素
    public Object front() {
        if (size == 0)
            throw new NoSuchElementException();
        return data[head];
    }
    // 进入队列enqueue()方法
    public void enqueue(Object obj) {
        // 此时队列已经满
        if (size == data.length) {
            Object[] oldData = data;
            data = new Object[data.length * 2];
            System.arraycopy(oldData, head, data, 0, oldData.length - head);
            if (head > 0)
                System.arraycopy(oldData, 0, data, head + 1, tail + 1);
            head = 0;
            tail = oldData.length - 1;
        }
        tail = (tail + 1) % data.length;
        size++;
        data[tail] = obj;
    }
    // 队列的元素出队
    public Object dequeue() {
        if (size == 0)
            throw new NoSuchElementException();
        Object ele = data[head];
        // 循环队列
        head = (head + 1) % data.length;
        size--;
        return ele;
    }
    @Override
    public String toString() {
        return super.toString();
    }
}

通过向量实现

// 通过向量实现栈
package 队列和堆栈;
import java.util.*;
public class VectorStackTest {
    // 字段
    Vector v;
    // 构造函数
    public VectorStackTest() {
        v = new Vector();
    }
    // 元素的个数
    public int size() {
        return v.size();
    }
    // 是否为空
    public boolean isEmpty() {
        return size() == 0;
    }
    // 进栈
    public Object Push(Object obj) {
        v.addElement(obj);
        return obj;
    }
    // 出栈方法
    public Object Pop() {
        int len = size();
        Object obj = Peek();
        v.removeElementAt(len - 1);
        return obj;
    }
    // 查看栈顶元素
    public Object Peek() {
        int len = size();
        if (len == 0)
            throw new EmptyStackException();
        return v.elementAt(len - 1);
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        VectorStackTest vst = new VectorStackTest();
        System.out.println("大小：" + vst.size());
        vst.Push("123");
        vst.Push("456");
        vst.Push("789");
        vst.Push("abc");
        System.out.println("大小：" + vst.size());
        System.out.println("栈顶：" + vst.Peek());
        System.out.println("出栈：" + vst.Pop());
        vst.Push("def");
        vst.Push("147");
        System.out.println("大小：" + vst.size());
        System.out.println("栈顶：" + vst.Peek());
        System.out.println("出栈：" + vst.Pop());
        System.out.println(vst.Peek());
        vst.Push("def");
        vst.Push("147");
        System.out.println(vst.Pop());
        System.out.println(vst.Pop());
        System.out.println(vst.Peek());
        System.out.println(vst.Pop());
        System.out.println(vst.Pop());
        vst.Push("1aadf");
        vst.Push("2dafad");
        vst.Push("123789");
        System.out.println(vst.Pop());
        System.out.println(vst.Peek());
        System.out.println(vst.Pop());
        System.out.println(vst.Peek());
        System.out.println("------------------end------------");
        VectorStackTest llst = new VectorStackTest();
        llst.Push("123");
        llst.Push("456");
        System.out.println("栈顶：" + llst.Peek());
        System.out.println("出栈：" + llst.Pop());
        System.out.println(llst.Peek());
        llst.Push("789");
        llst.Push("abc");
        System.out.println("栈顶：" + llst.Peek());
        System.out.println("出栈：" + llst.Pop());
        System.out.println(llst.size());
        System.out.println("栈顶：" + llst.Peek());
    }
}

推荐：都看 API 文档。有疑问可以问我，QQ：285479197

推荐文章