四,棧和隊列
棧
棧只允許訪問一個數(shù)據(jù)項:即最后插入的數(shù)據(jù)項.移出這個數(shù)據(jù)項后才能訪問倒數(shù)第二個插入的數(shù)據(jù)項,
以此類推.這種機制在不少編程環(huán)境中都很有用.
大部分微處理器運用基于棧的體系結構.當調用一個方法時,把它的返回地址和參數(shù)壓入棧,當方法結束
返回時,那些數(shù)據(jù)出棧.棧操作就嵌入在微處理器中.
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
// //////////////////////////////////////////////////////////////
上面的這個例子就是棧的應用，給定一個字符串按照倒排的順序重新輸出。
棧的效率
在實現(xiàn)棧的類中，數(shù)據(jù)項入棧和出棧的時間復雜度都為常數(shù)O(1).這也就是說，棧操作所耗的時間不依
賴于棧中數(shù)據(jù)項的個數(shù)，因此操作時間短。棧不需要比較和移動操作。
隊列
隊列(queue)，隊列是一種數(shù)據(jù)結構，有點類似棧，只是在隊列中第一個插入的數(shù)據(jù)項也會最先被移出
（先進先出,FIFO）,而在棧中，最后插入的數(shù)據(jù)項最先移出（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
////////////////////////////////////////////////////////////////
隊列的效率
和棧一樣，隊列中插入數(shù)據(jù)項和移出數(shù)據(jù)項的時間復雜度均為 O(1).
雙端隊列
雙端隊列就是一個兩端都是結尾的對列。隊列的每一個端都可以插入數(shù)據(jù)項和移出數(shù)據(jù)項。這些方法可
以叫作insertLeft()和insertRight(),以及removeLeft()和removeRight().
如果嚴禁調用insertLeft()和removeLeft()方法（或禁用右端的操作），雙端隊列功能就和棧一樣。禁
止調用insertLeft()和removeLeft()方法（或相反的另一對方法），他的功能就和隊列一樣了。
雙端隊列與棧或隊列相比，是一種多用途的數(shù)據(jù)結構，在容器類庫中有時會用雙端隊列來提供棧和隊列
的兩種功能。但是，雙端隊列 不像棧和隊列那常用。
優(yōu)先級隊列
優(yōu)先級隊列是比棧和隊列更專用的數(shù)據(jù)結構。但它在很多情況下都很有用。像普通隊列一樣，優(yōu)先級隊
列有一個對頭和一個隊尾，并且也是從對頭移出數(shù)據(jù)項。不過在優(yōu)先級隊列中，數(shù)據(jù)項按關鍵字的值有
序，這樣關鍵字最小的數(shù)據(jù)項（或者在某些實現(xiàn)中是關鍵最大的數(shù)據(jù)項）總是在隊列頭。數(shù)據(jù)項插入的
時候會按照順序插入到合適的位置以確保隊列的順序。
優(yōu)先級隊列的效率
優(yōu)先級隊列插入操作需要時間O(N)的時間，而刪除操作則需要O(1)的時間。