链表实现的栈
// linkStack.java// demonstrates a stack implemented as a list// to run this program: C>java LinkStackAppclass Link { public long dData; // data item public Link next; // next link in list// ------------------------------------------------------------- public Link(long dd) // constructor { dData = dd; }// ------------------------------------------------------------- public void displayLink() // display ourself { System.out.print(dData + " "); } } // end class Linkclass LinkList { private Link first; // ref to first item on list// ------------------------------------------------------------- public LinkList() // constructor { first = null; } // no items on list yet// ------------------------------------------------------------- public boolean isEmpty() // true if list is empty { return (first==null); }// ------------------------------------------------------------- public void insertFirst(long dd) // insert at start of list { // make new link Link newLink = new Link(dd); newLink.next = first; // newLink --> old first first = newLink; // first --> newLink }// ------------------------------------------------------------- public long deleteFirst() // delete first item { // (assumes list not empty) Link temp = first; // save reference to link first = first.next; // delete it: first-->old next return temp.dData; // return deleted link }// ------------------------------------------------------------- public void displayList() { Link current = first; // start at beginning of list while(current != null) // until end of list, { current.displayLink(); // print data current = current.next; // move to next link } System.out.println(""); }// ------------------------------------------------------------- } // end class LinkListclass LinkStack { private LinkList theList;//-------------------------------------------------------------- public LinkStack() // constructor { theList = new LinkList(); }//-------------------------------------------------------------- public void push(long j) // put item on top of stack { theList.insertFirst(j); }//-------------------------------------------------------------- public long pop() // take item from top of stack { return theList.deleteFirst(); }//-------------------------------------------------------------- public boolean isEmpty() // true if stack is empty { return ( theList.isEmpty() ); }//-------------------------------------------------------------- public void displayStack() { System.out.print("Stack (top-->bottom): "); theList.displayList(); }//-------------------------------------------------------------- } // end class LinkStackclass LinkStackApp { public static void main(String[] args) { LinkStack theStack = new LinkStack(); // make stack theStack.push(20); // push items theStack.push(40); theStack.displayStack(); // display stack theStack.push(60); // push items theStack.push(80); theStack.displayStack(); // display stack theStack.pop(); // pop items theStack.pop(); theStack.displayStack(); // display stack } // end main() } // end class LinkStackApp 用链表实现的队列
// linkQueue.java// demonstrates queue implemented as double-ended list// to run this program: C>java LinkQueueAppclass Link { public long dData; // data item public Link next; // next link in list// ------------------------------------------------------------- public Link(long d) // constructor { dData = d; }// ------------------------------------------------------------- public void displayLink() // display this link { System.out.print(dData + " "); }// ------------------------------------------------------------- } // end class Linkclass FirstLastList { private Link first; // ref to first item private Link last; // ref to last item// ------------------------------------------------------------- public FirstLastList() // constructor { first = null; // no items on list yet last = null; }// ------------------------------------------------------------- public boolean isEmpty() // true if no links { return first==null; }// ------------------------------------------------------------- public void insertLast(long dd) // insert at end of list { Link newLink = new Link(dd); // make new link if( isEmpty() ) // if empty list, first = newLink; // first --> newLink else last.next = newLink; // old last --> newLink last = newLink; // newLink <-- last }// ------------------------------------------------------------- public long deleteFirst() // delete first link { // (assumes non-empty list) long temp = first.dData; if(first.next == null) // if only one item last = null; // null <-- last first = first.next; // first --> old next return temp; }// ------------------------------------------------------------- public void displayList() { Link current = first; // start at beginning while(current != null) // until end of list, { current.displayLink(); // print data current = current.next; // move to next link } System.out.println(""); }// ------------------------------------------------------------- } // end class FirstLastListclass LinkQueue { private FirstLastList theList;//-------------------------------------------------------------- public LinkQueue() // constructor { theList = new FirstLastList(); } // make a 2-ended list//-------------------------------------------------------------- public boolean isEmpty() // true if queue is empty { return theList.isEmpty(); }//-------------------------------------------------------------- public void insert(long j) // insert, rear of queue { theList.insertLast(j); }//-------------------------------------------------------------- public long remove() // remove, front of queue { return theList.deleteFirst(); }//-------------------------------------------------------------- public void displayQueue() { System.out.print("Queue (front-->rear): "); theList.displayList(); }//-------------------------------------------------------------- } // end class LinkQueueclass LinkQueueApp { public static void main(String[] args) { LinkQueue theQueue = new LinkQueue(); theQueue.insert(20); // insert items theQueue.insert(40); theQueue.displayQueue(); // display queue theQueue.insert(60); // insert items theQueue.insert(80); theQueue.displayQueue(); // display queue theQueue.remove(); // remove items theQueue.remove(); theQueue.displayQueue(); // display queue } // end main() } // end class LinkQueueApp