文档章节

用两个栈实现队列&&用两个队列实现一个栈

datacube
 datacube
发布于 2016/06/22 19:12
字数 467
阅读 16
收藏 0
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;  
  
    /* 
     * Q 57 用两个栈实现队列 
     */

public class QueueImplementByTwoStacks {

    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    QueueImplementByTwoStacks(){
        stack1=new Stack<Integer>();
        stack2=new Stack<Integer>();
    }

    public Integer poll(){
        Integer re=null;
        if(!stack2.empty()){//如果stack2不为空则弹出栈顶元素
            re=stack2.pop();
        }else{//如果stack2为空,将stack1中的元素弹出,依次压栈到stack2中,那么stack1栈底的元素就会成为stack2栈顶的元素,从而达到stack1先进先出的队列顺序
            while(!stack1.empty()){
                re=stack1.pop();
                stack2.push(re);
            }
            if(!stack2.empty()){
                re=stack2.pop();
            }
        }
        return re;
    }
    public Integer offer(int o){//每次只从stack1压栈
        stack1.push(o);
        return o;
    }

    public static void main(String[] args) {
        QueueImplementByTwoStacks queue=new QueueImplementByTwoStacks();
        List<Integer> re=new ArrayList<Integer>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        re.add(queue.poll());
        queue.offer(4);
        re.add(queue.poll());
        queue.offer(5);
        re.add(queue.poll());
        re.add(queue.poll());
        re.add(queue.poll());
        System.out.println(re.toString());
    }

}  
import java.util.LinkedList;

/* 
 * Q 57 用两个队列实现一个栈 
 */
public class StackImplementByTwoQueues {

    //use 'queue1' and 'queue2' as a queue.That means only use the method 'addLast' and 'removeFirst'.  
    private LinkedList<Integer> queue1;
    private LinkedList<Integer> queue2;

    StackImplementByTwoQueues(){
        queue1=new LinkedList<Integer>();
        queue2=new LinkedList<Integer>();
    }

    public Integer pop(){//队列1不为空,队列2为空,将队列顺序读到队列2中,则最后一个元素就是需要弹出的值
        Integer re=null;
        if(queue1.size()==0&&queue2.size()==0){
            return null;
        }
        if(queue2.size()==0){
            while(queue1.size()>0){
                re=queue1.removeFirst();//等同re=queue1.remove();
                if(queue1.size()!=0){//do not add the last element of queue1 to queue2  
                    queue2.addLast(re);
                }
            }
        }else if (queue1.size()==0){
            while(queue2.size()>0){
                re=queue2.removeFirst();
                if(queue2.size()!=0){//do not add the last element of queue2 to queue1  
                    queue1.addLast(re);
                }
            }
        }
        return re;
    }
    public Integer push(Integer o){
        if(queue1.size()==0&&queue2.size()==0){
            queue1.addLast(o);//queue2.addLast(o); is also ok  
        }
        if(queue1.size()!=0){
            queue1.addLast(o);//等同queue1.=add(0)
        }else if(queue2.size()!=0){
            queue2.addLast(o);
        }
        return o;
    }

    public static void main(String[] args) {
        StackImplementByTwoQueues stack=new StackImplementByTwoQueues();
        int tmp=0;
        stack.push(1);
        stack.push(2);
        stack.push(3);
        tmp=stack.pop();
        System.out.println(tmp);//3  
        stack.push(4);
        tmp=stack.pop();
        System.out.println(tmp);//4  
        tmp=stack.pop();
        System.out.println(tmp);//2  
        stack.push(5);
        stack.push(6);
        tmp=stack.pop();
        System.out.println(tmp);//6  
        tmp=stack.pop();
        System.out.println(tmp);//5  
        tmp=stack.pop();
        System.out.println(tmp);//1  
    }
}  

本文转载自:

上一篇: jvm GC专家 1
下一篇: 求树的直径
datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问
使用两个栈实现队列,使用两个队列实现栈。

我是一个栈,我的双胞胎弟弟叫队列。我的爸爸是数组,我的妈妈是链表。在上一篇文章中,向你们介绍了我的家族成员对于数据存储方面的能力和特性。还包括如何通过数组和链表来实现栈和队列。 ...

2018/03/25
0
0
JavaScript数据结构之队栈互搏

今天稍微停下前进的脚步,来看下队栈的左右互搏术。 前两天学习了队列和栈以后,今天就可以试着来用两个栈实现队列的功能 或者 用两个队列来实现栈的功能。 数据结构之---栈实现队列 1. 用两...

snowLu
2018/12/28
0
0
JavaScript 数据结构之队栈互搏

今天稍微停下前进的脚步,来看下队栈的左右互搏术。 前两天学习了队列和栈以后,今天就可以试着来用两个栈实现队列的功能或者用两个队列来实现栈的功能。 1. 用两个栈实现一个队列 1.1 题目分...

大灰狼的小绵羊哥哥
03/18
0
0
数据结构-栈和队列面试题(上)

在数据结构的学习过程中,栈和队列的掌握是十分重要的。所以找了几个很热门的面试题试试手并小结一下。先回顾下栈和队列的特性:栈是后进先出,主要接口有PUSH,POP,TOP,而队列是先进先出,...

sssssuuuuu666
2017/12/05
0
0
STL-关于栈和队列的面试题

题目分别为: 1.实现一个栈,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)。 2.使用两个栈实现一个队列。 3.使用两个队列实现一个栈。 4.判断元素出栈、入...

han8040laixin
2017/12/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JavaScript设计模式——适配器模式

  适配器模式是设计模式行为型模式中的一种模式;   定义:   适配器用来解决两个已有接口之间不匹配的问题,它并不需要考虑接口是如何实现,也不用考虑将来该如何修改;适配器不需要修...

有梦想的咸鱼前端
35分钟前
3
0
Andorid SQLite数据库开发基础教程(1)

Andorid SQLite数据库开发基础教程(1) Android数据库访问方式 SQLite是Android系统默认支持的文件数据库。该数据库支持SQL语言,适合开发人员上手。本教程将讲解如何开发使用SQLite的Andro...

大学霸
38分钟前
3
0
Handler简解

Handler 这里简化一下代码 以便理解 Handler不一定要在主线程建 但如Handler handler = new Handler(); 会使用当前的Looper的, 由于要更新UI 所以最好在主线程 new Handler() { mLooper = Lo...

shzwork
今天
4
0
h5获取摄像头拍照功能

完整代码展示: <!DOCTYPE html> <head> <title>HTML5 GetUserMedia Demo</title> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum......

诗书易经
今天
3
0
正向代理和反向代理

文章来源 运维公会:正向代理和反向代理 1、正向代理 (1)服务对象不同 正向代理服务器的服务对象是客户端,可以将客户端和代理服务器看作一个整体。 (2)配置方法不同 需要在客户端配置代...

运维团
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部