【数据结构与算法02】栈与队列_队列进栈和出栈的时间复杂度

    我们知道，在数组中，若知道数据项的下标，便可立即访问该数据项，或者通过顺序搜索数据项，访问到数组中的各个数据项。但是栈和队列不同，它们的访问是受限制的，即在特定时刻只有一个数据项可以被读取或者被删除。众所周知，栈是先进后出，只能访问栈顶的数据，队列是先进先出，只能访问头部数据。这里不再赘述。

    栈的主要机制可以用数组来实现，也可以用链表来实现，下面用数组来实现栈的基本操作：

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;
	}
	
	public boolean isEmpty() {
		return (top == -1);
	}
	
	public boolean isFull() {
		return (top == size -1);
	}
	
	public void display() {
		for(int i = top; i >= 0; i--) {
			System.out.print(a[i] + " ");
		}
		System.out.println("");
	}
}

 

    数据项入栈和出栈的时间复杂度均为O(1)。这也就是说，栈操作所消耗的时间不依赖于栈中数据项的个数，因此操作时间很短。栈不需要比较和移动操作。

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

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++;
/*		if(rear == size-1){
			rear = -1;
		}
		a[++rear] = value;
*/
	}
	
	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.print(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)。

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

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(isEmpty()){
			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.print(a[i] + " ");
		}
		System.out.println(" ");
	}
}

 

    这里实现的优先级队列中，插入操作需要O(N)的时间，而删除操作则需要O(1)的时间。在第8节里将介绍堆来改进插入操作的时间。http://blog.csdn.net/eson_15/article/details/51105955

    栈和队列就讨论到这吧，如果有错误，欢迎留言指正~

    欢迎大家关注我的公众号：“武哥聊编程”，一个有温度的公众号~

    关注回复：资源，可以领取海量优质视频资料
    

_____________________________________________________________________________________________________________________________________________________

-----乐于分享，共同进步！

-----更多文章请看：http://blog.csdn.net/eson_15