数据结构 - 两个栈实现一个队列

Love The Way You Lie 2022-12-26 04:50 153阅读 0赞

# 实现原理 #

栈的特性是先进后出，队列的特性是先进先出。那么，我们使用两个栈，对同一个元素进行先进后出两次栈就形成了先进先出的顺序。

**即一个元素需要入栈两次，才能被取出来。**

我们将put，get定义为存放元素，与取元素。

使用命名为in，out的栈，in代表往队列里面put元素第一次入栈是进入in，out代表get元素是从out这个栈里取。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]  
第一次，get时out为空，需要从in中取元素，以形成正序取。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]

其内部实现细节如下：

put(){ 
    	in.put;
    }
    get(){ 
    //如果out为空，则从in里面取出所有第一次入栈元素放入out栈，形成最初的进栈顺序，这样底层的就在最上面。
    in.all.get -> out
    //然后 从out get
    }

# 实现代码 #

public class TwoStackQueue<T> { 
        private Stack<T> in = new Stack<T>();
        private Stack<T> out = new Stack<T>();
    
    
        public void put(T t) { 
                in.push(t)；
        }
    
        public T get() { 
    
              if (out.isEmpty()) { 
                    if (in.isEmpty()) return null;
                    while (!in.isEmpty()) { 
                            out.push(in.pop());
                    }
                    return out.pop();
                } else { 
                    return out.pop();
                }
       
        }
    
        public boolean isEmpty() { 
            return (in.isEmpty() && out.isEmpty()) ? true : false;
        }
    
        public int size() { 
            return out.size() + in.size();
        }
    }

# 存在问题 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 3]  
若a还没取，c已进栈时，如何控制？很明显这是一个线程安全问题。

在out取in中的元素的时候我们需要对 in加锁，阻止他存放新元素进去。  
而对于out，我们是在out为空的时候才取in中元素所以一般不会出现线程安全问题。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 4]  
以下是简易版本实现：

public class TwoStackQueue<T> { 
        private Stack<T> in = new Stack<T>();
        private Stack<T> out = new Stack<T>();
        private ReentrantLock lock_in = new ReentrantLock();
    
        public static void main(String[] args) { 
            TwoStackQueue<String> queue = new TwoStackQueue<>();
            ExecutorService threadPool = Executors.newFixedThreadPool(5);
            for (int i = 0; i < 10; i++) { 
                final int _i = i;
                threadPool.execute(() -> { 
                    queue.put(Thread.currentThread().getName() + " " + _i);
                    System.out.println(Thread.currentThread().getName() + "取到了 " + queue.get());
                });
            }
        }
    
        public void put(T t) { 
            lock_in.lock();
            try { 
                in.push(t);
            } finally { 
                lock_in.unlock();
            }
    
        }
    
        public T get() { 
    
            try { 
                //只有当out为空的时候才会去in中取元素，这个时候可能产生线程安全问题
                if (out.isEmpty()) { 
                    if (in.isEmpty()) return null;
                    lock_in.lock();
                try { 
                    while (!in.isEmpty()) { 
                        //在取in中元素的时候锁住in 
                           out.push(in.pop());                  
                  	    }
                    } finally { 
                           lock_in.unlock();
                    }
                    
                    return out.pop();
                    
                } else { 
                    return out.pop();
                }
            } finally { 
    
            }
    
    
        }
    
        public boolean isEmpty() { 
            return (in.isEmpty() && out.isEmpty()) ? true : false;
        }
    
        public int size() { 
            return out.size() + in.size();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]: /images/20221120/3fb07d8b650b49cebaf80c363628f51a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201203135631188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201203135756450.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201203135916213.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201203140227543.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70