图灵之旅--ArrayList&顺序表&LinkedList&链表&&栈&&Stack&&队列&&Queue

目录

线性表

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

顺序表

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

publicclassListimplementsMyArrayList{privateint[] elements;privateint usedSize;//顺序表的默认大小privatestaticfinalint DEFAULT_SIZE =2;publicList(){this.elements =newint[DEFAULT_SIZE];}publicList(int capacity){this.elements =newint[capacity];}@Overridepublicvoiddisplay(){for(int i =0; i <this.usedSize; i++){System.out.print(this.elements[i]+" ");}System.out.println();}@OverridepublicbooleanisFull(){/*if(this.usedSize==this.elements.length) {
            return true;
        }
        return false;*/returnthis.elements.length==usedSize;}privatevoidisEnlarger(){if(isFull()){
            elements =Arrays.copyOf(elements,elements.length*2);}}@Overridepublicvoidadd(int data){isEnlarger();this.elements[this.usedSize]= data;this.usedSize++;}@Overridepublicvoidadd(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++;}privatevoidcheckPos(int pos)throwsPosIllegal{if(pos<0||pos>usedSize){thrownewPosIllegal("插入下标异常: "+pos);}}@Overridepublicbooleancontains(int toFind){if(isEmpty()){returnfalse;}for(int i =0; i < usedSize; i++){//查找引用类型,要重写方法if(toFind==elements[i]){returntrue;}}returnfalse;}@OverridepublicbooleanisEmpty(){return usedSize==0;}@OverridepublicintindexOf(int toFind){if(isEmpty()){return-1;}for(int i =0; i < usedSize; i++){//查找引用类型,要重写方法if(toFind==elements[i]){return i;}}return-1;}@Overridepublicintget(int pos){try{checkPosOnGet(pos);}catch(PosIllegal e){
            e.printStackTrace();}return elements[pos];}privatevoidcheckPosOnGet(int pos)throwsPosIllegal{if(pos<0||pos>=usedSize){thrownewPosIllegal("获取指定下标异常: "+pos);}}@Overridepublicvoidset(int pos,int value){try{checkPosOnGet(pos);}catch(PosIllegal e){
            e.printStackTrace();return;}
        elements[pos]= value;}@Overridepublicvoidremove(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--;}@Overridepublicintsize(){return usedSize;}@Overridepublicvoidclear(){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 =newArrayList<>();//你当前传入的arraylist里面的元素一定是ArrayList<Integer> arrayList1中Integer的子类ArrayList<Integer> arrayList1 =newArrayList<>(arrayList);

换个栗子

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

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

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

publicstaticvoidmain(String[] args){ArrayList<Integer> arrayList =newArrayList<>();
        arrayList.add(1);
        arrayList.add(1);
        arrayList.add(1);
        arrayList.add(1);ArrayList<Number> arrayList1 =newArrayList<>(arrayList);
        arrayList1.add(2);
        arrayList1.add(2);
        arrayList1.add(2);System.out.println(arrayList1);}

ArrayList常见操作

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

publicstaticvoidmain(String[] args){ArrayList<Integer> list =newArrayList<>();
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(1);ArrayList<Number> list1 =newArrayList<>();
        list1.addAll(list);System.out.println(list1);}

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

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

publicstaticvoidmain(String[] args){ArrayList<Integer> list =newArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.remove(newInteger(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 =newArrayList<>();
        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 =newArrayList<>();
        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洗牌

卡包

packagecard;publicclassCard{privateString color;//花色privateint number;//数字publicStringgetColor(){return color;}publicCard(String color,int number){this.color = color;this.number = number;}publicvoidsetColor(String color){this.color = color;}publicintgetNumber(){return number;}publicvoidsetNumber(int number){this.number = number;}@OverridepublicStringtoString(){return color+":"+number;}}

操作包

packagecard;importjava.util.ArrayList;importjava.util.List;importjava.util.Random;publicclassCardDemo{privateString[] suits ={"♥","♠","♦","♣"};publicList<Card>buyCard(){List<Card> list =newArrayList<>();//创建一副新牌for(int i =0; i <4; i++){for(int j =1; j <=13; j++){Card card =newCard(suits[i], j);
                list.add(card);}}return list;}publicvoiddislocate(List<Card> cardList){Random random =newRandom();//从后往前开始进行互换,打乱牌面for(int i = cardList.size()-1; i >0; i--){int rand = random.nextInt(i);swap(cardList,i,rand);}}publicstaticvoidswap(List<Card> cardList,int x,int y){//交换牌Card tmp = cardList.get(x);
        cardList.set(x,cardList.get(y));
        cardList.set(y,tmp);}publicvoidInauguration(List<Card> cardList){List<List<Card>> roles =newArrayList<>();//三个人的牌建立顺序表储存List<Card> role1 =newArrayList<>();List<Card> role2 =newArrayList<>();List<Card> role3 =newArrayList<>();
        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);}}

测试包

packagecard;importjava.util.List;publicclassTest{publicstaticvoidmain(String[] args){CardDemo cardDemo =newCardDemo();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)

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

链表

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

链表的实现

链表接口

packageDemo01;publicinterfaceIlist{//头插法voidaddFirst(int data);//尾插法voidaddLast(int data);//任意位置插入,第一个数据节点为0号下标voidaddIndex(int index,int data);//查找是否包含关键字key是否在单链表当中booleancontains(int key);//删除第一次出现关键字为key的节点publicvoidremove(int key);//删除所有值为key的节点voidremoveAllKey(int key);//得到单链表的长度intsize();voidclear();voiddisplay();}

链表实现

packageDemo01;importorg.omg.CORBA.CODESET_INCOMPATIBLE;importjava.util.List;publicclassMyListimplementsIlist{staticclassListNode{publicint val;publicListNode next;publicListNode(int val){this.val = val;}}publicListNode head;@OverridepublicvoidaddFirst(int data){ListNode newNode =newListNode(data);
        newNode.next = head;
        head = newNode;}@OverridepublicvoidaddLast(int data){ListNode newNode =newListNode(data);if(head==null){
            head = newNode;}else{ListNode curNode = head;while(curNode.next!=null){
                curNode = curNode.next;}
            curNode.next = newNode;}}@OverridepublicvoidaddIndex(int index,int data){ListNode newNode =newListNode(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;}}@Overridepublicbooleancontains(int key){ListNode cur = head;while(cur!=null){if(cur.val==key){returntrue;}
            cur = cur.next;}returnfalse;}@Overridepublicvoidremove(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;}}@OverridepublicvoidremoveAllKey(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;}}}}@Overridepublicintsize(){int count =0;ListNode cur = head;while(cur!=null){
            count++;
            cur = cur.next;}return count;}@Overridepublicvoidclear(){if(head!=null){while(head!=null){ListNode tmp = head.next;
                head =null;
                head = tmp;}}}@Overridepublicvoiddisplay(){ListNode cur = head;while(cur!=null){System.out.print(cur.val+" ");
            cur = cur.next;}System.out.println();}}

