线性表

线性表是n个具有相同特性的数据元素的有限序列.线性表是一种在实际中广泛应用的数据结构
线性表在逻辑层面是连续的,但在物理结构上不一定连续,线性表在物理结构中存储一般以数组或者链式结构的形式存在

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下是以数组来进行存储数据.在数组中进行增删改查
接口实现

public class List implements MyArrayList{private int[] elements;private int usedSize;//顺序表的默认大小private static final int DEFAULT_SIZE = 2;public List() {this.elements = new int[DEFAULT_SIZE];}public List(int capacity) {this.elements = new int[capacity];}@Overridepublic void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(this.elements[i]+" ");}System.out.println();}@Overridepublic boolean isFull() {/*if(this.usedSize==this.elements.length) {return true;}return false;*/return this.elements.length==usedSize;}private void isEnlarger() {if(isFull()) {elements = Arrays.copyOf(elements,elements.length*2);}}@Overridepublic void add(int data) {isEnlarger();this.elements[this.usedSize] = data;this.usedSize++;}@Overridepublic void add(int pos, int data) {try {checkPos(pos);} catch (PosIllegal e) {e.printStackTrace();return;}isEnlarger();int move = usedSize;while (move-1>=pos) {elements[move] = elements[move-1];move--;}elements[pos] = data;usedSize++;}private void checkPos(int pos) throws PosIllegal{if(pos<0||pos>usedSize) {throw new PosIllegal("插入下标异常: "+pos);}}@Overridepublic boolean contains(int toFind) {if(isEmpty()) {return false;}for (int i = 0; i < usedSize; i++) {//查找引用类型,要重写方法if(toFind==elements[i]) {return true;}}return false;}@Overridepublic boolean isEmpty() {return usedSize==0;}@Overridepublic int indexOf(int toFind) {if(isEmpty()) {return -1;}for (int i = 0; i < usedSize; i++) {//查找引用类型,要重写方法if(toFind==elements[i]) {return i;}}return -1;}@Overridepublic int get(int pos) {try {checkPosOnGet(pos);} catch (PosIllegal e) {e.printStackTrace();}return elements[pos];}private void checkPosOnGet(int pos) throws PosIllegal{if(pos<0||pos>=usedSize) {throw new PosIllegal("获取指定下标异常: "+pos);}}@Overridepublic void set(int pos, int value) {try {checkPosOnGet(pos);} catch (PosIllegal e) {e.printStackTrace();return;}elements[pos] = value;}@Overridepublic void remove(int toRemove) {if(indexOf(toRemove)==-1) {System.out.println("无该数值可以删除");return;}int i = indexOf(toRemove);while (i+1< usedSize) {elements[i] = elements[i+1];i++;}usedSize--;}@Overridepublic int size() {return usedSize;}@Overridepublic void clear() {this.usedSize = 0;}}

ArrayList简介

在集合框架里,ArrayList是一个普通的类,实现List接口
说明

1. ArrayList是以泛型方式实现的,使用时必须要先实例化
2. ArrayList实现了RandomAccess接口,表明ArrayList支持随机访问
3. ArrayList实现Cloneable接口,表明ArrayList是可以clone的
4. ArrayList实现了Serializable,表明ArrayList是支持序列化的
5. ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表

ArrayList使用

ArrayList的构造

方法
ArrayList() 无参构造
ArrayList(Collection<? extends E> c) 利用其他Collection构建ArrayList
ArrayList(int initialCapacity) 指定顺序表初识容量

Collection<? extends E>中?是通配符
将来给ArrayList可以传入Collection

//类型是ArrayList,ArrayList实现了Collection接口,类型匹配ArrayList<Integer> arrayList = new ArrayList<>();
//你当前传入的arraylist里面的元素一定是ArrayList<Integer> arrayList1中Integer的子类ArrayList<Integer> arrayList1 = new ArrayList<>(arrayList);

换个栗子

