《java中用linkedlist实现栈和队列》由会员分享,可在线阅读,更多相关《java中用linkedlist实现栈和队列(5页珍藏版)》请在金锄头文库上搜索。
1、栈和队列是两种特殊的线性表,它们的逻辑结构和线性表相同,只是其运算规则较线性表有更多的限制,故又称它们为运算受限的线性表。 LinkedList数据结构是一种双向的链式结构,每一个对象除了数据本身外,还有两个引用,分别指向前一个元素和后一个元素,和数组的顺序存储结构(如:ArrayList)相比,插入和删除比较方便,但速度会慢一些。 栈的定义 栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。 (1)通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。 (2)当表中没有元素时称为空栈。 (3)栈为后进先出(Last In First Out)的线性表,简称为L
2、IFO表。 栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中最新的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。 实现代码: package com.weisou.dataStruct; import java.util.LinkedList; SuppressWarnings(unchecked) public class MyStack LinkedList linkList = new LinkedList(); public void push(Object object) linkList.addFirst(object); publi
3、c boolean isEmpty() return linkList.isEmpty(); public void clear() linkList.clear(); / 移除并返回此列表的第一个元素 public Object pop() if (!linkList.isEmpty() return linkList.removeFirst(); return 栈内无元素; public int getSize() return linkList.size(); public static void main(String args) MyStack myStack = new MySta
4、ck(); myStack.push(2); myStack.push(3); myStack.push(4); System.out.println(myStack.pop(); System.out.println(myStack.pop(); 队列定义 队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表 (1)允许删除的一端称为队头(Front)。 (2)允许插入的一端称为队尾(Rear)。 (3)当队列中没有元素时称为空队列。 (4)队列亦称作先进先出(First In First Out)的线性表,简称为FIFO表。 实现代码: package com.w
5、eisou.dataStruct; import java.util.LinkedList; /* * * author gf * date 2009-11-13 */ public class MyQueue LinkedList linkedList = new LinkedList(); /队尾插 public void put(Object o) linkedList.addLast(o);/队头取 取完并删除 public Object get() if(!linkedList.isEmpty() return linkedList.removeFirst(); else retur
6、n ; public boolean isEmpty() return linkedList.isEmpty(); public int size() return linkedList.size(); public void clear() linkedList.clear(); /* * param args */ public static void main(String args) MyQueue myQueue= new MyQueue(); myQueue.put(1); myQueue.put(2); myQueue.put(3); System.out.println(myQueue.get();