Java实现栈和队列面试题

面试的时候,栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容:

(1)栈的创建

(2)队列的创建

(3)两个栈实现一个队列

(4)两个队列实现一个栈

(5)设计含最小函数min()的栈,要求min、push、pop、的时间复杂度都是O(1)

(6)判断栈的push和pop序列是否一致

1、栈的创建:

我们接下来通过链表的形式来创建栈,方便扩充。

代码实现:

public class Stack {

public Node head;
 public Node current;

//方法:入栈操作
 public void push(int data) {
  if (head == null) {
   head = new Node(data);
   current = head;
  } else {
   Node node = new Node(data);
   node.pre = current;//current结点将作为当前结点的前驱结点
   current = node; //让current结点永远指向新添加的那个结点
  }
 }

public Node pop() {
  if (current == null) {
   return null;
  }

Node node = current; // current结点是我们要出栈的结点
  current = current.pre; //每出栈一个结点后,current后退一位
  return node;

}

class Node {
  int data;
  Node pre; //我们需要知道当前结点的前一个结点

public Node(int data) {
   this.data = data;
  }
 }

public static void main(String[] args) {

Stack stack = new Stack();
  stack.push(1);
  stack.push(2);
  stack.push(3);

System.out.println(stack.pop().data);
  System.out.println(stack.pop().data);
  System.out.println(stack.pop().data);
 }

}

入栈操作时,14、15行代码是关键。

运行效果:

2、队列的创建:

队列的创建有两种形式:基于数组结构实现(顺序队列)、基于链表结构实现(链式队列)。

我们接下来通过链表的形式来创建队列,这样的话,队列在扩充时会比较方便。队列在出队时,从头结点head开始。

代码实现:

入栈时,和在普通的链表中添加结点的操作是一样的;出队时,出的永远都是head结点。

public class Queue {
 public Node head;
 public Node curent;

//方法:链表中添加结点
 public void add(int data) {
  if (head == null) {
   head = new Node(data);
   curent = head;
  } else {
   curent.next = new Node(data);
   curent = curent.next;
  }
 }

//方法:出队操作
 public int pop() throws Exception {
  if (head == null) {
   throw new Exception("队列为空");
  }

Node node = head; //node结点就是我们要出队的结点
  head = head.next; //出队之后,head指针向下移

return node.data;

}

class Node {
  int data;
  Node next;

public Node(int data) {
   this.data = data;
  }
 }

public static void main(String[] args) throws Exception {
  Queue queue = new Queue();
  //入队操作
  for (int i = 0; i < 5; i++) {
   queue.add(i);
  }

//出队操作
  System.out.println(queue.pop());
  System.out.println(queue.pop());
  System.out.println(queue.pop());

}
}

运行效果:

3、两个栈实现一个队列:

思路:

栈1用于存储元素,栈2用于弹出元素,负负得正。

说的通俗一点,现在把数据1、2、3分别入栈一,然后从栈一中出来(3、2、1),放到栈二中,那么,从栈二中出来的数据(1、2、3)就符合队列的规律了,即负负得正。

完整版代码实现:

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());

}

}

注意第22行和第30行代码的顺序,以及注释,需要仔细理解其含义。

运行效果:

4、两个队列实现一个栈:

思路:

将1、2、3依次入队列一, 然后最上面的3留在队列一,将下面的2、3入队列二,将3出队列一,此时队列一空了,然后把队列二中的所有数据入队列一;将最上面的2留在队列一,将下面的3入队列二。。。依次循环。

代码实现:

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);
 }
}

运行效果:

5、设计含最小函数min()的栈,要求min、push、pop、的时间复杂度都是O(1)。min方法的作用是:就能返回是栈中的最小值。【微信面试题】

普通思路:

一般情况下,我们可能会这么想:利用min变量,每次添加元素时,都和min元素作比较,这样的话,就能保证min存放的是最小值。但是这样的话,会存在一个问题:如果最小的元素出栈了,那怎么知道剩下的元素中哪个是最小的元素呢?

改进思路:

这里需要加一个辅助栈,用空间换取时间。辅助栈中,栈顶永远保存着当前栈中最小的数值。具体是这样的:原栈中,每次添加一个新元素时,就和辅助栈的栈顶元素相比较,如果新元素小,就把新元素的值放到辅助栈中,如果新元素大,就把辅助栈的栈顶元素再copy一遍放到辅助栈的栈顶;原栈中,出栈时,

