首页 > 代码库 > 使用LinkedList实现Stack（栈）与Queue（队列）
使用LinkedList实现Stack（栈）与Queue（队列）
首先引用JDK API中关于LinkedList的一句说明："These operations allow linked lists to be used as a stack, queue, or double-ended queue."由此，可以得知，使用LinkedList可以轻松的实现栈和队列的功能。通过查看LinkedList源码实现，发现其底层采用双向链表实现。
一：使用LinkedList实现Stack
| public class TestStack { public static void main(String[] args) { MyStack ms = new MyStack(); ms.push("aaa"); ms.push("bbb"); ms.push(new Integer(3)); System.out.println(ms.peek()); System.out.println(ms.pop()); System.out.println(ms.isEmpty()); System.out.println(ms.pop()); System.out.println(ms.pop()); System.out.println(ms.isEmpty()); } } | |
public class TestStack
{
public static void main(String[] args)
{
MyStack ms = new MyStack();
ms.push("aaa");
ms.push("bbb");
ms.push(new Integer(3));
System.out.println(ms.peek());
System.out.println(ms.pop());
System.out.println(ms.isEmpty());
System.out.println(ms.pop());
System.out.println(ms.pop());
System.out.println(ms.isEmpty());
}
}
import java.util.LinkedList;public class TestStack{ public static void main(String[] args) { MyStack ms = new MyStack(); ms.push("aaa"); ms.push("bbb"); ms.push(new Integer(3)); System.out.println(ms.peek()); System.out.println(ms.pop()); System.out.println(ms.isEmpty()); System.out.println(ms.pop()); System.out.println(ms.pop()); System.out.println(ms.isEmpty()); } }class MyStack{ //无论栈还是队列，里面都会维护一个成员变量，该成员变量用于存储栈或队列的元素，该成员变量使用LinkedList类型。 private LinkedList list = new LinkedList(); public void push(Object o) { list.add(o); } public Object pop() { return list.removeLast(); } public Object peek()//查看栈顶元素 { return list.getLast(); } public boolean isEmpty() { return list.isEmpty(); }}
在Eclipse中的输出结果是：
--------------------------------------------------------------------------------
3
3
false
bbb
aaa
true
--------------------------------------------------------------------------------
二：使用LinkedList实现Queue
import java.util.LinkedList;public class TestQueue{ public static void main(String[] args) { MyQueue mq = new MyQueue(); mq.put("aaa"); mq.put("bbb"); mq.put(new Integer(3)); System.out.println(mq.get()); System.out.println(mq.isEmpty()); System.out.println(mq.get()); System.out.println(mq.get()); System.out.println(mq.isEmpty()); }}class MyQueue{ //无论栈还是队列，里面都会维护一个成员变量，该成员变量用于存储栈或队列的元素，该成员变量使用LinkedList类型。 private LinkedList list = new LinkedList(); public void put(Object o) { list.add(o);//this method is equivalent list.addFirst(o); } public Object get() { return list.remove();//or return list.removeFirst(); } public boolean isEmpty() { return list.isEmpty(); }}
在Eclipse中的输出结果是：
-------------------------------------------------------------------------------
aaa
false
bbb
3
true
-------------------------------------------------------------------------------
使用LinkedList实现Stack（栈）与Queue（队列）