データ構造の基礎_スタックとキュー

スタックとキューの話をするために、配列と比較して、データを迅速に挿入する利点がありますが、データを検索するときは、行列が来ないほど速いです.下のコードは配列でスタックを実現し、チェーンでキューを実現し、チェーンでスタックを実現します.
         配列でスタックを実現

package StackAndQueue;

/**
 *        
 * @author wly
 * @author 2013-10-23
 */
public class ArrayStack {
	
	Object[] array;
	int init_capcity = 12;
	int INCREATE_STEP = 12; //            
	int top = -1;
	
	public ArrayStack() {
		array = new Object[init_capcity];
	}
	
	public void push(Object obj) {
		if(top >= array.length) { //            ,      
			Object[] array2 = new Object[array.length + INCREATE_STEP];
			for(int i=0;i<array.length;i++) {
				array2[i] = array[i];
			}
			array = array2;
		}
		
		//          ，         
		top ++;
		array[top] = obj;
	}
	
	/**
	 *       
	 * @return
	 */
	public Object pop() {
		if(top >= 0) { //             
			Object topElement = array[top];
			top --;
			return topElement;
		} else {
			return null;
		}
	}
	
	/**
	 *       ，   
	 * @return
	 */
	public Object peek() {
		Object topElement = array[top];
		return topElement;
	}
}

           チェーンでスタックを実現する

package StackAndQueue;

/**
 *        ，       ，                  
 * @author wly
 * @date 2013-10-23
 */
public class ChainStack {
	Chain chain;
	
	public void push(Node node) {
		if(chain == null) {
			chain = new Chain();
		}
		chain.add(node);
	}
	
	public Node pop() {
	   return chain.remove();
	}
	
	public Node peek() {
		return chain.tail;
	}
}

/**
 *    
 * @author wly
 *
 */
class Chain {
	Node tail;
	
	
	public void add(Node node) {
		if(tail == null) {
			tail = node;
		} else {
			tail.setNext(node);
			tail = node;
		}
	}
	
	/**
	 *       ，          
	 * @return true     ,false     
	 */
	public Node remove() {
		Node result = tail;
		if(tail.prev != null) { 
			tail = tail.prev;
			tail.next = null;
		} else { //      
			tail = null;
		}
		return result;
	}
	
}

/**
 *    
 * @author wly
 *
 */
class Node {
	public Node next; //          
	public Node prev; //         
	
	public Object data;
	
	public Node(Object data) {
		this.data = data;
	}
	
	public void setNext(Node node) {
		node.prev = this;
		this.next = node;
	}
}

            チェーンで列を実現します.

package StackAndQueue;

/**
 *         
 * @author wly
 *
 */
public class ChainQueue {
	private QueueNode head; //       
	private QueueNode tail; //       
	
	private int size = 0;
	
	public ChainQueue() {
		
	}
	
	/**
	 *          
	 */
	public void insert(QueueNode node) {
			

//#######          ######
//      head.prev null，    remove peek   head.prev       
//		if(head == null) {
//			head = node;
//			tail = head;
//		} else {
//			node.next = tail;
//			tail = node;
//		}
		
//		if(isEmpty()){
//			tail = node;
//			head = tail;
//			
//			if(tail == head) {
//				System.out.println("--same--");
//			}
//		} else {
//			tail.prev = node;
//			tail = node;
//		}
		
//        ,  tail.prev = node
	if(head == null) {
		head = node;
		tail = head;
	} else {
		node.next = tail;
		tail.prev = node; //    ，  head.prev   
		tail = node;
	}
		
		size ++;
	}
	
	/**
	 *        
	 */
	public QueueNode remove() {
		if(!isEmpty()) {
			QueueNode temp = head;
			head = head.prev;
			size --;
			return temp;
		} else {
			System.out.println("    ，      !");
			return null;
		}
	}
	
	/**
	 *       
	 * @return
	 */
	public boolean isEmpty() {
		if(size > 0) {
			return false;
		} else {
			return true;
		}
	}
	
	/**
	 *        ，    
	 */
	public QueueNode peek() {
		if(!isEmpty()) {
			return head;
		} else {
			System.out.println();System.out.println("    ，      !");
			return null;
		}
	}
	
	
	/**
	 *       
	 * @return
	 */
	public int size() {
		return size;
	}
}

/**
 *    
 * @author wly
 *
 */
