文档章节

两个栈实现队列+两个队列实现栈----java

 张欢19933
发布于 2017/02/27 15:09
字数 499
阅读 18
收藏 1

一.两个栈实现一个队列

思路:所有元素进stack1,然后全部出stack1并进入stack2.实现队列的先进先出即:若stack2非空,我们需要的恰好再栈顶,出栈;若要给队列添加元素,即先进sack1,要出队时,若stack2不为空就出栈,为空时就把stack1全部进栈到stack2

import java.util.Stack;
 
/**
* Created by smyhvae on 2015/9/9.
*/
public class Queue {
 
private Stack<Integer> stack1 = new Stack<>();//执行入队操作的栈
 private Stack<Integer> stack2 = new Stack<>();//执行出队操作的栈
 
//方法:给队列增加一个入队的操作
 public void push(int data) {
  stack1.push(data);
 
}
 
//方法:给队列正价一个出队的操作
 public int pop() throws Exception {
 
if (stack2.empty()) {//stack1中的数据放到stack2之前,先要保证stack2里面是空的(要么一开始就是空的,要么是stack2中的数据出完了),不然出队的顺序会乱的,这一点很容易忘
 
while (!stack1.empty()) {
    stack2.push(stack1.pop());//把stack1中的数据出栈,放到stack2中【核心代码】
   }
 
}
 
if (stack2.empty()) { //stack2为空时,有两种可能:1、一开始,两个栈的数据都是空的;2、stack2中的数据出完了
   throw new Exception("队列为空");
  }
 
return stack2.pop();
 }
 
public static void main(String[] args) throws Exception {
  Queue queue = new Queue();
  queue.push(1);
  queue.push(2);
  queue.push(3);
 
System.out.println(queue.pop());
 
queue.push(4);
 
System.out.println(queue.pop());
  System.out.println(queue.pop());
  System.out.println(queue.pop());
 
}
 
}

二.两个队列实现一个栈

import java.util.ArrayDeque;
import java.util.Queue;
 
/**
* Created by smyhvae on 2015/9/9.
*/
public class Stack {
 
Queue<Integer> queue1 = new ArrayDeque<Integer>();
 Queue<Integer> queue2 = new ArrayDeque<Integer>();
 
//方法:入栈操作
 public void push(int data) {
  queue1.add(data);
 }
 
//方法:出栈操作
 public int pop() throws Exception {
  int data;
  if (queue1.size() == 0) {
   throw new Exception("栈为空");
  }
 
while (queue1.size() != 0) {
   if (queue1.size() == 1) {
    data = queue1.poll();
    while (queue2.size() != 0) { //把queue2中的全部数据放到队列一中
     queue1.add(queue2.poll());
     return data;
    }
   }
   queue2.add(queue1.poll());
  }
  throw new Exception("栈为空");//不知道这一行的代码是什么意思
 }
 
public static void main(String[] args) throws Exception {
  Stack stack = new Stack();
 
stack.push(1);
  stack.push(2);
  stack.push(3);
 
System.out.println(stack.pop());
  System.out.println(stack.pop());
  stack.push(4);
 }
}

 

本文转载自:http://www.2cto.com/kf/201408/324163.html

共有 人打赏支持
粉丝 33
博文 460
码字总数 226276
作品 0
海淀
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 栈的 java 实现 2. 队列的 java 实现 1. 用两个栈实现队列 剑指offer:用两个栈实现队列 Leet...

繁著
09/04
0
0
JAVA线程15 - 新特性:阻塞队列&阻塞栈

一、阻塞队列 1. 概述 阻塞队列是Java5线程新特征中的内容,Java定义了阻塞队列的接口java.util.concurrent.BlockingQueue。 阻塞队列是一个指定长度的队列,如果队列满了,添加新元素的操作...

小米米儿小
2014/03/05
0
0
Android--面试中遇到的问题总结(三)

《Android 开发工程师面试指南 LearningNotes 》,作者是陶程,由梁观全贡献部分。大家可以去知乎关注这两位用心的少年。这份指南包含了大部分Android开发的基础、进阶知识,不仅可以帮助准备...

sealin
2017/02/22
0
0
Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。 40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。 几乎...

JAVA高级架构开发
10/07
0
0
java_面试_01_一个月的面试总结(java)

重点知识 由于我面试的JAVA开发工程师,针对于JAVA,需要理解的重点内容有: JVM内存管理机制和垃圾回收机制(基本每次面试都会问,一定要搞得透彻) JVM内存调优(了解是怎么回事,一般做项...

rayner
03/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

可爱的python测试开发库(python测试开发工具库汇总)

欢迎转载,转载请注明来源: github地址 谢谢点赞 本文地址 相关书籍下载 测试开发 Web UI测试自动化 splinter - web UI测试工具,基于selnium封装。 链接 selenium - web UI自动化测试。 链...

python测试开发人工智能安全
54分钟前
2
0
Shiro | 实现权限验证完整版

写在前面的话 提及权限,就会想到安全,是一个十分棘手的话题。这里只是作为学校Shiro的一个记录,而不是,权限就应该这样设计之类的。 Shiro框架 1、Shiro是基于Apache开源的强大灵活的开源...

冯文议
今天
1
0
linux 系统的运行级别

运行级别 运行级别 | 含义 0 关机 1 单用户模式,可以想象为windows 的安全模式,主要用于修复系统 2 不完全的命令模式,不含NFS服务 3 完全的命令行模式,就是标准的字符界面 4 系统保留 5 ...

Linux学习笔记
今天
2
0
学习设计模式——命令模式

任何模式的出现,都是为了解决一些特定的场景的耦合问题,以达到对修改封闭,对扩展开放的效果。命令模式也不例外: 命令模式是为了解决命令的请求者和命令的实现者之间的耦合关系。 解决了这...

江左煤郎
今天
3
0
字典树收集(非线程安全,后续做线程安全改进)

将500W个单词放进一个数据结构进行存储,然后进行快速比对,判断一个单词是不是这个500W单词之中的;来了一个单词前缀,给出500w个单词中有多少个单词是该前缀. 1、这个需求首先需要设计好数据结...

算法之名
昨天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部