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

          

          

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


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

          3。棧的java實現(xiàn)：使用數(shù)組鏈表實現(xiàn)

          /**
          ?*?
          ?          */
          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。棧的應(yīng)用：
          1）程序中的匹配分割符，如(,[,{等符號
          2）大數(shù)的運算，比如大數(shù)相加，轉(zhuǎn)化為字符串，利用棧處理
          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。概念：隊列也是線性結(jié)構(gòu)，從尾部添加元素，從頭部刪除元素。與棧相反，隊列是先入先出結(jié)構(gòu)（FIFO）
          2。隊列主要操作：
          .clear() ——清空隊列
          .isEmpty()——判斷隊列是否為空
          .enqueue(el)——從尾部插入元素el
          .dequeue()——從隊列中起出第一個元素，并刪除
          .firstEl()——返回隊列第一個元素，不刪除。

          3。隊列的實現(xiàn)：
          1）環(huán)形數(shù)組：需要考慮隊列已滿的兩種情況，1，第一個元素在最后一個元素之后；2，第一個元素在第一單元，最后一個元素在最后單元。給出一個java實現(xiàn)：
          /**
          ?*?
          ?          */
          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）更適合實現(xiàn)隊列的雙向鏈表：
          /**
          ?*?
          ?          */
          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。隊列的應(yīng)用：線性規(guī)劃方面
          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          


    







          
        
	




主站蜘蛛池模板：
南雄市|
江口县|
汕尾市|
沛县|
铜川市|
惠水县|
安达市|
泸定县|
鹤壁市|
宝鸡市|
依安县|
龙海市|
丹江口市|
汶川县|
西畴县|
凤山县|
泗水县|
新郑市|
罗源县|
太谷县|
达日县|
雷波县|
淮滨县|
芦溪县|
临潭县|
建宁县|
大庆市|
新营市|
鄂州市|
桑日县|
上栗县|
曲水县|
读书|
常州市|
赤壁市|
剑河县|
黄陵县|
康马县|
旬阳县|
大同市|
二连浩特市|