企业做网站的,深圳展厅装修公司企业展厅设计公司,wordpress人型图标,个性化网站面试的时候#xff0c;栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容#xff1a;(1)栈的创建(2)队列的创建(3)两个栈实现一个队列(4)两个队列实现一个栈(5)设计含最小函数min()的栈#xff0c;要求min、push、pop、的时间复杂度都是O(1)(6)判断栈的push和p…面试的时候栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容(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 stack1 new Stack();//执行入队操作的栈private Stack 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 queue1 new ArrayDeque();Queue queue2 new ArrayDeque();//方法入栈操作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 stack new Stack();private Stack minStack new Stack(); //辅助栈栈顶永远保存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出栈15、4、3、2、1(正确)出栈24、5、3、2、1(正确)出栈34、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 stack new Stack(); //这里需要用到辅助栈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 stack new Stack();int[] data1 {1,2,3,4,5};int[] data2 {4,5,1};int[] data3 {4,1};System.out.println(sequenseIsPop(data1,data2));System.out.println(sequenseIsPop(data1,data3));}}代码比较简洁但也比较难理解要仔细体会。运行效果以上就是有关java栈和队列的经典面试题目希望可以帮助大家顺利通过面试。相关文章总结以上是编程之家为你收集整理的Java实现栈和队列面试题全部内容希望文章能够帮你解决Java实现栈和队列面试题所遇到的程序开发问题。如果觉得编程之家网站内容还不错欢迎将编程之家网站推荐给程序员好友。本图文内容来源于网友网络收集整理提供作为学习参考使用版权属于原作者。如您喜欢交流学习经验点击链接加入交流1群1065694478(已满)交流2群163560250
