stackqueue.java

来自「java的书上例子」· Java 代码 · 共 111 行

/** 一个应用程序，用双向链表实现了队列和栈的数据结构
  * @作者：尉哲明
  * @日期：2001年5月 */

/** 类LinkedList，双向链表类 */
class LinkedList{ 
	char data;
	LinkedList back;
	LinkedList forward;
}//类LinkedList结束

/** 接口Access，定义从队列和栈存取操作的接口 */
interface Access{ 

	/** 定义put()方法 */
	void put(char c);

	/** 定义get()方法 */
	char get();
}//接口Access结束

/** 类Queue，队列类，实现接口Access */
class Queue implements Access{ 
	private LinkedList QHead=new LinkedList();
	private LinkedList QRear=QHead; //初始化队头和队尾

	/** 实现接口Access的put()方法，该方法向队列存一个字符 */
	public void put(char c){
		QRear.forward=new LinkedList();
		QRear.forward.data=c;
		QRear.forward.back=QRear;
		QRear=QRear.forward;
	}

	/** 实现接口Access的get()方法，该方法从队列取一个字符 */
	public char get(){ 
		if(QHead!=QRear){ //如果队列不为空则取数
		  QHead.forward.back=null;
		  QHead=QHead.forward;
		  return QHead.data;
		}
		else{ 
		  System.out.println("The queue is empty!");
		  return '\0';
		}
	}
}//类Queue结束

/** 类Stack，栈类，实现接口Access */
class Stack implements Access { //定义栈类
	private LinkedList bottom=new LinkedList();
	private LinkedList top=bottom; //初始化栈顶与栈底

	/** 实现接口Access的put()方法，该方法向栈存一个字符 */
	public void put(char c){ 
		top.forward=new LinkedList();
		top.forward.data=c;
		top.forward.back=top;
		top=top.forward;
	}

	/** 实现接口Access的get()方法，该方法从栈中取一个字符 */
	public char get(){ 
		if(top!=bottom){ //如果栈不为空则取数
		  char ch=top.data;
		  top.back.forward=null;
		  top=top.back;
		  return ch;
		}
		else{ 
		  System.out.println("The stack is empty!");
		  return '\0';
		}
	}
}//类Stack结束

/** 类StackQueue */
public class StackQueue{

	/** main()方法 */
	public static void main(String a[]){
		char ch;
		Queue q=new Queue(); //创建一队列q
		Stack s=new Stack(); //创建一个栈s
		q.put('x'); 
		q.put('y');
		q.put('z'); //向队列q存入三个字符
		s.put('x');
		s.put('y');
		s.put('z'); //向栈s中存入三个字符
		System.out.println("Queue:");
		if((ch=q.get())!='\0')
		  System.out.println(ch);
		if((ch=q.get())!='\0')  
		  System.out.println(ch);
		if((ch=q.get())!='\0')  
		  System.out.println(ch);
		if((ch=q.get())!='\0')
		  System.out.println(ch); //从队列q中取数并显示
		System.out.println("Stack:");
		if((ch=s.get())!='\0')		
		  System.out.println(ch);
		if((ch=s.get())!='\0')  
		  System.out.println(ch);
		if((ch=s.get())!='\0')  
		  System.out.println(ch);
		if((ch=s.get())!='\0')  
		  System.out.println(ch); //从栈s中取数并显示
	}
}//类StackQueue结束