栈 队列 有序队列数据结构的生命周期比那些数据库类型的结构(比如链表，树)要短得多。在程序操作执行期间他们才被创建，通常用他们去执行某项特殊的任务；当完成任务之后，他们就会被销毁。这三个数据结构还有一个特点就是访问是受到限制的，即在特定时刻只有一个数据项可以被读取或者被删除，但是所谓的移除并不是真的删除，数据项依然在这些数据结构中，只不过因为指针已经指向其他数据项，没有办法访问到，当添加新的数据项时，当初移除的数据项被替代从而永远消失。
栈 队列 优先级队列的模拟思想
1.栈：栈遵循先进后出(FILO)模式最后插入的数据项最先被移除，而且只能访问最后的数据项，只有当移除这个数据项之后才能访问倒数第二项的数据项。
2.队列：队列遵循先进先出(FIFO)模式首先被插入的数据项最先被移除，而且只能访问访问第一个数据项，只有当移除这个数据项之后才能访问第二项的数据项。特别的为了避免队列不满却不能插入新数据项，可以让队头队尾指针绕回到数组开始的位置，这就是循环队列。
3.优先级队列：优先级队列和队列的特性相同有队头和队尾，除此之外在优先级队列中，数据项按关键字的值有序，这样关键字最小的数据项或最大的数据项(视情况而定)总是在队头，数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。
栈 队列 优先级队列的效率
栈：插入操作需要O(1),删除操作需要O(1)。
队列：插入操作需要O(1),删除操作需要O(1)。
优先级队列：插入操作需要O(N),删除操作需要O(1)。
栈 队列 优先级队列的指针
栈：top= -1。
队列：rear = -1， front = 0。
优先级队列：nItems = 0。
栈 队列 优先级队列的java代码
栈
package sy;
import sy.Stack;
class Stack{
//定义栈长度
private int maxSize;
//定义栈
private long[] stackArray;
//定义栈指针
private int top;
//定义构造方法
public Stack(int n){
maxSize = n;
stackArray = new long[maxSize];
top = -1;
}
//定义插入方法
public void push(long n){
//栈长度先增加，再向栈中压入数据
stackArray[++top] = n;
}
//定义删除方法
public long pop(){
//先向栈中压入数据，栈长度再减少
return stackArray[top--];
}
//定义查找方法
public long peek(){
return stackArray[top];
}
//定义查空方法
public boolean isEmpty(){
return (top == -1);
}
//定义查满方法
public boolean isFull(){
return (top == maxSize - 1);
}
}
public class App {
public static void main(String[] args){
Stack theStack = new Stack(10);
theStack.push(20);
theStack.push(40);
theStack.push(60);
theStack.push(80);
while(!theStack.isEmpty())
{
long value = theStack.pop();
System.out.print(value);
System.out.print(" ");
}
System.out.println("");
}
}
队列(带nItems)
package sy;
class Queue{
//定义队列长度
private int maxSize;
//定义队列
private long[] queArray;
//定义队首指针
private int front;
//定义队尾指针
private int rear;
//定义数据项个数
private int nItems;
//定义构造方法
public Queue(int n){
maxSize = n;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//定义插入方法
public void insert(long n){
//判断是否循环至队首
if(rear == maxSize - 1)
{
rear = -1;
}
//先自增再赋值
queArray[++rear] = n;
nItems++;
}
//定义删除方法
public long remove(){
//先赋值在自增
long temp = queArray[front++];
//判断是否循环至队首
if(front == maxSize)
{
front = 0;
}
nItems--;
return temp;
}
//定义查找首项方法
public long peekFront(){
return queArray[front];
}
public boolean isEmpty(){
return (nItems == 0);
}
public boolean isFull(){
return (nItems == maxSize);
}
public int size(){
return nItems;
}
}
public class App {
public static void main(String[] args){
Queue theQueue = new Queue(5);
theQueue.insert(10);
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove();
theQueue.remove();
theQueue.remove();
theQueue.insert(50);
theQueue.insert(60);
theQueue.insert(70);
theQueue.insert(80);
while(!theQueue.isEmpty())
{
long n = theQueue.remove();
System.out.print(n);
System.out.print(" ");
}
System.out.print("");
}
}
注意：insert()和remove方法中分别递增和递减了nItems，当处理大量的插入和移除操作的时候，就会影响性能。
队列(没有nItems)
package sy;
//import aa.Queue;
class Queue{
//定义队列长度
private int maxSize;
//定义队列
private long[] queArray;
//定义队首指针
private int front;
//定义队尾指针
private int rear;
//定义构造方法
public Queue(int n){
//这里最大值要加一
maxSize = n + 1;
queArray = new long[maxSize];
front = 0;
rear = -1;
}
//定义插入方法
public void insert(long n){
//判断是否循环至队首
if(rear == maxSize - 1)
{
rear = -1;
}
//先自增再赋值
queArray[++rear] = n;
}
//定义删除方法
public long remove(){
//先赋值在自增
long temp = queArray[front++];
//判断是否循环至队首
if(front == maxSize)
{
front = 0;
}
return temp;
}
//定义查找首项方法
public long peekFront(){
return queArray[front];
}
public boolean isEmpty(){
return (rear + 1 == front || (front + maxSize - 1 == rear));
}
public boolean isFull(){
return (rear + 2 == front || (front + maxSize - 2 == rear));
}
}
public class App {
public static void main(String[] args){
Queue theQueue = new Queue(5);
theQueue.insert(10);
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove();
theQueue.remove();
theQueue.remove();
theQueue.insert(50);
theQueue.insert(60);
theQueue.insert(70);
theQueue.insert(80);
while(!theQueue.isEmpty())
{
long n = theQueue.remove();
System.out.print(n);
System.out.print(" ");
}
System.out.print("");
}
}
优先级队列
package aa; import java.io.IOException;
//在这个队列中小的在后，队列有大到小排列，这里只能访问最后一个数据项
class Priority{
private int maxSize;
private long[] queArray;
private int nItems; public Priority(int s){
maxSize = s;
queArray = new long[maxSize];
nItems = 0;
} public void insert(long i){
//定义一个临时变量
int j;
//判断数据项是否为零
if(nItems == 0)
{
//如果为零插入数据，数据项增加
queArray[nItems++] = i;
}
else
{
//数据项从后往前遍历，注意j>=0
for(j = nItems - 1; j >= 0; j--)
{
//判断插入项是否大于遍历的数据项
if(i > queArray[j])
{
//如果大于则从j的数据项开始每一项都后移一位
queArray[j+1] = queArray[j];
}
else
{
break;
}
}
//在for循环中最后一次循环的最后阶段执行了j--，所以在这里加回来，这样for循环外的j+1相当于for循环内的判断的j
queArray[j + 1] = i;
nItems++;
}
} public long remove(){
return queArray[--nItems];
} public long peekMin(){
return queArray[nItems - 1];
} public boolean isEmpty(){
return (nItems == 0);
} public boolean isFull(){
return (nItems == maxSize);
}
}
public class PriorityApp {
public static void main(String[] args) throws IOException{
Priority thePri = new Priority(5);
thePri.insert(30);
thePri.insert(50);
thePri.insert(10);
thePri.insert(40);
thePri.insert(20); while(!thePri.isEmpty())
{
long item = thePri.remove();
System.out.print(item + " ");
}
System.out.println("");
}
}