线程情况下两个堆栈实现一个队列

前言：这是一个很经典的问题，我之所以要写这个题，是因为我同学面试360时面试过一道题，当时面试官对他说，你们写代码的时候要考虑多线程访问时应该怎么办，所以我就尝试如果是线程访问的情况下两个堆栈实现一个队列应该怎么做？

一、问题描述和算法：

用堆栈实现队列的功能，可以用两个堆栈（stack1和stack2）实现队列的功能，理解一下三句话：

1当有新元素时直接保存到堆栈stack1中

2当要取出一个元素时从stack2中取出

3stack1中的元素导出再存放在stack2中，这样stack2中出去元素就是FIFO了

需要补充的是：当stack2为空时时，需要从stack1中取出全部元素放到stack2中，当stack1和stack2都为空时，队列为空。

二、算法java实现

package util;
import java.util.*;


public class MyQueue<T> {

private Stack<T> stack1;
private Stack<T> stack2;
public MyQueue()
{

    stack1=new Stack<T>();
    stack2=new Stack<T>();
    }
public void appendTail(T item)
{    
    stack1.push(item);
}
public T deleteHead() throws Exception
{
    
    if(stack2.empty())
    {
        while(!stack1.empty())
        {
            T item=stack1.pop();
            stack2.push(item);
        }
    }
    if(stack2.empty())
    {
        throw new Exception("队列空了，需要休息");
    }
    T item=stack2.pop();
    lock_stack2.unlock();
    return item;
    }
}

三、多线程访问的情况

为了简单分析我们假设只有两个线程，一个线程作为生产者，生产元素放入到队列中，另一个线程作为消费者，从队列中取出元素。那么当stack2的元素为空时，要从stack1转移元素，而且是一次性把所有元素都转移走，这个时候如果插入元素时，stack1就会进行push操作，那么就会出现问题，因此stack1本身可以认为是一个临界区（这块如果我理解有错误，请指出），因此可以通过加锁的形式把元素转移变化为一个原子操作。stack1去push元素时，首先要看是否可以在进行元素转移操作。

下面是代码

package util;
import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class MyQueue<T> {
    private Lock lock_stack1;
    private Lock lock_stack2;
private Stack<T> stack1;
private Stack<T> stack2;
public MyQueue()
{
    lock_stack1=new ReentrantLock();
    lock_stack2=new ReentrantLock();
    stack1=new Stack<T>();
    stack2=new Stack<T>();
    }
public void appendTail(T item)
{    lock_stack1.lock();
    stack1.push(item);
    lock_stack1.unlock();
}
public T deleteHead() throws Exception
{
    lock_stack2.lock();
    if(stack2.empty())
    {
        lock_stack1.lock();
        System.out.println("锁了");
        System.out.print(stack1.size());
        while(!stack1.empty())
        {
            T item=stack1.pop();
            stack2.push(item);
        }
        lock_stack1.unlock();
    }
    if(stack2.empty())
    {
        throw new Exception("队列空了，需要休息");
    }
    T item=stack2.pop();
    lock_stack2.unlock();
    return item;
    }
}

四、验证问题

我分别写了两个线程为生产者和消费者两个类，生产者生产的是数字，而且是从0,1,2,3,4，......这样的数字，消费者每次从队列中取出的数字也应该是0,1,2,3,4,....，如果消费者上次取出的数字是j，这次取出的数字是i，如果i<=j就代表出现问题了，因为队列输入的数据是严格递增的，因此输出的数据也是严格递增的。

下面是生产者和消费者的代码。消费者如果发现不满足这一条件时，就会报错，可以尝试注释掉队列中的锁条件，看看是否会报错。当我注释掉相关锁时，显示出报错信息。

package test;

import util.MyQueue;

public class Producer implements Runnable {
private MyQueue qe;
private Producer()
{
    ///把它设为private这么做事有苦衷的
    }
public Producer(MyQueue q)
{
    qe=q;
}
public boolean stopThread;
@Override
public void run() {
    // TODO Auto-generated method stub
    if(qe==null)
    {
        System.out.print("请实例化MyQueue，正确调用Producer的构造参数");
    }
    stopThread=false;
    int i=0;
    java.util.Random random=new java.util.Random(); 
    int sleepTime=0;
    while(!stopThread)
    {    
        qe.appendTail(i++);        
        sleepTime=random.nextInt(100);
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

}

生产者代码

package test;

import util.MyQueue;

public class Consumer extends Thread {
    private MyQueue qe;
    private Consumer()
    {
        
    }
    public Consumer(MyQueue q)
    {
        qe=q;
    }
    public boolean stopThread;
    public void run()
    {
        if(qe==null)
        {
            System.out.print("请实例化MyQueue，正确调用Consumer的构造函数");
        }
        stopThread=false;
        java.util.Random random=new java.util.Random(); 
        int sleepTime=0;
        int j=-1;
        while(!stopThread)
        {    
            try {                
                int  i=(int)qe.deleteHead();
                System.out.println(i);
                if(i<=j)
                {
                    System.out.print("出错了！");
                    System.in.read();
                }
                j=i;
            } catch (Exception e1) {
                // TODO Auto-generated catch block
                e1.printStackTrace();                
            }    
            sleepTime=random.nextInt(500);
            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
    }
}

消费者代码

package test;

import util.MyQueue;
public class Program {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyQueue<Integer> mq=new MyQueue<Integer>();
        Producer myp=new Producer(mq);
        Consumer myc=new Consumer(mq);
        Thread tp=new Thread(myp);
        myc.start();
        tp.start();
        while(true)
        {
            
        }
        
    }

}

main代码

五、还存在的问题

目前只是解决了一个生产者和一个消费者的问题，没有解决多个消费者和多个生产者的问题，因为目前我还没有找到很好的方法验证多个消费者和多个消费者他们并发时应该产生的FIFO序列是什么？如果不是的话那就证明我出错了。如果大家有兴趣的话，希望大家指点一下。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　菜包子

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2013年5月29日0:18:36 于宿舍