class QueueNode {
	QueueNode prev;
	QueueNode next;
	
	int data;
	
	public QueueNode(int data) {
		this.data = data;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}
}

             テストします

package StackAndQueue;

public class Test {

	public static void main(String[] args) {
		
		//-----         -------
		System.out.println("-----         ");
		ArrayStack arrayStack = new ArrayStack();
		arrayStack.push("  ");
		arrayStack.push("  ");
		System.out.println(arrayStack.pop().toString()); //  
		System.out.println(arrayStack.peek().toString()); //  
		System.out.println(arrayStack.pop().toString()); //  
		System.out.println("--------------
");
		
		
		//-----         --------
		System.out.println("-----         ");
		ChainStack chainStack = new ChainStack();
		Node n1 = new Node("  ");
		Node n2 = new Node("  ");
		chainStack.push(n1);
		chainStack.push(n2);
		System.out.println(chainStack.pop().data.toString());
		System.out.println(chainStack.peek().data.toString());
		System.out.println(chainStack.pop().data.toString());
		System.out.println("--------------
");
		
		
		//-----          --------
		System.out.println("-----          ");
		QueueNode qnode1 = new QueueNode(123);
		QueueNode qnode2 = new QueueNode(666);
		ChainQueue chainQueue = new ChainQueue();
		chainQueue.insert(qnode1);
		chainQueue.insert(qnode2);
		System.out.println(chainQueue.remove().getData());
		System.out.println(chainQueue.peek().getData());
		System.out.println(chainQueue.remove().getData());
		System.out.println("--------------
");
		
		
		//  ，        ~~~
		//             ，               (      )，   ArrayList    ，  ~~~
		//        ，          。
		//      ：       n，    1 2 3 4 ... n   ，       ，           
		//             ，                 ？
		ChainQueue chainQueue2 = new ChainQueue();
		for(int i=1;i<=5;i++) {
			QueueNode qn = new QueueNode(i);
			chainQueue2.insert(qn);
		}
		while(chainQueue2.size() > 1) {
			chainQueue2.remove();
			if(chainQueue2.size() > 1) {
				chainQueue2.insert(chainQueue2.remove());
			} else {
				//    
				System.out.println("      ------:");
				System.out.print(chainQueue2.peek().getData());
			}
		}
	}
}

            最後に、その面接を紹介します.私はやはり重視しています.面接前にいろいろ準備しました.現場に来てよかったです.英語の文書を読む習慣があるので、面接官は英語で質問したことは大体分かりましたが、自分で英語で話した時にはうまくいかなかったです.後の問題は前の文のコードの中のそれが列で実現するテーマです.データ構造という本はまったく見たことがないからです.その後、アラーリストで20分ぐらいかかりました.面接官が試験したのはデータ構造かもしれません.自分で列を書いていないので、プログラムの調整とコードの仕様について聞きました.一つ一つ答えましたが、いい感じです.それからまたプロジェクトマネージャーが来ました.これはアウトソーシング会社ですか?そして彼は私にAndroidをやったことがあるのかと聞きました.オフショアだから今後何をするべきかを強調しました.何を学ぶべきかを迷っています.基礎がよくないと思いますが、要求された給料は低くないですよね.でも、力を尽くしたと思います.(その日の5時に退勤したら、寧波から杭州まで列車に乗ります.それから乗り換えて、夜9時半に着くホテルで、シャワーを浴びてからまた英語ができます.えっと.)
           でも、収穫があります.仕事を探す新人に参考になるポイントをまとめます.
           一、あなた自身が確かに牛(素晴らしいスタートプロジェクトをしました.ACM一等賞などはもう有名です.)でない限り、積極的に電話してあなたの会社を探しに来ます.
           二、卒業したばかりで、何もできないなら、小さい会社に行ってもいいです.ある程度のレベル(10万行ぐらいのコードを書きました)があれば、大企業に行きましょう.大企業は規範的なものがたくさんあります.
           三、会社からあなたに給料を上げるとは思わないでください.もし給料が気になるなら、努力して自分を高めましょう.あなたのレベルがもっと高い報酬を受けるべきだと思う時、普通の会社はあなたにプラスします.あなたは転職できます.主導権を持っています.
      
           O啦~~
           転載は出典を保留してください.http://blog.csdn.net/u011638883/article/details/14107863
           ありがとうございます.