栈和队列.md

#栈和队列

##栈

栈只允许访问一个数据项：即最后插入的数据。溢出这个数据才能访问倒数第二个插入的数据项。它是一种"后进先出"的数据结构。

栈最基本的操作是出栈(Pop)、入栈(Push)，还有其他扩展操作，如查看栈顶元素，判断栈是否为空、是否已满，读取栈的大小等。

/**
 * 栈是先进后出
 * 只能访问栈顶的数据
 * @author dream
 *
 */

/**
 * 基于数组来实现栈的基本操作
 * 数据项入栈和出栈的时间复杂度均为O(1)
 * @author dream
 *
 */
public class ArrayStack {

	private long[] a;
	private int size;   //栈数组的大小
	private int top;   //栈顶
	
	public ArrayStack(int maxSize){
		this.size = maxSize;
		this.a = new long[size];
		this.top = -1;   //表示空栈
	}
	
	public void push(long value){   //入栈
		if(isFull()){
			System.out.println("栈已满!");
			return;
		}
		a[++top] = value;
	}
	
	public long peek(){   //返回栈顶内容，但不删除
		if(isEmpty()){
			System.out.println("栈中没有数据");
			return 0;
		}
		return a[top];
	}
	
	
	public long pop(){   //弹出栈顶内容
		if(isEmpty()){
			System.out.println("栈中没有数据!");
			return 0;
		}
		return a[top--];
	}
	
	public int size(){
		return top + 1;
	}
	
	/**
	 * 判断是否满了
	 * @return
	 */
	public boolean isFull(){
		return (top == size - 1);
	}
	
	/**
	 * 是否为空
	 * @return
	 */
	public boolean isEmpty(){
		return (top == -1);
	}
	
	
	public void display(){
		for (int i = top; i >= 0; i--) {
			System.out.println(a[i] + " ");
		}
		System.out.println("");
	}
	
}

##队列

依然使用数组作为底层容器来实现一个队列的封装

/**
 * 队列也可以用数组来实现，不过这里有个问题，当数组下标满了后就不能再添加了，
 * 但是数组前面由于已经删除队列头的数据了，导致空。所以队列我们可以用循环数组来实现，
 * @author dream
 *
 */
public class RoundQueue {

	private long[] a;
	private int size;     //数组大小
	private int nItems;    //实际存储数量
	private int front;     //头
	private int rear;       //尾
	
	public RoundQueue(int maxSize){
		this.size = maxSize;
		a = new long[size];
		front = 0;
		rear = -1;
		nItems = 0;
	}
	
	public void insert(long value){
		if(isFull()){
			System.out.println("队列已满");
			return;
		}
		rear = ++rear % size;
		a[rear] = value;  //尾指针满了就循环到0处，这句相当于下面注释内容
		nItems++;
	}
	
	public long remove(){
		if(isEmpty()){
			System.out.println("队列为空!");
			return 0;
		}
		nItems--;
		front = front % size;
		return a[front++];
	}
	
	public void display(){
		if(isEmpty()){
			System.out.println("队列为空!");
			return;
		}
		int item = front;
		for(int i = 0;i < nItems; i++){
			System.out.println(a[item++ % size] + " ");
		}
		System.out.println("");
	}
	
	public long peek(){
		if(isEmpty()){
			System.out.println("队列为空！");
			return 0;
		}
		return a[front];
	}
	
	public boolean isFull(){
		return (nItems == size);
	}
	
	public boolean isEmpty(){
		return (nItems == 0);
	}
	
	public int size(){
		return nItems;
	}
	
	
}

和栈一样，队列中插入数据项和删除数据项的时间复杂度均为O(1)

还有个优先级队列，优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比，主要区别在于队列中的元素是有序的，关键字最小（或者最大）的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。这里用数组实现优先级队列。

public class PriorityQueue {

   private long[] a;
   private int size;
   private int nItems;  //元素个数
   
   public PriorityQueue(int maxSize){
   	size = maxSize;
   	nItems = 0;
   	a = new long[size];
   }
   
   public void insert(long value){
   	if(isFull()){
   		System.out.println("队列已满！");
   		return;
   	}
   	int j;
   	if(nItems == 0){  //空队列直接添加
   		a[nItems++] = value;
   	}else {
   		//将数组中的数字依照下标按照从大到小排列
   		for(j=nItems-1; j>=0; j--){
   			if(value > a[j]){  
                   a[j+1] = a[j];  
               }  
               else {  
                   break;  
               } 
   		}
   		a[j+1] = value;
   		nItems++;
   	}
   }
   
   public long remove(){
   	if(isFull()){
   		System.out.println("队列为空!");
   		return 0;
   	}
   	return a[--nItems];
   }
   
   public long peekMin(){
   	return a[nItems - 1];
   }
   
   public boolean isFull(){
   	return (nItems == size);
   }
   
   public boolean isEmpty(){
   	return (nItems == 0);
   }
   
   public int size(){
   	return nItems;
   }
   
   public void display(){
   	for(int i = nItems - 1;i >= 0; i--){
   		System.out.println(a[i] + " ");
   	}
   	System.out.println(" ");
   }
}

优先级队列中，插入操作需要O(N)的时间，而删除操作则需要O(1)的时间。