双向链表的实现

双向链表的实现

publicclassMyLinkedListimplementsIlist{//双向链表的节点staticclassListNode{//后继publicListNode next;//前驱publicListNode prev;publicint val;publicListNode(int val){this.val = val;}}publicListNode head;publicListNode last;//头插法@OverridepublicvoidaddFirst(int data){ListNode newNode =newListNode(data);if(head!=null){
            head.prev = newNode;
            newNode.next = head;
            head = newNode;}else{
            head = last = newNode;}}//尾插法@OverridepublicvoidaddLast(int data){ListNode newNode =newListNode(data);if(head==null){
            head = last = newNode;}else{
            last.next = newNode;
            newNode.prev = last;
            last = newNode;}}@OverridepublicvoidaddIndex(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 =newListNode(data);while(count!=index){
            curNode = curNode.next;
            count++;}
        node.prev = curNode.prev;
        node.next = curNode;
        curNode.prev.next = node;
        node.next.prev = node;}//是否包含某个值@Overridepublicbooleancontains(int key){ListNode curNode = head;while(curNode!=null){if(curNode.val==key){returntrue;}
            curNode = curNode.next;}returnfalse;}//删除某值@Overridepublicvoidremove(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;}}//删除所有该值@OverridepublicvoidremoveAllKey(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;}}//得到链表长度@Overridepublicintsize(){int count =0;ListNode curNode = head;while(curNode!=null){
            count++;
            curNode = curNode.next;}return count;}@Overridepublicvoidclear(){ListNode cur = head;while(cur!=null){ListNode tmp = cur.next;
            cur.prev =null;
            cur.next =null;
            cur = tmp;}
        head =null;
        last =null;}//打印链表@Overridepublicvoiddisplay(){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