完整代码实现:

import java.util.Stack;

/**
* Created by smyhvae on 2015/9/9.
*/
public class MinStack {

private Stack<Integer> stack = new Stack<Integer>();
 private Stack<Integer> minStack = new Stack<Integer>(); //辅助栈:栈顶永远保存stack中当前的最小的元素

public void push(int data) {
  stack.push(data); //直接往栈中添加数据

//在辅助栈中需要做判断
  if (minStack.size() == 0 || data < minStack.peek()) {
   minStack.push(data);
  } else {
   minStack.add(minStack.peek()); //【核心代码】peek方法返回的是栈顶的元素
  }
 }

public int pop() throws Exception {
  if (stack.size() == 0) {
   throw new Exception("栈中为空");
  }

int data = stack.pop();
  minStack.pop(); //核心代码
  return data;
 }

public int min() throws Exception {
  if (minStack.size() == 0) {
   throw new Exception("栈中空了");
  }
  return minStack.peek();
 }

public static void main(String[] args) throws Exception {
  MinStack stack = new MinStack();
  stack.push(4);
  stack.push(3);
  stack.push(5);

System.out.println(stack.min());
 }
}

运行效果:

6、判断栈的push和pop序列是否一致:

通俗一点讲:已知一组数据1、2、3、4、5依次进栈,那么它的出栈方式有很多种,请判断一下给出的出栈方式是否是正确的?

例如:

数据:

1、2、3、4、5

出栈1:

5、4、3、2、1(正确)

出栈2:

4、5、3、2、1(正确)

出栈3:

4、3、5、1、2(错误)

完整版代码:

import java.util.Stack;
/**
* Created by smyhvae on 2015/9/9.*/public class StackTest {

//方法:data1数组的顺序表示入栈的顺序。现在判断data2的这种出栈顺序是否正确    public static boolean sequenseIsPop(int[] data1, int[] data2) {        Stack<Integer> stack = new Stack<Integer>(); //这里需要用到辅助栈

for (int i = 0, j = 0; i < data1.length; i++) {            stack.push(data1[i]);

while (stack.size() > 0 && stack.peek() == data2[j]) {                stack.pop();                j++;            }        }        return stack.size() == 0;    }

public static void main(String[] args) {

Stack<Integer> stack = new Stack<Integer>();

int[] data1 = {1, 2, 3, 4, 5};        int[] data2 = {4, 5, 3, 2, 1};        int[] data3 = {4, 5, 2, 3, 1};

System.out.println(sequenseIsPop(data1, data2));        System.out.println(sequenseIsPop(data1, data3));    }}

代码比较简洁,但也比较难理解,要仔细体会。

运行效果:

以上就是有关java栈和队列的经典面试题目,希望可以帮助大家顺利通过面试。

时间: 2015-09-15

JAVA实现链表面试题

