首页 > > 程序设计 > Java技术 >

LinkedList集合实现栈和队列

2018-07-19 05:38:08来源：博客园阅读 ()

LinkedList集合的底层是链表结构实现的，所以可以模拟栈（先进后出）和队列（先进先出）。

方法：

　　　　addFirst()　　　　//添加元素到列表的起始位置

　　　　addLast()　　　　//添加元素到列表的结束位置

　　　　removeFirst()　　//移除列表起始位置的元素

　　　　removeLast()　　//移除列表结束位置的元素

　　　　getFirst()　　　　//获取列表起始位置的元素

　　　　getLast()　　　　//获取列表结束位置的元素

User类

 1 package queue;
 2 
 3 public class User {
 4 
 5     private int id;
 6     private String account;
 7     private String password;
 8     private String name;
 9 
10     public int getId() {
11         return id;
12     }
13 
14     public void setId(int id) {
15         this.id = id;
16     }
17 
18     public String getAccount() {
19         return account;
20     }
21 
22     public void setAccount(String account) {
23         this.account = account;
24     }
25 
26     public String getPassword() {
27         return password;
28     }
29 
30     public void setPassword(String password) {
31         this.password = password;
32     }
33 
34     public String getName() {
35         return name;
36     }
37 
38     public void setName(String name) {
39         this.name = name;
40     }
41 
42     public User() {
43         super();
44     }
45 
46     public User(int id, String account, String password, String name) {
47         super();
48         this.id = id;
49         this.account = account;
50         this.password = password;
51         this.name = name;
52     }
53 
54     @Override
55     public String toString() {
56         return "User [id=" + id + ", account=" + account + ", password=" + password + ", name=" + name + "]";
57     }
58 
59 }

构造队列的方法类

 1 package queue;
 2 
 3 import java.util.LinkedList;
 4 
 5 /**
 6  * LinkedList模拟队列，先进先出
 7  * 
 8  * @author WJY
 9  *
10  */
11 public class Queue<T> {
12 
13     private LinkedList<T> linkedList = new LinkedList<T>();
14 
15     /**
16      * 进队
17      * 
18      * @param t
19      *            进队的元素
20      */
21     public void enQueue(T t) {
22         linkedList.addLast(t);
23     }
24 
25     /**
26      * 出队
27      * 
28      * @return 出队的元素
29      */
30     public T deQueue() {
31         return linkedList.removeFirst();
32     }
33 
34     /**
35      * 销毁队列
36      */
37     public void destroyQueue() {
38         linkedList.clear();
39     }
40 
41     /**
42      * 查看队首元素
43      * 
44      * @return 队首的元素
45      */
46     public T queueFirst() {
47         return linkedList.getFirst();
48     }
49 
50     /**
51      * 查看队尾元素
52      * 
53      * @return 队尾的元素
54      */
55     public T queueLast() {
56         return linkedList.getLast();
57     }
58 
59     /**
60      * 查看队列长度
61      * 
62      * @return 队列的长度
63      */
64     public int queueLength() {
65         return linkedList.size();
66     }
67 
68     /**
69      * 判断队列是否为空
70      * 
71      * @return 队列为空 true 队列不为空 false
72      */
73     public boolean isEmpty() {
74         return linkedList.isEmpty();
75     }
76 
77     /**
78      * 打印队列
79      */
80     public String toString() {
81         return linkedList.toString();
82     }
83 
84 }

测试队列类

 1 package queue;
 2 
 3 import list.User;
 4 
 5 public class Test {
 6 
 7     public static void main(String[] args) {
 8 
 9         User user1 = new User(1, "账号1", "密码1", "姓名1");
10         User user2 = new User(2, "账号2", "密码2", "姓名2");
11         User user3 = new User(3, "账号3", "密码3", "姓名3");
12         User user4 = new User(4, "账号4", "密码4", "姓名4");
13         User user5 = new User(5, "账号5", "密码5", "姓名5");
14 
15         Queue<User> queue = new Queue<User>();
16 
17         queue.enQueue(user1);
18         queue.enQueue(user2);
19         queue.enQueue(user3);
20         queue.enQueue(user4);
21         queue.enQueue(user5);// 进队
22 
23         System.out.println("队首元素：" + queue.queueFirst());
24         System.out.println("队尾元素：" + queue.queueLast());
25         System.out.println("队列长度：" + queue.queueLength());
26         System.out.println("队列是否为空：" + queue.isEmpty());
27         System.out.println(queue.toString());// 打印队列
28 
29         queue.deQueue();
30         queue.deQueue();
31         queue.deQueue();// 出队
32 
33         System.out.println("队首元素：" + queue.queueFirst());
34         System.out.println("队尾元素：" + queue.queueLast());
35         System.out.println("队列长度：" + queue.queueLength());
36         System.out.println("队列是否为空：" + queue.isEmpty());
37         System.out.println(queue.toString());// 打印队列
38 
39         queue.destroyQueue();// 销毁队列
40 
41         System.out.println("队列长度：" + queue.queueLength());
42         System.out.println("队列是否为空：" + queue.isEmpty());
43         System.out.println(queue.toString());// 打印队列
44 
45     }
46 
47 }

测试结果：

队首元素：User [id=1, account=账号1, password=密码1, name=姓名1]
队尾元素：User [id=5, account=账号5, password=密码5, name=姓名5]
队列长度：5
队列是否为空：false
[User [id=1, account=账号1, password=密码1, name=姓名1], User [id=2, account=账号2, password=密码2, name=姓名2], User [id=3, account=账号3, password=密码3, name=姓名3], User [id=4, account=账号4, password=密码4, name=姓名4], User [id=5, account=账号5, password=密码5, name=姓名5]]
队首元素：User [id=4, account=账号4, password=密码4, name=姓名4]
队尾元素：User [id=5, account=账号5, password=密码5, name=姓名5]
队列长度：2
队列是否为空：false
[User [id=4, account=账号4, password=密码4, name=姓名4], User [id=5, account=账号5, password=密码5, name=姓名5]]
队列长度：0
队列是否为空：true
[]

