<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        



    
	
    
		
			

    

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

    

    

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


    
		    		
	
    
	
    
		
			
    
			
    
		    		
		
			
    
				
					
	
    
		
    
			
    
				數據結構之棧與隊列 
			
    
 			Posted on 2007-02-20 12:51 dennis 閱讀(690) 評論(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。隊列的應用：線性規劃方面
    
	
    
	


    
	    
    




    








    

				
			
    
		    		
	
    
	
    
		
			


		
	
    

    


    







    
        
	



主站蜘蛛池模板：
成年女人午夜毛片免费看|
国产在线98福利播放视频免费|
秋霞人成在线观看免费视频
|
国产免费A∨在线播放|
日韩国产免费一区二区三区|
亚洲成年看片在线观看|
亚洲国产成人精品无码一区二区|
jizz中国免费|
免费鲁丝片一级观看|
亚洲黄色在线电影|
中文字幕不卡高清免费|
日本视频免费在线|
亚洲午夜精品在线|
拨牐拨牐x8免费|
香港特级三A毛片免费观看|
在线观看无码AV网站永久免费
|
免费一本色道久久一区|
亚洲AV综合色一区二区三区|
黄页网站在线视频免费|
久久精品国产亚洲5555|
四虎影视久久久免费观看|
日韩a在线观看免费观看|
有色视频在线观看免费高清在线直播
|
久99久精品免费视频热77|
国产日韩成人亚洲丁香婷婷|
大地影院MV在线观看视频免费|
亚洲精品天堂成人片?V在线播放|
亚洲成a人片在线不卡一二三区|
一个人在线观看视频免费|
羞羞的视频在线免费观看|
亚洲国产精品SSS在线观看AV|
eeuss影院免费直达入口|
亚洲欧洲日韩不卡|
99精品视频在线视频免费观看
|
久久久久亚洲AV无码专区网站
|
国产一级黄片儿免费看|
亚洲性线免费观看视频成熟|
亚洲一级毛片免费观看|
亚洲第一永久在线观看|
成人福利免费视频|
亚洲国产成人精品激情|