        ArrayList<Integer> arrayList = new ArrayList<>();
//Integer是Number的子类ArrayList<Number> arrayList1 = new ArrayList<>(arrayList);

Collection<? extends E>中?是E的子类或者E本身
传入的arrayList一定是Number或者Number的子类,结合如下代码,E和?的代表分别是Number和Integer

这种构造方法可以将集合一组内容都填充到另一个List里面,类似应用如下代码:

    public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(1);arrayList.add(1);arrayList.add(1);ArrayList<Number> arrayList1 = new ArrayList<>(arrayList);arrayList1.add(2);arrayList1.add(2);arrayList1.add(2);System.out.println(arrayList1);}

ArrayList常见操作

boolean addAll(Collection<? extends E> c) 尾插 c 中的元素

    public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(1);list.add(1);list.add(1);ArrayList<Number> list1 = new ArrayList<>();list1.addAll(list);System.out.println(list1);}

E remove(int index) 删除 index 位置元素

boolean remove(Object o) 删除遇到的第一个 o

    public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.remove(new Integer(4));System.out.println(list);}

E get(int index) 获取下标 index 位置元素

E set(int index, E element) 将下标 index 位置元素设置为 element

void clear() 清空

boolean contains(Object o) 判断 o 是否在线性表中

int indexOf(Object o) 返回第一个 o 所在下标

int lastIndexOf(Object o) 返回最后一个 o 的下标

List subList(int fromIndex, int toIndex) 截取部分 list

ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器
for循环+下标

        ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(1);list.add(1);list.add(1);for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}

foreach

        for (Integer x : list) {System.out.print(x+" ");}

迭代器(使用迭代器遍历集合类)

        ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(1);list.add(1);list.add(1);Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()) {System.out.println(iterator.next()+" ");}

ArrayList最长使用的遍历方式是:for循环+下标以及foreach

ArrayList的扩容机制

ArrayList是一个动态类型的顺序表,就是在插入元素的时候会自动扩容
检测是否真正需要扩容,如果是调用grow准备扩容
预计需要扩容的大小

1. 初步预估扩容1.5倍
2. 如果用户所需大小超过预估1.5倍,则按照用户所需大小进行扩容
3. 真正扩容之前检测是否能扩容成功,防止太大导致扩容失败
   使用copyOf进行扩容

利用ArrayList洗牌

卡包

package card;public class Card {private String color;//花色private int number;//数字public String getColor() {return color;}public Card(String color, int number) {this.color = color;this.number = number;}public void setColor(String color) {this.color = color;}public int getNumber() {return number;}public void setNumber(int number) {this.number = number;}@Overridepublic String toString() {return color+":"+number;}
}

操作包

