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


    
	    
    




    








    

				
			
    
		    		
	
    
	
    
		
			


		
	
    

    


    







    
        
	



主站蜘蛛池模板：
18女人腿打开无遮掩免费|
人人爽人人爽人人片av免费
|
亚洲综合久久夜AV |
亚洲精品动漫免费二区|
欧美男同gv免费网站观看|
亚洲av片不卡无码久久|
亚洲免费福利视频|
亚洲一区二区三区久久|
99精品国产免费久久久久久下载|
亚洲av乱码一区二区三区香蕉|
波多野结衣中文字幕免费视频|
久久精品国产亚洲AV蜜臀色欲|
成年女人毛片免费播放人|
亚洲人成色77777在线观看|
国产精品黄页在线播放免费|
亚洲jizzjizz少妇|
亚洲精品麻豆av|
免费人成视频在线观看网站|
亚洲精品视频观看|
成年女人免费视频播放体验区|
亚洲国产精品精华液|
亚洲AV之男人的天堂|
免费无码作爱视频|
国产成人免费A在线视频|
麻豆va在线精品免费播放|
99精品免费观看|
亚洲六月丁香六月婷婷蜜芽|
欧洲精品免费一区二区三区|
国产无遮挡色视频免费观看性色|
国产精品免费看香蕉|
一本久久免费视频|
亚洲美女大bbbbbbbbb|
日韩精品视频免费在线观看|
国产成人精品免费视频大全|
久久久久亚洲AV无码网站|
免费高清在线影片一区|
free哆拍拍免费永久视频
|
99久久国产亚洲综合精品|
亚洲AV永久无码精品一区二区国产
|
亚洲综合精品第一页|
亚洲综合精品香蕉久久网|