<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。隊列的應用：線性規劃方面
    
	
    
	


    
	    
    




    








    

				
			
    
		    		
	
    
	
    
		
			


		
	
    

    


    







    
        
	



主站蜘蛛池模板：
亚洲精品无码成人|
五月天婷婷免费视频|
亚洲国产一级在线观看|
韩国免费a级作爱片无码|
777亚洲精品乱码久久久久久|
毛片a级毛片免费观看免下载|
日韩大片免费观看视频播放
|
成年女人毛片免费观看97|
色视频在线观看免费|
久久99免费视频|
亚洲乱码无人区卡1卡2卡3|
亚洲中文字幕无码一区二区三区|
波多野结衣免费在线观看|
亚洲第一精品福利|
免费黄网在线观看|
嫩草成人永久免费观看|
亚洲AV无码一区二区三区性色
|
亚洲欧美日韩中文字幕一区二区三区|
亚洲免费无码在线|
最近的中文字幕大全免费版|
国产线视频精品免费观看视频|
亚洲熟女综合一区二区三区|
亚洲AV无码专区在线播放中文|
日韩免费电影在线观看|
131美女爱做免费毛片|
亚洲入口无毒网址你懂的|
亚洲午夜无码久久久久|
欧洲精品免费一区二区三区|
久久久久久曰本AV免费免费|
91在线视频免费观看|
www亚洲精品久久久乳|
亚洲一区二区三区深夜天堂|
亚洲精品乱码久久久久久|
中文在线免费看视频|
亚洲乱色熟女一区二区三区蜜臀|
久久久久亚洲AV成人片|
亚洲国产精品无码中文字|
亚洲欧洲日产国码一级毛片|
日韩免费观看视频|
最近的免费中文字幕视频|
无码国产精品一区二区免费式影视|