package card;import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class CardDemo {private String[] suits = {"♥","♠","♦","♣"};public List<Card> buyCard() {List<Card> list = new ArrayList<>();//创建一副新牌for (int i = 0; i < 4; i++) {for (int j = 1; j <= 13; j++) {Card card = new Card(suits[i], j);list.add(card);}}return list;}public void dislocate(List<Card> cardList) {Random random = new Random();//从后往前开始进行互换,打乱牌面for (int i = cardList.size()-1; i > 0 ; i--) {int rand = random.nextInt(i);swap(cardList,i,rand);}}public static void swap(List<Card> cardList,int x,int y) {//交换牌Card tmp = cardList.get(x);cardList.set(x,cardList.get(y));cardList.set(y,tmp);}public void Inauguration(List<Card> cardList) {List<List<Card>> roles = new ArrayList<>();//三个人的牌建立顺序表储存List<Card> role1 = new ArrayList<>();List<Card> role2 = new ArrayList<>();List<Card> role3 = new ArrayList<>();roles.add(role1);roles.add(role2);roles.add(role3);for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {//摸牌Card card = cardList.get(0);roles.get(j).add(card);cardList.remove(0);}}System.out.println("第一个人的牌");System.out.println(roles.get(0));System.out.println("第二个人的牌");System.out.println(roles.get(1));System.out.println("第三个人的牌");System.out.println(roles.get(2));System.out.println("剩余的牌");System.out.println(cardList);}
}

测试包

package card;import java.util.List;public class Test {public static void main(String[] args) {CardDemo cardDemo =  new CardDemo();List<Card> cardList = cardDemo.buyCard();System.out.println("扑克牌如下 : ");System.out.println(cardList);System.out.println("打乱如下");cardDemo.dislocate(cardList);System.out.println(cardList);cardDemo.Inauguration(cardList);}
}

ArrayList的优缺点

缺点

1. 插入数据必须移动其他数据,最坏情况插入0位置,时间复杂度O(N)
2. 删除数据也要移动数据,最坏情况删除0位置,时间复杂度O(N)
3. 扩容之后有可能会浪费空间

优点
4. 在给定下标进行查找的时候,时间复杂度O(1)

总结
顺序表比较适合给定下标查找的场景

链表

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用来进行链接的

链表的实现

链表接口

package Demo01;public interface Ilist {
//头插法void addFirst(int data);
//尾插法void addLast(int data);
//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中boolean contains(int key);
//删除第一次出现关键字为key的节点public void remove(int key);
//删除所有值为key的节点void removeAllKey(int key);
//得到单链表的长度int size();void clear();void display();
}

链表实现

package Demo01;import org.omg.CORBA.CODESET_INCOMPATIBLE;import java.util.List;public class MyList implements Ilist{static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;@Overridepublic void addFirst(int data) {ListNode newNode = new ListNode(data);newNode.next = head;head = newNode;}@Overridepublic void addLast(int data) {ListNode newNode = new ListNode(data);if(head==null) {head = newNode;} else {ListNode curNode = head;while (curNode.next!=null) {curNode = curNode.next;}curNode.next = newNode;}}@Overridepublic void addIndex(int index, int data) {ListNode newNode = new ListNode(data);if(index<0||index>size()) {System.out.println("插入下标违法");return;}if(index==0) {addFirst(data);} else {int count = 0;ListNode curNode = head;while(count+1!=index) {curNode = curNode.next;count++;}ListNode tmp = curNode.next;curNode.next = newNode;newNode.next = tmp;}}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur!=null) {if(cur.val==key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(head==null) {return;}if(!contains(key)) {System.out.println("不存在该值");return;}if(head.val==key) {head = head.next;} else {ListNode curNode = head;while (curNode.next.val!=key) {curNode = curNode.next;}curNode.next = curNode.next.next;}}@Overridepublic void removeAllKey(int key) {if(head==null) {return;}if(!contains(key)) {System.out.println("该值不存在,无法删除");return;}while (head!=null&&head.val==key) {head = head.next;}if(head!=null) {ListNode curNode = head;while (curNode.next !=null) {if (curNode.next.val==key) {curNode.next = curNode.next.next;} else {curNode = curNode.next;}}}}@Overridepublic int size() {int count = 0;ListNode cur = head;while (cur!=null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {if(head!=null) {while (head!=null) {ListNode tmp = head.next;head = null;head = tmp;}}}@Overridepublic void display() {ListNode cur = head;while (cur!=null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}
}

双向链表的实现

双向链表的实现

public class MyLinkedList implements Ilist{
//双向链表的节点static class ListNode {//后继public ListNode next;//前驱public ListNode prev;public int val;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//头插法@Overridepublic void addFirst(int data) {ListNode newNode = new ListNode(data);if(head!=null) {head.prev = newNode;newNode.next = head;head = newNode;} else {head = last = newNode;}}//尾插法@Overridepublic void addLast(int data) {ListNode newNode = new ListNode(data);if(head==null) {head = last = newNode;} else {last.next = newNode;newNode.prev = last;last = newNode;}}@Overridepublic void addIndex(int index, int data) {if(index<0||index>size()) {System.out.println("index  违法");return;}if(index==0) {addFirst(data);return;}if(index==size()) {addLast(data);return;}int count = 0;ListNode curNode = head;ListNode node = new ListNode(data);while(count!=index) {curNode = curNode.next;count++;}node.prev = curNode.prev;node.next = curNode;curNode.prev.next = node;node.next.prev = node;}
//是否包含某个值@Overridepublic boolean contains(int key) {ListNode curNode = head;while(curNode!=null) {if(curNode.val==key) {return true;}curNode = curNode.next;}return false;}
//删除某值@Overridepublic void remove(int key) {if(head.val==key) {head.next.prev = null;head = head.next;return;}ListNode curNode = head;while (curNode!=null) {if(curNode.val==key) {break;}curNode = curNode.next;}if(curNode==null) {System.out.println("没有该值,无法删除");return;}curNode.prev.next = curNode.next;if(curNode!=last) {curNode.prev = curNode.prev;} else {last = last.prev;}}
//删除所有该值@Overridepublic void removeAllKey(int key) {if(head==null) {return;}//移除链表头节点连续出现移除的数值while(head!=null&&head.val==key) {head = head.next;}if(head==null) {last = null;return;} else {head.prev = null;}ListNode cur = head;//处理中间和末尾出现移除节点的情况while (cur!=null) {if(cur.val == key) {cur.prev.next = cur.next;if(cur!=last) {cur.next.prev = cur.prev;} else {last = last.prev;}}cur = cur.next;}}
//得到链表长度@Overridepublic int size() {int count = 0;ListNode curNode = head;while(curNode!=null) {count++;curNode = curNode.next;}return count;}@Overridepublic void clear() {ListNode cur = head;while (cur!=null) {ListNode tmp = cur.next;cur.prev = null;cur.next = null;cur = tmp;}head = null;last = null;}
//打印链表@Overridepublic void display() {ListNode curNode = head;while(curNode!=null) {System.out.print(curNode.val+" ");curNode = curNode.next;}System.out.println();}
}

LinkedList

LinkedList引入

LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续空间中,元素存储在单独的节点中,然后通过引用将节点连接起来,因此在任意位置或者删除元素时,不需要移动元素,效率比较高

说明

1. LinkedList实现了List接口
2. LinkedList的底层使用双向链表
3. LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)
4. LinkedList比较适合任意插入的场景

LinkedList的使用

LinkedList的构造

方法 解释
LinkedList() 无参构造
public LinkedList(Collection<? extends E> c) 使用其他集合容器中元素构造List

    public static void main(String[] args) {List<Integer> list = new LinkedList<>();List<Double> list1 = new LinkedList<>();list1.add(1.1);list1.add(2.1);List<Number> list2 = new LinkedList<>(list1);list2.add(3);list2.add(4);System.out.println(list2);}

LinkedList的常用方法介绍

方法 解释
boolean add(E e) 尾插 e
void add(int index, E element) 将 e 插入到 index 位置

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(0,6);for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}}

boolean addAll(Collection<? extends E> c) 尾插 c 中的元素

        LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(0,6);LinkedList<Number> list1 = new LinkedList<>();list1.add(2.3);list1.add(2);list1.addAll(list);for (int i = 0; i < list1.size(); i++) {System.out.print(list1.get(i)+" ");}

E remove(int index) 删除 index 位置元素
boolean remove(Object o) 删除遇到的第一个 o
E get(int index) 获取下标 index 位置元素
E set(int index, E element) 将下标 index 位置元素设置为 element
void clear() 清空
boolean contains(Object o) 判断 o 是否在线性表中
int indexOf(Object o) 返回第一个 o 所在下标
int lastIndexOf(Object o) 返回最后一个 o 的下标
List subList(int fromIndex, int toIndex) 截取部分 list

LinkedList的遍历

LinkedList<Character> list = new LinkedList();list.add('a');list.add('b');list.add('c');list.add('d');//直接打印System.out.println(list);//foreach遍历for (Character c: list) {System.out.print(c+" ");}System.out.println();//for循环遍历for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();//迭代器遍历ListIterator<Character> it = list.listIterator();while (it.hasNext()) {System.out.print(it.next()+" ");}

LinkedList<Character> list = new LinkedList();list.add('a');list.add('b');list.add('c');list.add('d');//直接打印System.out.println(list);//foreach遍历for (Character c: list) {System.out.print(c+" ");}System.out.println();//for循环遍历for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();//迭代器正向遍历ListIterator<Character> it = list.listIterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();//迭代器反向遍历while (it.hasPrevious()) {System.out.print(it.previous()+" ");}

ArrayList和LinkedList的区别

不同点 ArrayList LinkedList
存储空间 物理上一定连续 逻辑上连续,物理上不一定连续
随机访问 O(1) O(N)
头插 需要移动元素,效率低O(N) 只需要改变引用的指向,O(1)
插入 空间不够需要扩容 没有扩容的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁

栈

概念

一种特殊的线性表,其只允许在固定的一段进行插入和删除元素操作.进行数据插入和删除操作的一段称为栈顶,另一端称为栈底,栈中的数据元素遵守后进先出的原则
压栈: 栈的插入操作叫作进栈/压栈/入栈,入数据在栈顶
出栈: 栈的删除操作叫作出栈.出数据在栈顶

栈的使用

方法 功能
Stack() 构造一个空的栈
E push(E e) 将e入栈，并返回e
E pop() 将栈顶元素出栈并返回
E peek() 获取栈顶元素
int size() 获取栈中有效元素个数
boolean empty() 检测栈是否为空

        Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);stack.push(3);stack.push(4);System.out.println(stack.size());int len = stack.size();for (int i = 0; i < len; i++) {System.out.print(stack.pop()+" ");}

