直接上干货。。。。。
栈和队列常见题型：
实现栈和实现队列
主要包括：栈，队列，循环队列。
package com.sywyg;/** * 实现栈 * 数组应该是Object类型的 * 注意top的设置影响出栈和获取栈顶元素。 * size也可以用top代替 */class MyStack<E>{size;top;// 数组保存元素private Object[] stack = null;public MyStack(int length){stack = new Object[length];top = 0;}(){return size;}(E e){if(size == stack.length){try{throw new Exception(“栈已满”);}catch(Exception ex){ex.printStackTrace();}}stack[top++] = e;size++;}// 出栈public E pop(){E e = null;if(size == 0){try{throw new Exception(“栈为空”);}catch(Exception ex){ex.printStackTrace();}}e = (E)stack[–top];size–;return e;}// 获取栈顶元素public E top(){if(size == 0){try{throw new Exception(“栈为空”);}catch(Exception e){e.printStackTrace();}}return (E)stack[top-1];}}/** * 创建队列，，这种队列会造成假溢出 */class MyQueue<E>{size;front;back;private Object[] queue;public MyQueue(int length){queue = new Object[length];size = 0;front = 0;back = 0;}(){return size;}(E e){if(size == queue.length){try{throw new Exception(“队已满”);}catch(Exception ex){ex.printStackTrace();}}queue[back++] = e;size++;}// 出队public E dequeue(){E e = null;if(size == 0 || back == front){try{throw new Exception(“队为空”);}catch(Exception ex){ex.printStackTrace();}}e = (E)queue[front++];size–;return e;}// 返回队头public E front(){return (E)queue[front];}// 返回队尾？public E back(){return (E)queue[back – 1];}}/** * 循环队列，采用浪费一个位置（使用size可以保证全利用） * 这里不使用size标记队列的长度，尽管这种方式很简单 */class LoopQueue<E>{front;back;private Object[] queue;public LoopQueue(int length){// 浪费一个queue = new Object[length + 1];front = 0;back = 0;}(){return (back – front + queue.length)% queue.length;}(E e){if((front – back + queue.length)% queue.length == 1){try{throw new Exception(“队已满”);}catch(Exception ex){ex.printStackTrace();}}queue[back ++ % queue.length] = e;}// 出队public E dequeue(){E e = null;if(front == back){try{throw new Exception(“队为空”);}catch(Exception ex){ex.printStackTrace();}}e = (E)queue[front++ % queue.length];return e;}// 返回队头public E front(){return (E)queue[front];}// 返回队尾？public E back(){return (E)queue[(back – 1 + queue.length) % queue.length];}}两个栈实现一个队列
思想：一个栈A只进，一个栈B只出，B为空则A元素进入B，再出栈。
package com.sywyg;/** * 两个栈实现一个队列。 * 这样仍然会造成假溢出。 * * */<Stack<E> stack1 = new Stack<E>();// stack2用来出队private Stack<E> stack2 = new Stack<E>();(E e){stack1.push(e);//System.out.println(“此时stack1栈顶元素为：” + stack1.top());}// 出队public E dequeue(){E e = null;if(stack2.size() != 0){e = stack2.pop();}else if(stack1.size() != 0){int length = stack1.size();for(int i = 0;i<length;i++){stack2.push(stack1.pop());//System.out.println(“此时stack2栈顶元素为：” + stack2.top());}e = stack2.pop();}return e;}}- 测试：进进出出，进出。- 如何用两个队列实现一个栈。#设计栈，使得pop，push和min时间复杂度为O(1)思想：额外的栈A存放当前最小值，每当进来的值a小于/等于该栈顶值b时，a需要入栈A；出栈时若栈A的栈顶和刚出栈的元素相等时，则A也出栈。“`javapackage com.sywyg;import java.util.Stack;/** * 设计栈，使得pop，push和min时间复杂度为O(1)。 * 或者使用一个每个最小值再包含一个计数标记 */<E>{private Stack<E> stack,stackMin;public Solution(){stack = new Stack<E>();stackMin = new Stack<E>();}(E e){stack.push(e);if(stackMin.isEmpty()){stackMin.push(e);}else if(stackMin.peek() >= e){stackMin.push(e);}}// 出栈public E pop(){E e = stack.pop();if(e == stackMin.peek()){stackMin.pop();}}// 返回最小public E min(){return stackMin.peek();}}<div class=”se-preview-section-delimiter”></div>测试：小大大大小小，每次出栈判断是否正确。时间复杂度：O(1),空间复杂度O(n)滑动窗口的最大值
给定一个数组，和滑动窗口的大小，计算每个窗口中的最大值。例如数组{1，2，3，4，5}，窗口大小为3。那么共存在3个滑动窗口，它们的大小为：{3，4，5}。
飞机一阵抖动，我终于说出了最后一句再见。
