数据结构与算法（2）

四,栈和队列

栈
栈只允许访问一个数据项:即最后插入的数据项.移出这个数据项后才能访问倒数第二个插入的数据项,

以此类推.这种机制在不少编程环境中都很有用.

大部分微处理器运用基于栈的体系结构.当调用一个方法时,把它的返回地址和参数压入栈,当方法结束

返回时,那些数据出栈.栈操作就嵌入在微处理器中.

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)的时间。