基于链表实现Java 自定义Stack队列

接下来让我们看看，如何利用单链表结构来实现栈与队列。由于栈的操作只限于栈顶元素，，而单链表只有对首元素才能在O(1)时间内完成插入和删除，故这里把单链表的首节点作为栈顶，其余元素依次排列。此外，为了保证getSize()方法也能够在O(1)时间内完成，还需借助一个实例变量来动态记录栈中元素的数目。具体的实现如 代码二.12 所示。

Node类 Java代码见（ Java 实现链表）

StackLink 类：

package com.list.stack;import java.util.Arrays;import com.stack.ExceptionStackEmpty;import com.list.stack.Node;{size;Node top;public StackList() {this.size = 0;this.top = null;}() {if(isEmpty())return 0;elsereturn size;}() {return size == 0;}// Get the top element of stackpublic Object top() throws ExceptionStackEmpty {if(isEmpty())throw new ExceptionStackEmpty(“Stack is empty!”);return top.getElement();}(Object element){Node newNode = new Node(element,top);top = newNode;size ++;}// Pop element from stackpublic Object pop() throws ExceptionStackEmpty {if(isEmpty())throw new ExceptionStackEmpty(“Stack is empty!”);Object container = top.getElement();top = top.getNext();size –;return container;}() throws ExceptionStackEmpty {Node travelTop;travelTop = top;Object[] array = new Object[getSize()];for(int i = 0;i < array.length;i ++ ){array[i] = travelTop.getElement();travelTop = travelTop.getNext();}System.out.println(“Get all elemnt: ” + Arrays.toString(array));}}

StackLinkTest 类：

package import public class StackListTest {public static void main(String[] args) throws ExceptionStackEmpty {//Test Class StackListStackList sl = new StackList();System.out.println(“Size of stack list: ” + sl.getSize());System.out.println(“Is emplty? : ” + sl.isEmpty());sl.push(12);sl.push(13);sl.push(15);sl.push(17);sl.push(2);sl.push(6);sl.getAllElements();System.out.println(“Size of stack list: ” + sl.getSize());System.out.println(“Is emplty? : ” + sl.isEmpty());//sl.getAllElements();System.out.println(sl.pop());System.out.println(sl.pop());System.out.println(sl.pop());System.out.println(sl.pop());System.out.println(sl.pop());System.out.println(sl.pop());System.out.println(“Size of stack list: ” + sl.getSize());System.out.println(“Is emplty? : ” + sl.isEmpty());}}

测试结果:

Size all elemnt: [6, 2, 17, 15, 13, 12]Size Size of stack list: 0Is emplty? : true

转载请注明出处，谢谢！

销售世界上第一号的产品–不是汽车，而是自己。