[算法总结] 3 道题搞定 BAT 面试——堆栈和队列
本文首发于我的个人博客：尾尾部落 0. 基础概念 栈：后进先出（LIFO） image 队列：先进先出（FIFO） image 1. 栈的 java 实现 import java.util.Arrays; public class Stack { private int size = 0; //栈顶位置 private int[] array; public Stack(){ this(10); } public Stack(int init) { if(init <= 0){ init = 10; } array = new int[init]; } /** * 入栈操作 * @param item 入栈的元素 */ public void push(int item){ if(size == array.length){ array = Arrays.copyOf(array, size*2); //扩容操作 } array[size++] = item; } /** * 获取栈顶元素，但栈顶元素不出栈 * @return 栈顶元素 */ public int peek(){ if(size == 0){ //空栈 throw new IndexOutOfBoundsException("栈是空的"); } return array[size-1]; } /** * 出栈，同时获取栈顶元素 * @return */ public int pop(){ int item = peek(); //获取栈顶元素 size--; //直接使元素个数减1，不用清除元素，下次入栈会覆盖旧元素的值 return item; } /** * 判断栈是否已满 * @return */ public boolean isFull(){ return size == array.length; } /** * 判断栈是否为空 * @return */ public boolean isEmpty(){ return size == 0; } public int getSize(){ return size; } } 2. 队列的 java 实现 public class ArrayQueue { private final Object[] queue; //声明一个数组 private int head; private int tail; /** * 初始化队列 * @param capacity 队列长度 */ public ArrayQueue(int capacity){ this.queue = new Object[capacity]; } /** * 入队 * @param o 入队元素 * @return 入队成功与否 */ public boolean put(Object o){ if(head == (tail+1)%queue.length){ //说明队满 return false; } queue[tail] = o; tail = (tail+1)%queue.length; //tail标记后移一位 return true; } /** * 返回队首元素，但不出队 * @return */ public Object peak() { if(head==tail){ //队空 return null; } return queue[head]; } /** * 出队 * @return 出队元素 */ public Object pull(){ if(head==tail){ return null; } Object item = queue[head]; queue[head] = null; return item; } /** * 判断是否为空 * @return */ public boolean isEmpty(){ return head == tail; } /** * 判断是否为满 * @return */ public boolean isFull(){ return head == (tail+1)%queue.length; } /** * 获取队列中的元素个数 * @return */ public int getsize(){ if(tail>=head){ return tail-head; }else{ return (tail+queue.length)-head; } } } 3. 用两个栈实现队列 剑指offer：用两个栈实现队列 LeetCode：Implement Queue using Stacks class MyQueue { Stack<Integer> input = new Stack<Integer>(); Stack<Integer> output = new Stack<Integer>(); /** Push element x to the back of queue. */ public void push(int x) { input.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { peek(); return output.pop(); } /** Get the front element. */ public int peek() { if(output.isEmpty()){ while(!input.isEmpty()) output.push(input.pop()); } return output.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return input.isEmpty() && output.isEmpty(); } } 4. 用队列实现栈 LeetCode：Implement Stack using Queues class MyStack { Queue<Integer> q1 = new LinkedList<Integer>(); Queue<Integer> q2 = new LinkedList<Integer>(); /** Push element x onto stack. */ public void push(int x) { if(q1.isEmpty()){ q1.add(x); for(int i = 0; i < q2.size(); i++){ q1.add(q2.poll()); } }else{ q2.add(x); for(int i = 0; i < q1.size(); i++){ q2.add(q1.poll()); } } } /** Removes the element on top of the stack and returns that element. */ public int pop() { return q1.isEmpty() ? q2.poll() : q1.poll(); } /** Get the top element. */ public int top() { return q1.isEmpty() ? q2.peek() : q1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return q1.isEmpty() && q2.isEmpty(); } } 5. 包含min函数的栈 剑指offer：包含min函数的栈 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。 class MinStack { Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> temp = new Stack<Integer>(); public void push(int x) { stack.push(x); if(temp.isEmpty() || temp.peek() >= x) temp.push(x); } public void pop() { int x = stack.pop(); int min = temp.peek(); if(x == min) temp.pop(); } public int top() { return stack.peek(); } public int getMin() { return temp.peek(); } } 6. 栈的压入、弹出序列 剑指offer：栈的压入、弹出序列 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的） import java.util.ArrayList; import java.util.Stack; public class Solution { public boolean IsPopOrder(int [] pushA, int [] popA) { if(pushA.length != popA.length || pushA.length == 0 || popA.length == 0) return false; Stack<Integer> stack = new Stack<>(); int index = 0; for(int i = 0; i < pushA.length; i++){ stack.push(pushA[i]); while(!stack.empty() && stack.peek() == popA[index]){ stack.pop(); index++; } } return stack.empty(); } }