User类

 1 package stack;
 2 
 3 public class User {
 4 
 5     private int id;
 6     private String account;
 7     private String password;
 8     private String name;
 9 
10     public int getId() {
11         return id;
12     }
13 
14     public void setId(int id) {
15         this.id = id;
16     }
17 
18     public String getAccount() {
19         return account;
20     }
21 
22     public void setAccount(String account) {
23         this.account = account;
24     }
25 
26     public String getPassword() {
27         return password;
28     }
29 
30     public void setPassword(String password) {
31         this.password = password;
32     }
33 
34     public String getName() {
35         return name;
36     }
37 
38     public void setName(String name) {
39         this.name = name;
40     }
41 
42     public User() {
43         super();
44     }
45 
46     public User(int id, String account, String password, String name) {
47         super();
48         this.id = id;
49         this.account = account;
50         this.password = password;
51         this.name = name;
52     }
53 
54     @Override
55     public String toString() {
56         return "User [id=" + id + ", account=" + account + ", password=" + password + ", name=" + name + "]";
57     }
58 
59 }

构造栈的方法类

 1 package stack;
 2 
 3 import java.util.LinkedList;
 4 
 5 /**
 6  * LinkedList模拟栈，先进后出
 7  * 
 8  * @author WJY
 9  *
10  */
11 public class Stack<T> {
12 
13     private LinkedList<T> linkedList = new LinkedList<T>();
14 
15     /**
16      * 进栈
17      * 
18      * @param t
19      *            进栈的元素
20      */
21     public void push(T t) {
22         linkedList.addFirst(t);
23     }
24 
25     /**
26      * 出栈
27      * 
28      * @return 出栈的元素
29      */
30     public T pop() {
31         return linkedList.removeFirst();
32     }
33 
34     /**
35      * 销毁栈
36      */
37     public void destroyStack() {
38         linkedList.clear();
39     }
40 
41     /**
42      * 查看栈顶元素
43      * 
44      * @return 栈顶的元素
45      */
46     public T stackFirst() {
47         return linkedList.getFirst();
48     }
49 
50     /**
51      * 查看栈底元素
52      * 
53      * @return 栈底的元素
54      */
55     public T stackLast() {
56         return linkedList.getLast();
57     }
58 
59     /**
60      * 查看栈长度
61      * 
62      * @return 栈的长度
63      */
64     public int stackLength() {
65         return linkedList.size();
66     }
67 
68     /**
69      * 判断栈是否为空
70      * 
71      * @return 栈为空 true 栈不为空 false
72      */
73     public boolean isEmpty() {
74         return linkedList.isEmpty();
75     }
76 
77     /**
78      * 打印栈
79      */
80     public String toString() {
81         return linkedList.toString();
82     }
83 
84 }

测试栈类

 1 package stack;
 2 
 3 import list.User;
 4 
 5 public class Test {
 6 
 7     public static void main(String[] args) {
 8 
 9         User user1 = new User(1, "账号1", "密码1", "姓名1");
10         User user2 = new User(2, "账号2", "密码2", "姓名2");
11         User user3 = new User(3, "账号3", "密码3", "姓名3");
12         User user4 = new User(4, "账号4", "密码4", "姓名4");
13         User user5 = new User(5, "账号5", "密码5", "姓名5");
14 
15         Stack<User> stack = new Stack<User>();
16 
17         stack.push(user1);
18         stack.push(user2);
19         stack.push(user3);
20         stack.push(user4);
21         stack.push(user5);// 进栈
22 
23         System.out.println("栈顶元素：" + stack.stackFirst());
24         System.out.println("栈底元素：" + stack.stackLast());
25         System.out.println("栈长度：" + stack.stackLength());
26         System.out.println("栈是否为空：" + stack.isEmpty());
27         System.out.println(stack.toString());// 打印栈
28 
29         stack.pop();
30         stack.pop();
31         stack.pop();// 出栈
32 
33         System.out.println("栈顶元素：" + stack.stackFirst());
34         System.out.println("栈底元素：" + stack.stackLast());
35         System.out.println("栈长度：" + stack.stackLength());
36         System.out.println("栈是否为空：" + stack.isEmpty());
37         System.out.println(stack.toString());// 打印栈
38 
39         stack.destroyStack();// 销毁栈
40 
41         System.out.println("栈长度：" + stack.stackLength());
42         System.out.println("栈是否为空：" + stack.isEmpty());
43         System.out.println(stack.toString());// 打印栈
44 
45     }
46 
47 }

测试结果：

栈顶元素：User [id=5, account=账号5, password=密码5, name=姓名5]
栈底元素：User [id=1, account=账号1, password=密码1, name=姓名1]
栈长度：5
栈是否为空：false
[User [id=5, account=账号5, password=密码5, name=姓名5], User [id=4, account=账号4, password=密码4, name=姓名4], User [id=3, account=账号3, password=密码3, name=姓名3], User [id=2, account=账号2, password=密码2, name=姓名2], User [id=1, account=账号1, password=密码1, name=姓名1]]
栈顶元素：User [id=2, account=账号2, password=密码2, name=姓名2]
栈底元素：User [id=1, account=账号1, password=密码1, name=姓名1]
栈长度：2
栈是否为空：false
[User [id=2, account=账号2, password=密码2, name=姓名2], User [id=1, account=账号1, password=密码1, name=姓名1]]
栈长度：0
栈是否为空：true
[]

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有