栈的模拟实现

栈接口

public interface IStack {void push(int val);int pop();int peek();int size();boolean empty();boolean full();
}

栈实现
栈空的自定义异常

public class EmptyException extends RuntimeException{EmptyException(String s) {super(s);}
}

public class MyStack implements IStack{private int[] arr;private int usedSize;public static final int DEFAULT_CAPACITY = 10;MyStack() {arr = new int[DEFAULT_CAPACITY];}@Overridepublic void push(int val) {if(full()) {arr = Arrays.copyOf(arr,arr.length*2);}arr[usedSize++] = val;}@Overridepublic int pop() {if(empty()) {throw new EmptyException("栈空,无法出栈");}usedSize--;return arr[usedSize];}@Overridepublic int peek() {if(empty()) {throw new EmptyException("栈空,无法出栈");}return arr[usedSize-1];}@Overridepublic int size() {return 0;}@Overridepublic boolean full() {if(usedSize==arr.length) {return true;}return false;}@Overridepublic boolean empty() {return usedSize==0;}
}

概念区分

栈:数据结构的一种
虚拟机栈:JVM划分的一块内存而已
栈帧:调用方法的时候,会在虚拟机中给这个方法开辟一块内存

队列

概念

队列: 只允许在一段进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特点.入队列: 进行插入操作的一端叫队尾, 出队列: 进行删除操作的一端称为队头

