首页 > 代码库 > 使用LinkedList实现Stack（栈）与Queue（队列）

使用LinkedList实现Stack（栈）与Queue（队列）

2024-07-22 09:56:33   225人阅读

首先引用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（队列）


联系
我们