莊周夢蝶
          
			生活、程序、未來
		          		
	
          

          

          

          
	
          
	
 
 ::
首頁 ::
 ::
 ::
聚合
 ::
管理


          
		          		
	
          
	
          
		
			
          
			
          
		          		
		
			
          
				
					
	
          
		
          
			
          
				數據結構之棧與隊列 
			
          
 			Posted on 2007-02-20 12:51 dennis 閱讀(693) 評論(0)  編輯  收藏  所屬分類: 數據結構與算法 
			
			


		
          
		
          一。棧
          1。概念：棧（stack）是一種線性數據結構，只能訪問它的一端來存儲或者讀取數據。棧是一種后進先出的結構（LIFO)
          2。棧的主要操作：
          .clear()——清棧
          .isEmpty()——檢查棧是否為空
          .push(e)——壓棧
          .pop()——出棧
          .topEl()——返回棧頂元素

          3。棧的java實現：使用數組鏈表實現

          /**
          ?*?
          ?          */
          package?com.sohu.blog.denns_zane.stackqueue;

          /**
          ?*?          @author?dennis
          ?*?
          ?          */
          public?abstract?class?AbstractStack?{
          ????          public?abstract?Object?pop();

          ????          public?abstract?void?push(Object?obj);

          ????          public?abstract?Object?topEl();

          ????          public?abstract?boolean?isEmpty();

          ????          public?abstract?void?clear();
          }


          /**
          ?*?
          ?          */
          package?com.sohu.blog.denns_zane.stackqueue;

          /**
          ?*?          @author?dennis
          ?*?
          ?          */
          public?class?Stack?extends?AbstractStack?{
          ????          private?java.util.ArrayList?pool?=?new?java.util.ArrayList();

          ????          public?Stack()?{
          ????}

          ????          public?Stack(int?n)?{
          ????????pool.ensureCapacity(n);
          ????}

          ????          public?void?clear()?{
          ????????pool.clear();
          ????}

          ????          public?boolean?isEmpty()?{
          ????????          return?pool.isEmpty();
          ????}

          ????          public?Object?topEl()?{
          ????????          if?(isEmpty())
          ????????????          throw?new?java.util.EmptyStackException();
          ????????          return?pool.get(pool.size()?-?1);
          ????}

          ????          public?Object?pop()?{
          ????????          if?(isEmpty())
          ????????????          throw?new?java.util.EmptyStackException();
          ????????          return?pool.remove(pool.size()?-?1);
          ????}

          ????          public?void?push(Object?el)?{
          ????????pool.add(el);
          ????}

          ????          public?String?toString()?{
          ????????          return?pool.toString();
          ????}
          }

          4。棧的應用：
          1）程序中的匹配分割符，如(,[,{等符號
          2）大數的運算，比如大數相加，轉化為字符串，利用棧處理
          3）回文字，例子：
          /**
          ?*?
          ?          */
          package?com.sohu.blog.denns_zane.stackqueue;

          import?java.io.BufferedReader;
          import?java.io.IOException;
          import?java.io.InputStreamReader;

          /**
          ?*?          @author?dennis
          ?*?
          ?          */
          public?class?HuiWen?{

          ????          /**
          ?????*?          @param?args
          ?????          */
          ????          public?static?void?main(String[]?args)?{
          ????????BufferedReader?buffer?          =?new?BufferedReader(new?InputStreamReader(
          ????????????????System.in));
          ????????          try?{
          ????????????String?str?          =?buffer.readLine();
          ????????????          if?(str?!=?null)
          ????????????????isHuiWen(str);

          ????????}          ?catch?(IOException?e)?{
          ????????????e.printStackTrace();
          ????????}
          ????????          //?TODO?Auto-generated?method?stub

          ????}

          ????          public?static?void?isHuiWen(String?str)?{
          ????????          int?length?=?str.length();
          ????????          char[]?ch?=?str.toCharArray();
          ????????Stack?stack?          =?new?Stack();
          ????????          if?(length?%?2?==?0)?{
          ????????????          for?(int?i?=?0;?i?<?length?/?2;?i++)?{
          ????????????????stack.push(ch[i]);
          ????????????}
          ????????????          for?(int?i?=?length?/?2;?i?<?length?-?1;?i++)?{
          ????????????????          if?(ch[i]?!=?((Character)?stack.pop()).charValue())?{
          ????????????????????System.out.println(          "不是回文字！！");
          ????????????????????          return;
          ????????????????}

          ????????????}

          ????????????System.out.println(str?          +?"是回文字！！");
          ????????}          ?else?{
          ????????????          for?(int?i?=?0;?i?<?length?/?2;?i++)?{
          ????????????????stack.push(ch[i]);
          ????????????}
          ????????????          for?(int?i?=?(length?/?2?+?1);?i?<?length?-?1;?i++)?{
          ????????????????          if?(ch[i]?!=?((Character)?stack.pop()).charValue())?{
          ????????????????????System.out.println(          "不是回文字！！");
          ????????????????????          return;
          ????????????????}
          ????????????}
          ????????????System.out.println(str?          +?"是回文字！！");
          ????????}

          ????}

          }

          4）java虛擬機中的本地方法棧


          二。隊列（queue）
          1。概念：隊列也是線性結構，從尾部添加元素，從頭部刪除元素。與棧相反，隊列是先入先出結構（FIFO）
          2。隊列主要操作：
          .clear() ——清空隊列
          .isEmpty()——判斷隊列是否為空
          .enqueue(el)——從尾部插入元素el
          .dequeue()——從隊列中起出第一個元素，并刪除
          .firstEl()——返回隊列第一個元素，不刪除。

          3。隊列的實現：
          1）環形數組：需要考慮隊列已滿的兩種情況，1，第一個元素在最后一個元素之后；2，第一個元素在第一單元，最后一個元素在最后單元。給出一個java實現：
          /**
          ?*?
          ?          */
          package?com.sohu.blog.denns_zane.stackqueue;

          /**
          ?*?          @author?dennis
          ?*?
          ?          */
          //?queue?implemented?as?an?array
          public?class?ArrayQueue?{
          ????          private?int?first,?last,?size;

          ????          private?Object[]?storage;

          ????          public?ArrayQueue()?{
          ????????          this(100);
          ????}

          ????          public?ArrayQueue(int?n)?{
          ????????size?          =?n;
          ????????storage?          =?new?Object[size];
          ????????first?          =?last?=?-1;
          ????}

          ????          public?boolean?isFull()?{
          ????????          return?first?==?0?&&?last?==?size?-?1?||?first?==?last?+?1;
          ????}

          ????          public?boolean?isEmpty()?{
          ????????          return?first?==?-1;
          ????}

          ????          public?void?enqueue(Object?el)?{
          ????????          if?(last?==?size?-?1?||?last?==?-1)?{
          ????????????storage[          0]?=?el;
          ????????????last?          =?0;
          ????????????          if?(first?==?-1)
          ????????????????first?          =?0;
          ????????}          ?else
          ????????????storage[          ++last]?=?el;
          ????}

          ????          public?Object?dequeue()?{
          ????????Object?tmp?          =?storage[first];
          ????????          if?(first?==?last)
          ????????????last?          =?first?=?-1;
          ????????          else?if?(first?==?size?-?1)
          ????????????first?          =?0;
          ????????          else
          ????????????first          ++;
          ????????          return?tmp;
          ????}

          ????          public?void?printAll()?{
          ????????          for?(int?i?=?0;?i?<?size;?i++)
          ????????????System.out.print(storage[i]?          +?"?");
          ????}
          }

          2）更適合實現隊列的雙向鏈表：
          /**
          ?*?
          ?          */
          package?com.sohu.blog.denns_zane.stackqueue;

          /**
          ?*?          @author?dennis
          ?*?
          ?          */
          public?class?Queue?{
          ????          private?java.util.LinkedList?list?=?new?java.util.LinkedList();

          ????          public?Queue()?{
          ????}

          ????          public?void?clear()?{
          ????????list.clear();
          ????}

          ????          public?boolean?isEmpty()?{
          ????????          return?list.isEmpty();
          ????}

          ????          public?Object?firstEl()?{
          ????????          return?list.getFirst();
          ????}

          ????          public?Object?dequeue()?{
          ????????          return?list.removeFirst();
          ????}

          ????          public?void?enqueue(Object?el)?{
          ????????list.add(el);
          ????}

          ????          public?String?toString()?{
          ????????          return?list.toString();
          ????}


          }

          4。隊列的應用：線性規劃方面
          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          


    







          
        
	




主站蜘蛛池模板：
孝昌县|
镇巴县|
米泉市|
搜索|
湘潭市|
怀宁县|
浦江县|
黔南|
临桂县|
隆子县|
巫溪县|
嵊州市|
渝北区|
泽库县|
东阿县|
平南县|
金秀|
海伦市|
肇源县|
东平县|
徐闻县|
海盐县|
紫金县|
汝南县|
九台市|
沙河市|
定西市|
旬邑县|
登封市|
连城县|
通辽市|
柯坪县|
滨州市|
米林县|
岳阳县|
克拉玛依市|
上栗县|
新龙县|
哈巴河县|
洞头县|
扶绥县|