队列使用

方法 功能
boolean offer(E e) 入队列
E poll() 出队列
peek() 获取队头元素
int size() 获取队列中有效元素个数
boolean isEmpty() 检测队列是否为空

注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口

        Queue<Integer> queue = new LinkedList<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);System.out.println(queue.peek());System.out.println(queue.poll());System.out.println(queue.poll());

队列模拟实现

public class MyLinkQueue {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//队头public ListNode tail;//队尾public int usedSize;
//入队列,在头节点处进行头插public boolean offer(int val) {ListNode node = new ListNode(val);if(head==null) {head = tail = node;} else {tail.next = node;node.prev = tail;tail = tail.next;}usedSize++;return true;}
//出队列--删除双向链表第一个节点public int poll() {//1.链表为空,返回自定义异常//2.队列中只有一个元素--链表中只有一个节点--直接删除//3.多个节点,删除第一个节点if(head==null) {throw new QueueNullException("队列为空");}int val = head.val;if(head.next==null) {head = null;tail = null;return val;}head = head.next;head.prev = null;usedSize--;return val;}//获取队头元素,获取链表中第一个节点的值public int peek() {if(head==null) {throw new QueueNullException("队列为空");}return head.val;}public boolean empty() {return head==null;}public int size() {return usedSize;}
}

循环队列

如何区分空与满:

