java-集合(4)-用LinkedList来实现栈/队列-ArrayList和LinkedList比较

1:栈(Stack)也是一种特殊的线性表，是一种后进先出(LIFO)的结构。
2:栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)。

package stack;

import java.util.LinkedList;

class stack {
public static LinkedList<Object> ll = new LinkedList<Object>();
//入栈
public void push(Object o) {
        ll.add(o);
    }
//出栈
public Object pop() {
return ll.remove();
    }
//查看栈顶元素
public Object peek() {
return ll.getFirst();
    }
//判断栈是否为空
public boolean isEmpty(){
return ll.isEmpty();
    }
public static void main(String args[]) {
        stack s = new stack();
        s.push("1");
        s.push("2");
        s.push("3");
        s.pop();
        System.out.println(s.peek());
        System.out.println(s.peek());
        s.pop();
        s.pop();
        System.out.println(s.isEmpty());
    }
}

2
2
true

队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。
表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。按先进先出(FIFO)的原则进行的。

package queue;

import java.util.LinkedList;

class Queue {
    LinkedList<Object> ll = new LinkedList<Object>();

// 入队
public void push(Object o) {
        ll.addLast(o);
    }

// 出队
public Object pop() {
return ll.removeFirst();
    }

public Object peek() {
return ll.getFirst();
    }

public boolean isEmpty() {
return ll.isEmpty();
    }

public static void main(String args[]) {
        Queue q = new Queue();
        q.push("xiaoxi");
        q.push("xiaozhu");
        q.push("xiaohong");
        q.pop();
        System.out.println(q.peek());
        System.out.println(q.isEmpty());

    }
}

xiaozhu
false

1：ArrayList底层采用数组完成，而LinkedList则是以一般的双向链表(double-linked list)完成，其内每个对象除了数据本身外，还有两个 引用，分别指向前一个元素和后一个元素。

2：如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。