栈和队列

代码实现：

	public static void main(String[] args) {
//		中缀表达式3*(17-15)+18/6的逆波兰表达式如下
		String notation[]= {"3","17","15","-","*","18","6","/","+"};
		int result=caculate(notation);
		System.out.println("逆波兰表达式的结果为:"+result);
	}
	private static int caculate(String[] notation) {
//		创建一个栈对象stack存储操作数
		Stack<Integer> stack=new Stack<Integer>();
//		从左往右遍历逆波兰表达式，得到每一个字符串
		for(int i=0;i<notation.length;i++) {
			String curr=notation[i];
//			判断该字符串是不是运算符
			Integer o1;
			Integer o2;
			Integer result;
//			如果是运算符，则从stack栈中弹出两个操作数o1,o2
			switch(curr) {
			case "+":
//				如果是运算符，则从stack栈中弹出两个操作数o1,o2
				o1=stack.pop();
				o2=stack.pop();
//				使用该运算符计算o1和o2，得到结果result
				result=o1+o2;
//				把该结果压入stack栈中
				stack.push(result);
				break;
			case "-":
				o1=stack.pop();
				o2=stack.pop();
				result=o2-o1;
				stack.push(result);
				break;
			case "*":
				o1=stack.pop();
				o2=stack.pop();
				result=o1*o2;
				stack.push(result);
				break;
			case "/":
				o1=stack.pop();
				o2=stack.pop();
				result=o2/o1;
				stack.push(result);
				break;
			default:
//				如果不是，把该该操作数压入stack栈中
				stack.push(Integer.parseInt(curr));
				break;
			}
		}
		return stack.pop();
	}

}

2.队列

代码实现：

public class Queue<T> implements Iterable<T>{
//	首节点
	private Node head;
//	尾结点
	private Node last;
//	记录队列中元素个数
	private int N;
//	定义内部类
	private static class Node<T>{
		T item;
		Node next;
		public Node(T item,Node next) {
			this.item=item;
			this.next=next;
		}
	}
//	构造方法
	public Queue(){
		head=new Node(null,null);
		last=null;
		N=0;
	}
//	判断队列元素是否为空
	public boolean isEmpty() {
		return N==0;
	}
//	返回队列中元素个数
	public int size() {
		return N;
	}
	//从队列中拿出一个元素
	public T dequeue() {
		if(isEmpty()) {
			return null;
		}
		
		Node<T> oldfirst=head.next;
		head.next=oldfirst.next;
//		元素个数-1
		N--;
//		
		if(isEmpty()) {
			last=null;
		}
		
		return oldfirst.item;
	}
	//向队列中插入元素t
	public void enqueue(T t) {
		if(last==null) {
			last=new Node(t,null);
			head.next=last;
		}else {
			Node oldlast=last;
			last=new Node(t,null);
			oldlast.next=last;
		}
//		元素个数+1
		N++;
	}
	@Override
	public Iterator<T> iterator() {
		return new QIterator();
	}
	private class QIterator<T> implements Iterator{
		Node<T> n;
		public QIterator() {
			n= head;
		}
		@Override
		public boolean hasNext() {
			
			return n.next!=null;
		}
		@Override
		public Object next() {
			n=n.next;
			return n.item;
		}	
	}
}