队列。queue，就是现实生活中的排队。
1、简单队列：
public class Queqe {
private int array[];
private int front;
private int end;
private int number;
private int max;
private Queqe(int maxsize){
array = new int[maxsize];
max = maxsize;
front = 0;
end = 0;
number = 0;
}
private void insert(int item){
if(isFull()){
System.out.println("is full,can not insert");
return;
}
array[end++] = item;
number++;
}
private int remove(){
if(isEmpty()){
System.out.println("is empty,can not remove");
return -1;
}
number--;
return array[front++];
}
private boolean isFull(){
return number == max;
}
private boolean isEmpty(){
return number == 0;
}
private int size(){
return number;
}
private int peekFront(){
return array[front];
}
public static void main(String[] args) {
Queqe q = new Queqe(4);
System.out.println("queqe is empty:"+q.isEmpty());
q.insert(1);
q.insert(2);
q.insert(3);
q.insert(4);
q.insert(5);
System.out.println(q.size());
System.out.println("front is "+q.peekFront());
while(!q.isEmpty())
System.out.println(q.remove());
}
}
result:
queqe is empty:true
is full,can not insert
4
front is 1
1
2
3
4
还是通过数组实现，可是和栈不同的是。队列的话有队头队尾。队头指向队列的首部。而队尾指向队列的尾部。number为队列中数的个数，每当插入一个新元素。队尾后移。每当移除一个新元素，队首后移，插入和移除的同一时候依据队列是否为空或者是满，才进行插入和移除。
先进的元素排在前面，那么移除的时候就是先移除队头，达到先进先出的效果。·插入和移除并不用移动整个数组，仅仅需改变队头和队列的指向，所以时间复杂度和栈一样都是O(1)。
2、不用number之后的方法改变
前面用了number统计队列中元素个数，事实上不用这个变量。单靠队头和队尾也是能够实现队列。
private boolean isFull(){
return end == max;
}
private boolean isEmpty(){
return (front ==0&&end ==0)||front == max;
}
private int size(){
return end -front;
}
队尾减去队头就是元素的个数。由于一旦插入，end是添加1的。
而推断是不是满了更简单，队尾移到数组尾部即是满了。
空的话会复杂一些，一种是一開始front为零，可是有元素插入，此时end不为零。假设两者为零那就是空了。还有就是不停remove之后，front移到最后，证明之前的元素所有remove掉了，此时也为空。
作者依据的是front和end的变化。然后再insert和remove中直接改变front和end的值，在isEmpty和isFull中，比如在isFull()中：
private boolean isFull(){
return end+2 == front||(front+max-2==end);
}
作者的end一開始设为-1，然后一旦end超过max会变成-1，所以其中有着非常复杂的位置关系。
这样更复杂。
由于这样相似循环队列，超出之后又重头開始插入。
事实上在isEmpty和isFull中直接进行推断就能够了。
然后真的超出的时候直接打印错误后return。
3、优先级队列
银行办业务当然要排队，可是。银行的vip用户不须要，由于他存的钱比你多。银行重视这种客户。优先级高，所以他尽管比你晚来到银行。可是排号的时候拿到的号比你还前。
那这种话，优先级队列就像是一開始就依据优先级排列好顺序的队列。
private void insert(int item){
if(isFull()){
System.out.println("is full,can not insert");
return;
}
if(end == 0){
array[end++] = item;
}else{
int i;
for ( i = number-1; i >=0; i--) {
if(item > array[i]){
array[i+1] = array[i];
}
}
array[i+1]= item;
end++;
}
number++;
}
result：
queqe is empty:true
size:0
is full,can not insert
queqe is empty:false
size:4
front is 4
4
3
2
1
如今我们将数值大的看成是优先级高的，第一个插入直接插入数组第一位，后面插入的開始比較，假设比前面的数都小，那么就放在队列最后面，假设大的话，就将整个队列后推，然后找到适当的位置插入。和插入排序是相似的。
这样插入元素的同一时候，就已经依照优先级从大到小的顺序排好序了（前:prefix expression 中:infix expression 后:postfix expression）。
4、算术表达式的解析
1+2+3=？
由于我们从小接受的教育就是从左到右，有括号计算括号中面，先乘除后加减这种思路。然后看到上面那个算式的时候一下子就得出结果，这是中缀表达式。
也就是我们脑里面计算算式的方式。
从左到右，1+2看后面，是+号。那能够直接算1+2的值为3,3+3后面是=号了，直接计算3+3=6。
1+2*3=？
从左到右，1+2看后面，是*号，那不能直接算1+2的值,先计算2*3=6。再看后面为=。所以计算1+6=7。
1*（2+3）=？
从左到右，1后面是*，所以本来先计算的，可是后面是（所以先看括号，括号中面是2+3=5后面是=，所以直接计算1*5=5。
可是计算机并不像人脑这么聪明。一眼看过去基本能够心算。计算机认后缀表达式比較easy，假设我们从小就接受的是后缀表达式的方式的话。那对于我们来说一样能够。
后缀表达式的话就用符号a,b,c表示了。由于多位数字的话，写成1242132+，根本就不知道是那两个数字相加，那么就要有分隔符，可是无疑会添加难度。
a+b-c转后缀：
读a。读到+，继续读到b，写成ab。再读到-号能够将+放在ab后面。即ab+，读入c，后面结束了则ab+c-。
a+b*c转后缀：
读a，读+，读b，放置为ab，再读后面，*优先级大于+号。临时不能放+，再读c，c后面结束。所以能够放入*，在放+。即abc*+。
a*(b+c)转后缀：
读a，读*，后面发现（不能放置*，（里比*优先级高，读b+c，后面为），可变为bc+，再和a*合。即abc+*。
这篇尽管讲得是队列。可是要用到的结构是栈，由于进来进去的。这里的算数不用压入栈，直接输出。
a+b-c转后缀：
直接输出a。读+。栈空压入栈，再输出b。栈非空。弹出+，读到-，+优先级>= -，输出+，压-入栈，输出c，结束了，弹出-。
最后结果：ab+c-。
a+b*c转后缀：
直接输出a，读+。栈空压入栈，再输出b，栈非空，弹出+，读到*，+优先级< -。所以先+压入栈，再压*，输出c，结束了，弹出*，再弹+。
最后结果：abc*+。
a*(b+c)转后缀：
直接输出a。读*。栈空压入栈。读到（压（入栈，输出b，读+。压入栈。输出c。读），发现后面结束能够弹出+并输出。弹出（不输出，弹出*。
最后结果：abc+*。
看了这个分析过程之后，就是利用栈，对操作符进行栈的压入和弹出。
假设纯粹用高级语言写计算器，直接使用中缀表达式就可以，可是到了底层的编译器。就是须要后缀表达式实现。还要考虑到位数和其它操作符，可想代码远远比上面的复杂。
总体的思路就是这样，代码的实现就是通过栈和条件推断进行入栈和出栈就可以。
- 顶
- 0
- 踩
- 1
- 上一篇Java数据结构和算法(四)——栈
- 下一篇Jquery入门