四,栈和队列
栈
栈只允许访问一个数据项:即最后插入的数据项.移出这个数据项后才能访问倒数第二个插入的数据项,
以此类推.这种机制在不少编程环境中都很有用.
大部分微处理器运用基于栈的体系结构.当调用一个方法时,把它的返回地址和参数压入栈,当方法结束
返回时,那些数据出栈.栈操作就嵌入在微处理器中.
package stack;
import java.io.*;
/** *//**
*
* @author jason
*
*/
class StackC 
{
private int maxSize;
private char[] stackArray;
private int top;
// --------------------------------------------------------------
public StackC(int max) // constructor
{
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
// --------------------------------------------------------------
public void push(char j) // put item on top of stack
{
stackArray[++top] = j;
}
// --------------------------------------------------------------
public char pop() // take item from top of stack
{
return stackArray[top--];
}
// --------------------------------------------------------------
public char peek() // peek at top of stack
{
return stackArray[top];
}
// --------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{
return (top == -1);
}
// --------------------------------------------------------------
} // end class StackX
// //////////////////////////////////////////////////////////////
class Reverser {
private String input; // input string
private String output; // output string
// --------------------------------------------------------------
public Reverser(String in) // constructor
{
input = in;
}
// --------------------------------------------------------------
public String doRev() // reverse the string
{
int stackSize = input.length(); // get max stack size
StackC theStack = new StackC(stackSize); // make stack
for (int j = 0; j < input.length(); j++) {
char ch = input.charAt(j); // get a char from input
theStack.push(ch); // push it
}
output = "";
while (!theStack.isEmpty()) {
char ch = theStack.pop(); // pop a char,
output = output + ch; // append to output
}
return output;
} // end doRev()
// --------------------------------------------------------------
} // end class Reverser
// //////////////////////////////////////////////////////////////
class ReverseApp {
public static void main(String[] args) throws IOException {
String input, output;
while (true) {
System.out.print("Enter a string: ");
System.out.flush();
input = getString(); // read a string from kbd
if (input.equals("")) // quit if [Enter]
break;
// make a Reverser
Reverser theReverser = new Reverser(input);
output = theReverser.doRev(); // use it
System.out.println("Reversed: " + output);
} // end while
} // end main()
// --------------------------------------------------------------
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// --------------------------------------------------------------
} // end class ReverseApp
// //////////////////////////////////////////////////////////////
上面的这个例子就是栈的应用，给定一个字符串按照倒排的顺序重新输出。
栈的效率
在实现栈的类中，数据项入栈和出栈的时间复杂度都为常数O(1).这也就是说，栈操作所耗的时间不依
赖于栈中数据项的个数，因此操作时间短。栈不需要比较和移动操作。
队列
队列(queue)，队列是一种数据结构，有点类似栈，只是在队列中第一个插入的数据项也会最先被移出
（先进先出,FIFO）,而在栈中，最后插入的数据项最先移出（LIFO）
队列的代码：
package queue;
/** *//**
*
* @author jason
*
*/
class Queue
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
//--------------------------------------------------------------
public Queue(int s) // constructor
{
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//--------------------------------------------------------------
public void insert(long j) // put item at rear of queue
{
if(rear == maxSize-1) // deal with wraparound
rear = -1;
queArray[++rear] = j; // increment rear and insert
nItems++; // one more item
}
//--------------------------------------------------------------
public long remove() // take item from front of queue
{
long temp = queArray[front++]; // get value and incr front
if(front == maxSize) // deal with wraparound
front = 0;
nItems--; // one less item
return temp;
}
//--------------------------------------------------------------
public long peekFront() // peek at front of queue
{
return queArray[front];
}
//--------------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{
return (nItems==0);
}
//--------------------------------------------------------------
public boolean isFull() // true if queue is full
{
return (nItems==maxSize);
}
//--------------------------------------------------------------
public int size() // number of items in queue
{
return nItems;
}
//--------------------------------------------------------------
} // end class Queue
////////////////////////////////////////////////////////////////
class QueueApp
{
public static void main(String[] args)
{
Queue theQueue = new Queue(5); // queue holds 5 items
theQueue.insert(10); // insert 4 items
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove(); // remove 3 items
theQueue.remove(); // (10, 20, 30)
theQueue.remove();
theQueue.insert(50); // insert 4 more items
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while( !theQueue.isEmpty() ) // remove and display
{ // all items
long n = theQueue.remove(); // (40, 50, 60, 70, 80)
System.out.print(n);
System.out.print(" ");
}
System.out.println("");
} // end main()
} // end class QueueApp
////////////////////////////////////////////////////////////////
队列的效率
和栈一样，队列中插入数据项和移出数据项的时间复杂度均为 O(1).
双端队列
双端队列就是一个两端都是结尾的对列。队列的每一个端都可以插入数据项和移出数据项。这些方法可
以叫作insertLeft()和insertRight(),以及removeLeft()和removeRight().
如果严禁调用insertLeft()和removeLeft()方法（或禁用右端的操作），双端队列功能就和栈一样。禁
止调用insertLeft()和removeLeft()方法（或相反的另一对方法），他的功能就和队列一样了。
双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列
的两种功能。但是，双端队列 不像栈和队列那常用。
优先级队列
优先级队列是比栈和队列更专用的数据结构。但它在很多情况下都很有用。像普通队列一样，优先级队
列有一个对头和一个队尾，并且也是从对头移出数据项。不过在优先级队列中，数据项按关键字的值有
序，这样关键字最小的数据项（或者在某些实现中是关键最大的数据项）总是在队列头。数据项插入的
时候会按照顺序插入到合适的位置以确保队列的顺序。
优先级队列的效率
优先级队列插入操作需要时间O(N)的时间，而删除操作则需要O(1)的时间。