<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级毛片免费观看AV网站|
最刺激黄a大片免费网站|
最近免费中文字幕mv在线电影|
91嫩草免费国产永久入口|
国产曰批免费视频播放免费s|
青青在线久青草免费观看|
女性无套免费网站在线看|
热99re久久免费视精品频软件|
日韩在线看片免费人成视频播放|
国产大片51精品免费观看|
俄罗斯极品美女毛片免费播放|
亚洲av中文无码|
亚洲精品无码不卡在线播HE|
亚洲AV无码一区二区三区DV|
久久亚洲精品人成综合网|
国产亚洲精品成人AA片|
色欲aⅴ亚洲情无码AV|
亚欧洲精品在线视频免费观看|
免费黄网站在线观看|
AV无码免费永久在线观看|
在线观着免费观看国产黄|
亚洲精品国产日韩无码AV永久免费网
|
日本一区二区三区在线视频观看免费|
永久免费无码日韩视频|
久久青草91免费观看|
麻豆一区二区免费播放网站|
国产精品成人四虎免费视频|
综合亚洲伊人午夜网|
亚洲网站在线播放|
亚洲av成人一区二区三区在线播放|
caoporm超免费公开视频|
18禁男女爽爽爽午夜网站免费|
在线免费观看一级毛片|
老司机亚洲精品影视www|