java备忘录-集合之栈和队列

字数统计: 1.7k   |   阅读时长≈ 7 分钟

栈Stack

栈是Vector的一个子类，它实现了一个标准的后进先出的栈。堆栈只定义了默认构造函数，用来创建一个空栈。 堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。

1
2
3
4
5
boolean empty()  //判断栈是否为空
Object peek()    //查看堆栈顶部的对象，但不从堆栈中移除它。
Object pop()     //移除堆栈顶部的对象，并作为此函数的值返回该对象。
Object push(E element) //把项压入堆栈顶部。
int search(Object element)  //返回对象在堆栈中的位置，以 1 为基数。

下面的代码演示了栈的基本用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args)
{
     Stack<String> stack = new Stack<String>();

     stack.push("a");
     stack.push("b");
     stack.push("c");
     stack.push("d");
     System.out.println("stack中栈顶的元素: "+ stack.peek());
     System.out.println("stack中b的元素索引: "+ stack.search("b")); 
     while(!stack.empty()){
         System.out.print( stack.pop() + "   " );
     }
 }

输出结果为

1
2
3
stack中栈顶的元素: d
stack中b的元素索引: 3
d   c   b   a

队列 Queue

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
Queue的主要方法如下

1
2
3
4
5
6
7
8
boolean add(Object element)    //向队的末尾添加元素，如果队列已满，会抛出异常
boolean offer(Object element)  //相队的末尾添加元素，如果队列已满，返回false，推荐使用

Object remove()                //删除并返回队列头部的元素，如果队列为空抛出异常 
Object poll()                  //删除并返回队列头部的元素，如果队列为空返回null，推荐使用

Object element()               //返回队列头部的元素，如果队列为空抛出异常
Object peek()                  //返回队列头部的元素，如果队列为空返回null，推荐使用

一般队列 Queue

一般队列的示例代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void main(String[] args)
{
	Queue<String> queueList = new LinkedList<>();
    //使用offer方法
    queueList.offer("a");
    queueList.offer("b");
    queueList.offer("c");
    queueList.offer("d");
    System.out.println("queueList peek 栈顶元素: " + queueList.peek());
    while(!queueList.isEmpty())
    {
        System.out.print( queueList.poll() + "   " );
    }
    System.out.println( "\n队列为空 poll " + queueList.poll());
    System.out.println( "队列为空 peek " + queueList.peek());
    //使用add方法
    queueList.add("a");
    queueList.add("b");
    queueList.add("c");
    queueList.add("d");
    System.out.println("queueList element 栈顶元素: " + queueList.element());
    while(!queueList.isEmpty())
    {
        System.out.print( queueList.remove() + "   " );
    }
    try {
        System.out.println( "\n队列为空 remove " + queueList.remove());
    }catch(NoSuchElementException e){
        System.out.print("\n队列为空 remove  捕获异常   " );
    }
    try {
        System.out.println( "\n队列为空 element " + queueList.element());
    }catch(NoSuchElementException e){
        System.out.print("\n队列为空 element 捕获异常   " );
    }
}

输出结果为

1
2
3
4
5
6
7
8
queueList peek 栈顶元素: a
a   b   c   d   
队列为空 poll null
队列为空 peek null
queueList element 栈顶元素: a
a   b   c   d   
队列为空 remove  捕获异常   
队列为空 element 捕获异常

双向队列 Deque

Queue接口是单向队列，它有一个子接口Deque，表示双向队列。双向队列的特点是在队列的头部和尾部都可以添加或删除元素。它可以使用new ArrayDeque<>()来初始化，同时LinkedList实现了它的接口，也可使用new LinkedList<>()来初始化。
主要方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//向队列的头部或者尾部添加元素，如果队列已满会抛出异常
void addFirst(Object element)        
void addLast(Object element)    

//向队列的头部或者尾部添加元素，如果队列已满返回false
boolean offerFirst(Object element)   
boolean offerLast(Object element)   

//从头部或尾部删除元素，如果队列为空抛出异常
Object removeFirst()
Object removeLast()

//从头部或尾部删除元素，如果队列为空返回nul
Object pollFirst()
Object pollLast()

//从队列头部或者尾部获取元素，如果队列为空抛出异常
Object getFirst()
Object getLast()

//从队列头部或者尾部获取元素，如果队列为空返回null
Object peekFirst()
Object peekLast()

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args)
{
	Deque<String> deque = new ArrayDeque<String>();

    deque.offer("b");
    deque.offerFirst("a");
    deque.offerLast("c");
    deque.offer("d");

    System.out.println("遍历双向队列 " );
    for(String atr : deque)
    {
        System.out.print(atr + "   " );
    }
}

输出结果

1
2
遍历双向队列 
a   b   c   d

优先级队列 PriorityQueue

优先级队列会按照排序的方式对队列中的元素进行排序和检索。因此加入到PriorityQueue中的对象必须实现Comparable接口，提供对元素排序时两个元素之间的比较规则。
示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args)
{
	Queue<String> priorityQueue = new PriorityQueue<String>();
    priorityQueue.add("c");
    priorityQueue.add("a");
    priorityQueue.add("d");
    priorityQueue.add("b");

    System.out.println("遍历优先级队列 " );
    for(String atr : priorityQueue)
    {
        System.out.print(atr + "   " );
    }
    System.out.println("\n依次删除优先级队列中的元素");
    while(!priorityQueue.isEmpty())
    {
        System.out.print(priorityQueue.poll() + "   " );
    }
}

注意的是，用foreach语句遍历优先级队列时，获得元素并没有排序，而在通过poll()或者remove()方法删除元素时，该方法总会删除当前队列中最小的元素。
以上代码输出结果为

1
2
3
4
遍历优先级队列 
a   b   d   c   
依次删除优先级队列中的元素
a   b   c   d

LinkedList

LinkedList在实现中采用了链表的数据结构，对顺序访问进行了优化，向Lsit中插入和删除元素的速度较快，随机访问则相对较慢。而且LinkedList实现了实现了较多的接口，它可以作为栈、队列和双向队列使用。
示例代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void main(String[] args)
{
	LinkedList<String> linkList = new LinkedList<>();
    System.out.println("linkList stack: ");

    linkList.push("a");
    linkList.push("b");
    linkList.push("c");
    linkList.push("d");
    while(!linkList.isEmpty())
    {
        System.out.print( linkList.pop() + "   " );
    }

    System.out.println();
    System.out.println("linkList queue offer方法: ");
    linkList.offer("a");
    linkList.offer("b");
    linkList.offer("c");
    linkList.offer("d");
    while(!linkList.isEmpty())
    {
        System.out.print( linkList.poll() + "   " );
    }

    System.out.println();
    System.out.println("linkList queue add方法: ");
    linkList.add("a");
    linkList.add("b");
    linkList.add("c");
    linkList.add("d");
    while(!linkList.isEmpty())
    {
        System.out.print( linkList.remove() + "   " );
    }
}

输出结果如下

1
2
3
4
5
6
linkList stack: 
d   c   b   a   
linkList queue offer方法: 
a   b   c   d   
linkList queue add方法: 
a   b   c   d
打赏

请我喝杯咖啡吧~

支付宝
微信