疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

两种特殊的数据结构:队列和栈


 

   

  一、队列

  队列(Queue:本文要介绍的第一种数据结构):只能从线性表的一端添加(offer)元素,从另一端取出(poll)元素,并遵循FIFO(先进先出)

  选择LinkedList来实现Queue接口,因为LinkedList在插入删除的操作方面效率较高

  相关操作:

  boolean offer(E e):将元素追加到队列末尾

  E poll():删除并返回队首元素

  E peek():仅返回队首元素,不删除

  实例编程:

  复制代码

  1 package Java20170331;

  2

  3 import java.util.LinkedList;

  4 import java.util.Queue;

  5

  6 public class BlogDemo {

  7 public static void main(String[] args) {

  8 /**

  9 * Queue

  10 * boolean offer(E e) 添加元素,放在队列末尾

  11 * E poll() 提取并删除队列首位元素

  12 * E peek() 提取队列首位元素,不删除

  13 */

  14 Queue queue = new LinkedList();

  15 queue.offer("one");

  16 queue.offer("two");

  17 queue.offer("three");

  18 queue.offer("four");

  19 System.out.println("原队列为:"+queue);

  20 queue.offer("1");

  21 System.out.println("添加1后为:"+queue);

  22 String str = queue.poll();

  23 System.out.println("提取的元素为:"+str);

  24 System.out.println("poll操作后的队列为:"+queue);

  25 String str1 = queue.peek();

  26 System.out.println("提取的元素为:"+str1);

  27 System.out.println("peek操作后的队列为:"+queue);

  28 while(queue.size()>0){

  29 str = queue.poll();

  30 System.out.println(str);

  31 }

  32 System.out.println(queue);

  33 }

  34 }

  复制代码

  复制代码

  运行结果为:

  原队列为:[one, two, three, four]

  添加1后为:[one, two, three, four, 1]

  提取的元素为:one

  poll操作后的队列为:[two, three, four, 1]

  提取的元素为:two

  peek操作后的队列为:[two, three, four, 1]

  two

  three

  four

  1

  []

  复制代码

  二、栈

  (双端队列)Deque是Queue的子接口,可以从队列的两端入队和出队,同样的用LinkedList来实现

  若将Deque限制为只能从一端入队和出队,即为栈(Stack:本文要介绍的第二种数据结构),入栈(push),出栈(pop),遵循FILO(先进后出)

  相关操作:

  void push(E e):元素入栈,放在栈首

  E pop():删除并返回栈首元素

  E peek():仅返回栈首元素,不删除 (同队列)

  复制代码

  package Java20170331;

  import java.util.Deque;

  import java.util.LinkedList;

  public class BlogDemo {

  public static void main(String[] args) {

  /**

  * Deque->Stack

  * void push(E e) :添加元素,放在栈首

  * E pop() : 删除并返回栈首元素

  * E peek() :返回栈首元素,不删除(和队列的一样)

  */

  // 查API,Stack也是一个类,根据API,不选用Stack类来创建栈的原因在于:

  // Deque 接口及其实现提供了 LIFO 堆栈操作的更完整和更一致的 set

  Deque stack = new LinkedList();

  stack.push("one");

  stack.push("two");

  stack.push("three");

  stack.push("four");

  System.out.println("原栈为:"+stack);

  String str1 = stack.pop();

  System.out.println("pop()操作提取的元素为:"+str1);

  System.out.println("pop()操作后的栈为:"+stack);

  String str2 = stack.peek();

  System.out.println("peek()操作提取的元素为:"+str2);

  System.out.println("peek()操作后的栈为:"+stack);

  }

  }

  复制代码

  复制代码

  运行结果为:

  原栈为:[four, three, two, one]

  pop()操作提取的元素为:four

  pop()操作后的栈为:[three, two, one]

  peek()操作提取的元素为:three

  peek()操作后的栈为:[three, two, one]

  复制代码

  Hello,Java!