1、用链表实现栈
package stack;
/**
*
* @author denghb
*
*/
class Link {
public long dData;
public Link next;
public Link(long dd) {
dData = dd;
}
public void displayLink() {
System.out.print(dData + " ");
}
} class LinkList {
private Link first;
public LinkList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(long dd) {
Link newLink = new Link(dd);
newLink.next = first;
first = newLink;
}
public long deleteFirst() {
//如果这是一个非空链表
Link temp = first;
first = first.next;
return temp.dData;
}
public void displayList() {
Link current = first;
while(current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
} class LinkStack {
private LinkList theList;
public LinkStack() {
theList = new LinkList();
}
public void push(long j) {
theList.insertFirst(j);
}
public long pop() {
return theList.deleteFirst();
}
public boolean isEmpty() {
return (theList.isEmpty());
}
public void displayStack() {
System.out.print("Stack (top-->bottom): ");
theList.displayList();
}
}
public class LinkStackApp {
public static void main(String[] args) {
LinkStack theStack = new LinkStack();
theStack.push(20);
theStack.push(40); theStack.displayStack(); theStack.push(60);
theStack.push(80); theStack.displayStack(); theStack.pop();
theStack.pop(); theStack.displayStack();
}
}
2、用链表实现队列
package queue;
/**
*
* @author denghb
*
*/
class Link {
public long dData;
public Link next;
public Link(long dd) {
dData = dd;
}
public void displayLink() {
System.out.print(dData + " ");
}
} class FirstLastList {
private Link first;
private Link last; public FirstLastList() {
first = null;
last = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertLast(long dd) {
Link newLink = new Link(dd);
if(isEmpty()) {
first = newLink;
} else {
last.next = newLink;
}
last = newLink;
}
public long deleteFirst() {
//如果这是一个非空链表
long temp = first.dData;
if(first.next == null) { //如果仅仅有一个链接点
last = null;
}
first = first.next;
return temp;
}
public void displayList() {
Link current = first;
while(current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
} class LinkQueue {
private FirstLastList theList;
public LinkQueue() {
theList = new FirstLastList();
}
public void insert(long j) {
theList.insertLast(j);
}
public long remove() {
return theList.deleteFirst();
}
public boolean isEmpty() {
return (theList.isEmpty());
}
public void displayStack() {
System.out.print("Stack (top-->bottom): ");
theList.displayList();
}
} public class LinkQueueApp {
public static void main(String[] args) {
LinkQueue theQueue = new LinkQueue();
theQueue.insert(20);
theQueue.insert(40); theQueue.displayStack(); theQueue.insert(60);
theQueue.insert(80); theQueue.displayStack(); theQueue.remove();
theQueue.remove();
theQueue.displayStack();
}
}
第一个源程序的输出结果：
Stack (top-->bottom): 40 20
Stack (top-->bottom): 80 60 40 20
Stack (top-->bottom): 40 20
第二个源程序的输出结果：
Stack (top-->bottom): 20 40
Stack (top-->bottom): 20 40 60 80
Stack (top-->bottom): 60 80