Java面试题：栈和队列的实现.docxVIP

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