1. 通过添加size属性记录
2. 保留一个位置
3. 使用标记

public class MyCircularQueue {private int[] elements;public int front;public int rear;private boolean flg;private int usedSize;public MyCircularQueue(int k) {elements = new int[k];}//入队public boolean enQueue(int value) {if(isFull()) {return false;}elements[rear] = value;rear = (rear+1)%elements.length;usedSize++;
//        flg = true;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elements.length;usedSize--;
/*        if(front==rear) {flg = false;}*/return true;}public int Front() {if(isEmpty()) {return -1;}return elements[front];}public int Rear() {if(isEmpty()) {return -1;}int index = (rear==0)?(elements.length-1):(rear-1);return elements[index];
/*        if(rear==0) {return elements[elements.length-1];} else {return elements[rear-1];}*/}public boolean isEmpty() {return front==rear&&usedSize==0;
//        return front==rear&&flg==false;}public boolean isFull() {return front==rear&&usedSize==elements.length-1;
//        return (rear+1)%elements.length==front;}
}

双端队列

双端队列指的是在队列两边都可以进行入队和出队的操作
deque是"double ended queue"的简称
元素可以从队头出队或入队,也可以在队尾出队和入队
Deque是一个接口,使用时必须创建LinkedList对象

		Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现Deque<Integer> queue  = new LinkedList<>();//双端队列的链式实现

用队列实现栈

队列是先进先出
栈是先进后出
用队列实现栈(leetcode原题)

使用两个队列实现
哪个栈不为空放在哪个栈,两个都为空,直到其中一个放进去
出栈的时候哪个不为空出哪个,直到size-1
当两个队列为空时,模拟的栈为空

class MyStack {private Queue<Integer> queue1;private Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {Queue existQueue;Queue emptyQueue;if (queue2.isEmpty()) {existQueue = queue1;emptyQueue = queue2;existQueue.offer(x);} else {existQueue = queue2;emptyQueue = queue1;existQueue.offer(x);}}public int pop() {Queue existQueue;Queue emptyQueue;if (queue2.isEmpty()) {existQueue = queue1;emptyQueue = queue2;} else {existQueue = queue2;emptyQueue = queue1;}if (existQueue.size() == 0) {return -1;}if (existQueue.size() == 1) {int ret = (int) existQueue.peek();existQueue.poll();return ret;}int size = existQueue.size();while (size > 1) {emptyQueue.offer(existQueue.peek());existQueue.poll();size--;}int ret = (int) existQueue.peek();existQueue.poll();return ret;}public int top() {Queue existQueue;Queue emptyQueue;if (queue2.isEmpty()) {existQueue = queue1;emptyQueue = queue2;} else {existQueue = queue2;emptyQueue = queue1;}if (existQueue.size() == 0) {return -1;}if (existQueue.size() == 1) {int ret = (int) existQueue.peek();return ret;}int size = existQueue.size();while (size > 1) {emptyQueue.offer(existQueue.peek());existQueue.poll();size--;}int ret = (int) existQueue.poll();emptyQueue.offer(ret);return ret;}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}

用栈实现队列

入队放到第一个栈里
出队都出第二个栈当中的元素,第二个栈没有元素,把第一个栈的元素倒进来
用栈实现队列题目

class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack();stack2 = new Stack();}public void push(int x) {stack1.push(x);}public int pop() {if(!stack2.isEmpty()) {return stack2.pop();} else if(stack2.isEmpty()&&!stack1.isEmpty()) {int ret = -1;int size = stack1.size();for (int i = 0; i < size; i++) {ret = stack1.pop();stack2.push(ret);}return stack2.pop();} else {return -1;}}public int peek() {if(!stack2.isEmpty()) {return stack2.peek();} else if(stack2.isEmpty()&&!stack1.isEmpty()) {int ret = -1;int size = stack1.size();for (int i = 0; i < size; i++) {ret = stack1.pop();stack2.push(ret);}return ret;} else {return -1;}}public boolean empty() {return stack1.isEmpty()&&stack2.isEmpty();}
}