这份笔记整理了整整一个星期,每一行代码都是自己默写完成,并测试运行成功,同时也回顾了一下<剑指offer>这本书中和链表有关的讲解,希望对笔试和面试有所帮助. 本文包含链表的以下内容: 1.单链表的创建和遍历 2.求单链表中节点的个数 3.查找单链表中的倒数第k个结点(剑指offer,题15) 4.查找单链表中的中间结点 5.合并两个有序的单链表,合并之后的链表依然有序[出现频率高](剑指offer,题17) 6.单链表的反转[出现频率最高](剑指offer,题16) 7.从尾到头打印单链表(

小米Java程序员第二轮面试10个问题 你是否会被刷掉?

近日,开发者头条上分享了一篇"小米java第二轮面经",有很多的java程序员表示非常有兴趣. 下面就和各位分享小米java第二轮面经: 0.谈谈对Spring的认识 1.java集合的继承关系 相关文章: java集合继承关系图分享 Java集合类的组织结构和继承.实现关系详解 Java集合继承体系详解 Java中集合关系图及常见操作详解 2.你知道CLOSE_WAIT这个状态吗? 3.谈谈你对jvm.java内存模型的认识? 4.Java里的红黑树是怎么实现的? 相关文章: jav

java面试常见问题之Hibernate总结

主要从以下十几个方面对Hibernate做总结,包括Hibernate的检索方式,Hibernate中对象的状态,Hibernate的3种检索策略是什么,分别适用于哪种场合,ORM解决的不匹配问题, Hibernate映射继承关系的3种方式,Session的find()方法以及Query接口的区别等方面问题的总结,具体内容如下: 1  Hibernate的检索方式 Ø  导航对象图检索(根据已经加载的对象,导航到其他对象.) Ø  OID检索(按照对象的OID来检索对象.) Ø  HQL检索(使

探讨Java中最常见的十道面试题(超经典)

第一,谈谈final, finally, finalize的区别. final?修饰符(关键字)如果一个类被声明为final,意味着它不能再派生出新的子类,不能作为父类被继承.因此一个类不能既被声明为 abstract的,又被声明为final的.将变量或方法声明为final,可以保证它们在使用中不被改变.被声明为final的变量必须在声明时给定初值,而在以后的引用中只能读取,不可修改.被声明为final的方法也同样只能使用,不能重载 finally?再异常处理时提供 finally 块来执行任何

关于Java集合框架面试题(含答案)上

1.Java集合框架是什么?说出一些集合框架的优点? 每种编程语言中都有集合,最初的Java版本包含几种集合类:Vector.Stack.HashTable和Array.随着集合的广泛使用,Java1.2提出了囊括所有集合接口.实现和算法的集合框架.在保证线程安全的情况下使用泛型和并发集合类,Java已经经历了很久.它还包括在Java并发包中,阻塞接口以及它们的实现.集合框架的部分优点如下: (1)使用核心集合类降低开发成本,而非实现我们自己的集合类. (2)随着使用经过严格测试的集合框架类,代

最有价值的50道java面试题 适用于准入职Java程序员

下面的内容是对网上原有的Java面试题集及答案进行了全面修订之后给出的负责任的题目和答案,原来的题目中有很多重复题目和无价值的题目,还有不少的参考答案也是错误的,修改后的Java面试题集参照了JDK最新版本,去掉了EJB 2.x等无用内容,补充了数据结构和算法相关的题目.经典面试编程题.大型网站技术架构.操作系统.数据库.软件测试.设计模式.UML等内容,同时还对很多知识点进行了深入的剖析,例如hashCode方法的设计.垃圾收集的堆和代.Java新的并发编程.NIO.2等,相信对准备入职的Ja

Java中类的加载顺序剖析(常用于面试题)

这其实是去年校招时我遇到的一道阿里巴巴的笔试题(承认有点久远了-.-),嗯,如果我没记错的话,当时是作为Java方向的一道选做大题.当然题意没有这么直白,题目只要求你写出程序运行后所有System.out.println的输出结果,其中程序是题目给的,而各个System.out.println的执行顺序不同会导致最后程序输出的结果也不同. 具体的题目我肯定记不清,不过我们可以换个直接的问法,如果类A和类B中有静态变量,静态语句块,非静态变量,非静态语句块,构造函数,静态方法,非静态方法,同时类A

15个高级Java多线程面试题及回答

Java 线程面试问题 在任何Java面试当中多线程和并发方面的问题都是必不可少的一部分.如果你想获得任何股票投资银行的前台资讯职位,那么你应该准备很多关于多线程的问题.在投资银行业务中多线程和并发是一个非常受欢迎的话题,特别是电子交易发展方面相关的.他们会问面试者很多令人混淆的Java线程问题.面试官只是想确信面试者有足够的Java线程与并发方面的知识,因为候选人中有很多只浮于表面.用于直接面向市场交易的高容量和低延时的电子交易系统在本质上是并发的.下面这些是我在不同时间不同地点喜欢问的Jav

java 多态性详解及常见面试题

java多态性 多态分两种: (1)   编译时多态(设计时多态):方法重载. (2)   运行时多态:JAVA运行时系统根据调用该方法的实例的类型来决定选择调用哪个方法则被称为运行时多态.(我们平时说得多的事运行时多态,所以多态主要也是指运行时多态) 运行时多态存在的三个必要条件: 一.要有继承(包括接口的实现): 二.要有重写: 三.父类引用指向子类对象. 多态的好处: 1.可替换性(substitutability).多态对已存在代码具有可替换性.例如,多态对圆Circle类工作,对其他任

关于Java集合框架面试题(含答案)下

21.HashMap和HashTable有何不同? (1)HashMap允许key和value为null,而HashTable不允许. (2)HashTable是同步的,而HashMap不是.所以HashMap适合单线程环境,HashTable适合多线程环境. (3)在Java1.4中引入了LinkedHashMap,HashMap的一个子类,假如你想要遍历顺序,你很容易从HashMap转向LinkedHashMap,但是HashTable不是这样的,它的顺序是不可预知的. (4)HashMap

Java集合框架源码分析之LinkedHashMap详解

LinkedHashMap简介 LinkedHashMap是HashMap的子类,与HashMap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到LinkedHashmap的节点一一串成了一个双向循环链表,因此它保留了节点插入的顺序,可以使节点的输出顺序与输入顺序相同. LinkedHashMap可以用来实现LRU算法(这会在下面的源码中进行分析). LinkedHashMap同样是非线程安全的,只在单线程环境下使用. LinkedHashMap源码剖析 LinkedHashM

通过实例学习Java集合框架HashSet

这篇文章主要介绍了通过实例学习Java集合框架HashSet,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 示例 1 : 元素不能重复 Set中的元素,不能重复 package collection; import java.util.HashSet; public class TestCollection { public static void main(String[] args) { HashSet<String> names = n

关于Java集合框架的总结

本篇文章先从整体介绍了Java集合框架包含的接口和类,然后总结了集合框架中的一些基本知识和关键点,并结合实例进行简单分析.当我们把一个对象放入集合中后,系统会把所有集合元素都当成Object类的实例进行处理.从JDK1.5以后,这种状态得到了改进:可以使用泛型来限制集合里元素的类型,并让集合记住所有集合元素的类型. 一.综述 所有集合类都位于java.util包下.集合中只能保存对象(保存对象的引用变量).(数组既可以保存基本类型的数据也可以保存对象). 当我们把一个对象放入集合中后,系统会把所

Java集合框架中迭代器Iterator解析

Java里面的数组数据可以通过索引来获取,那么对象呢?也是通过索引吗?今天我们就来分析一下Java集合中获取集合对象的方法迭代-Iterator. 本篇文章主要分析一下Java集合框架中的迭代器部分,Iterator,该源码分析基于JDK1.8,分析工具,AndroidStudio,文章分析不足之处,还请指正! 一.简介 我们常常使用 JDK 提供的迭代接口进行 Java 集合的迭代. Iterator iterator = list.iterator(); while(iterator.has

Java集合框架LinkedList详解及实例

Java集合框架LinkedList详解 LinkedList定义 package java.util; public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0; transient Node<E> first;

详谈java集合框架

1.为什么使用集合框架 当我们并不知道程序运行时会需要多少对象,或者需要更复杂方式存储对象--可以使用Java集合框架 2.Java集合框架包含的内容 接口:(父类)Collection接口下包含List(子类 )接口和Set(子类) 接口 List接口下又包含(ArrayList集合实现类和LinkedList集合实现类) Set接口下又包含(HashSet集合实现类和TreeSet集合实现类) 接口:(父类)Map接口下包含(HashMap集合实现类和TreeMap 集合实现类) *Coll

java集合框架详解

1.java集合框架概述 java SE包含了由一组类和接口组成的java集合框架(java Collection Framework,简称JCF),其主要功能是用来将存储的数据以某种结构组织,并以特定的方式来访问这些数据,其目标是提供一个处理对象集合的通用框架,减少程序员处理不同对象集合时的编码量. 集合类中的一些区别,除了它们是否支持重复元素操作外,还包括元素是否有顺序,以及是否允许添加null元素.java集合框架中根据这三个区别,将对象的存储方式分为三种类型,分别是: Set(集):对象

Lambda表达式和Java集合框架

本文github地址 Java8为容器新增一些有用的方法,这些方法有些是为完善原有功能,有些是为引入函数式编程(Lambda表达式),学习和使用这些方法有助于我们写出更加简洁有效的代码.本文分别以ArrayList和HashMap为例,讲解Java8集合框架(Java Collections Framework)中新加入方法的使用. 前言 我们先从最熟悉的Java集合框架(Java Collections Framework, JCF)开始说起. 为引入Lambda表达式,Java8新增了jav