队列的实现(java)

队列遵循先进先出(FIFO)原则,队列可以用数组或链表实现，实现过程如下：

数组实现：

package com.tongtong;

import java.util.LinkedList;

/**
 * 数组实现队列(实现了多线程安全)
 */
public class MyQueue2<E> {

    private LinkedList<E> list = new LinkedList<E>();
    private int size = 0;
    public synchronized void put(E e){
        list.addLast(e);
        size++;
    }

    public synchronized E pop(){
        size--;
        return list.removeFirst();
    }

    public synchronized boolean empty(){
        return size == 0;
    }

    public synchronized int size(){
        return size;
    }
}

链表实现：

package com.tongtong;

/**
 * 用单链表实现队列
 */

/**
 * 定义节点
 * @param <E>
 */
public class Node<E> {

    Node<E> next = null;
    E data;
    public Node(E data){this.data = data;}
}


public class MyQueue<E> {

    private Node<E> head = null;
    private Node<E> tail = null;
    public boolean isEmpty(){
        return head == tail;
    }

    public void put(E data){
        Node<E> newNode = new Node<E>(data);
        if(head == null && tail == null){
            head = tail = newNode;
        }else{
            tail.next = newNode;
            tail = newNode;
        }
    }

    public E pop(){
        if(this.isEmpty()){
            return null;
        }
        E data = head.data;
        head = head.next;
        return data;
    }

    public int size(){
        Node<E> tmp = head;
        int n = 0;
        while(tmp != null){
            n++;
            tmp = tmp.next;
        }

        return n;
    }

    public static void main(String[] args) {
        MyQueue<Integer> q = new MyQueue<Integer>();
        q.put(11);
        q.put(12);
        q.put(13);
        q.put(14);
        q.put(15);

        System.out.println(q.pop());
        System.out.println(q.pop());
        System.out.println(q.pop());
    }
}

提出问题：

如何用两个栈模拟队列操作：

思路：

定义两个栈A和B：

1.若栈B不为空，则直接弹出栈B的数据；

2.若栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。

实现：

package com.tongtong;

import java.util.Stack;

/**
 * 用两个栈模拟队列操作
 */
public class MyQueueTest<E> {

    private Stack<E> s1 = new Stack<E>();
    private Stack<E> s2 = new Stack<E>();
    public synchronized void put(E e){
        s1.push(e);
    }

    public synchronized E pop(){
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public synchronized boolean empty(){
        return s1.isEmpty()&&s2.isEmpty();
    }

    public static void main(String[] args) {
        MyQueueTest<Integer> q = new MyQueueTest<Integer>();
        q.put(1);
        q.put(2);
        System.out.println("队列首元素：" + q.pop());
        System.out.println("队列首元素：" + q.pop());
    }
}

小蜜蜂

队列的实现(java)