publicstaticvoidmain(String[] args){List<Integer> list =newLinkedList<>();List<Double> list1 =newLinkedList<>();
        list1.add(1.1);
        list1.add(2.1);List<Number> list2 =newLinkedList<>(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 位置

publicstaticvoidmain(String[] args){LinkedList<Integer> list =newLinkedList<>();
        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 =newLinkedList<>();
        list.add(1);
        list.add(0,6);LinkedList<Number> list1 =newLinkedList<>();
        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 =newLinkedList();
        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 =newLinkedList();
        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 =newStack<>();
        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()+" ");}

栈的模拟实现

栈接口

publicinterfaceIStack{voidpush(int val);intpop();intpeek();intsize();booleanempty();booleanfull();}

栈实现
栈空的自定义异常

publicclassEmptyExceptionextendsRuntimeException{EmptyException(String s){super(s);}}

publicclassMyStackimplementsIStack{privateint[] arr;privateint usedSize;publicstaticfinalint DEFAULT_CAPACITY =10;MyStack(){
        arr =newint[DEFAULT_CAPACITY];}@Overridepublicvoidpush(int val){if(full()){
            arr =Arrays.copyOf(arr,arr.length*2);}
        arr[usedSize++]= val;}@Overridepublicintpop(){if(empty()){thrownewEmptyException("栈空,无法出栈");}
        usedSize--;return arr[usedSize];}@Overridepublicintpeek(){if(empty()){thrownewEmptyException("栈空,无法出栈");}return arr[usedSize-1];}@Overridepublicintsize(){return0;}@Overridepublicbooleanfull(){if(usedSize==arr.length){returntrue;}returnfalse;}@Overridepublicbooleanempty(){return usedSize==0;}}

概念区分

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

队列

概念

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

队列使用

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

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

Queue<Integer> queue =newLinkedList<>();
        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());

队列模拟实现

publicclassMyLinkQueue{staticclassListNode{publicint val;publicListNode prev;publicListNode next;publicListNode(int val){this.val = val;}}publicListNode head;//队头publicListNode tail;//队尾publicint usedSize;//入队列,在头节点处进行头插publicbooleanoffer(int val){ListNode node =newListNode(val);if(head==null){
                head = tail = node;}else{
                tail.next = node;
                node.prev = tail;
                tail = tail.next;}
            usedSize++;returntrue;}//出队列--删除双向链表第一个节点publicintpoll(){//1.链表为空,返回自定义异常//2.队列中只有一个元素--链表中只有一个节点--直接删除//3.多个节点,删除第一个节点if(head==null){thrownewQueueNullException("队列为空");}int val = head.val;if(head.next==null){
                head =null;
                tail =null;return val;}
            head = head.next;
            head.prev =null;
            usedSize--;return val;}//获取队头元素,获取链表中第一个节点的值publicintpeek(){if(head==null){thrownewQueueNullException("队列为空");}return head.val;}publicbooleanempty(){return head==null;}publicintsize(){return usedSize;}}

循环队列

如何区分空与满:

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

publicclassMyCircularQueue{privateint[] elements;publicint front;publicint rear;privateboolean flg;privateint usedSize;publicMyCircularQueue(int k){
        elements =newint[k];}//入队publicbooleanenQueue(int value){if(isFull()){returnfalse;}
        elements[rear]= value;
        rear =(rear+1)%elements.length;
        usedSize++;//        flg = true;returntrue;}publicbooleandeQueue(){if(isEmpty()){returnfalse;}
        front =(front+1)%elements.length;
        usedSize--;/*        if(front==rear) {
            flg = false;
        }*/returntrue;}publicintFront(){if(isEmpty()){return-1;}return elements[front];}publicintRear(){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];
        }*/}publicbooleanisEmpty(){return front==rear&&usedSize==0;//        return front==rear&&flg==false;}publicbooleanisFull(){return front==rear&&usedSize==elements.length-1;//        return (rear+1)%elements.length==front;}}

双端队列

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

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

用队列实现栈

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

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

classMyStack{privateQueue<Integer> queue1;privateQueue<Integer> queue2;publicMyStack(){
        queue1 =newLinkedList<>();
        queue2 =newLinkedList<>();}publicvoidpush(int x){Queue existQueue;Queue emptyQueue;if(queue2.isEmpty()){
            existQueue = queue1;
            emptyQueue = queue2;
            existQueue.offer(x);}else{
            existQueue = queue2;
            emptyQueue = queue1;
            existQueue.offer(x);}}publicintpop(){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;}publicinttop(){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;}publicbooleanempty(){return queue1.isEmpty()&& queue2.isEmpty();}}

用栈实现队列

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

classMyQueue{privateStack<Integer> stack1;privateStack<Integer> stack2;publicMyQueue(){
        stack1 =newStack();
        stack2 =newStack();}publicvoidpush(int x){
        stack1.push(x);}publicintpop(){if(!stack2.isEmpty()){return stack2.pop();}elseif(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;}}publicintpeek(){if(!stack2.isEmpty()){return stack2.peek();}elseif(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;}}publicbooleanempty(){return stack1.isEmpty()&&stack2.isEmpty();}}