import Ġjava . util .* Ċ Ċ // è¯· ä½ł ä»ħ ä½¿çĶ¨ ä¸¤ä¸ª éĺŁåĪĹ å®ŀçİ° ä¸Ģä¸ª åĲİ åħ¥ åħĪ åĩº ï¼Ī LI FO ï¼ī çļĦ æłĪ ï¼Į å¹¶ æĶ¯æĮģ æĻ®éĢļ éĺŁåĪĹ çļĦ åħ¨éĥ¨ åĽĽ ç§į æĵįä½ľ ï¼Ī push ãĢģ top ãĢģ pop ĠåĴĮ Ġempty ï¼īãĢĤ Ċ // Ċ // Ġ å®ŀçİ° ĠMy Stack Ġ ç±» ï¼ļ Ġ Ċ // Ċ // Ġ Ċ // Ġvoid Ġpush ( int Ġx ) Ġå°Ĩ åħĥç´ł Ġx Ġ åİĭ åħ¥ æłĪ é¡¶ ãĢĤ Ġ Ċ // Ġint Ġpop () Ġ ç§»éĻ¤ å¹¶ è¿ĶåĽŀ æłĪ é¡¶ åħĥç´ł ãĢĤ Ġ Ċ // Ġint Ġtop () Ġè¿ĶåĽŀ æłĪ é¡¶ åħĥç´ł ãĢĤ Ġ Ċ // Ġboolean Ġempty () Ġå¦Ĥæŀľ æłĪ æĺ¯ ç©º çļĦ ï¼Į è¿ĶåĽŀ Ġtrue Ġ ï¼Ľ åĲ¦åĪĻ ï¼Į è¿ĶåĽŀ Ġfalse ĠãĢĤ Ġ Ċ // Ġ Ċ // Ċ // Ġ Ċ // Ċ // Ġ æ³¨æĦı ï¼ļ Ġ Ċ // Ċ // Ġ Ċ // Ġ ä½ł åıªèĥ½ ä½¿çĶ¨ éĺŁåĪĹ çļĦ åŁºæľ¬ æĵįä½ľ ĠâĢĶ âĢĶ Ġ ä¹Łå°±æĺ¯ Ġpush Ġto Ġback ãĢģ peek / pop Ġfrom Ġfront ãĢģ size ĠåĴĮ Ġis Ġempty Ġ è¿ĻäºĽ æĵįä½ľ ãĢĤ Ġ Ċ // Ġ ä½ł æīĢ ä½¿çĶ¨çļĦ è¯Ńè¨Ģ ä¹Ł è®¸ ä¸į æĶ¯æĮģ éĺŁåĪĹ ãĢĤ Ġ ä½łåı¯ä»¥ ä½¿çĶ¨ Ġlist Ġï¼Ī åĪĹè¡¨ ï¼ī æĪĸèĢħ Ġdeque ï¼Ī åıĮ ç«¯ éĺŁåĪĹ ï¼ī æĿ¥ æ¨¡ æĭŁ ä¸Ģä¸ª éĺŁåĪĹ Ġ, Ġåıª è¦ģ æĺ¯ æłĩåĩĨ çļĦ éĺŁåĪĹ æĵįä½ľ åį³åı¯ ãĢĤ Ġ Ċ // Ġ Ċ // Ċ // Ġ Ċ // Ċ // Ġ ç¤ºä¾ĭ ï¼ļ Ġ Ċ // Ċ // Ġ Ċ // è¾ĵåħ¥ ï¼ļ Ċ // [" My Stack ", Ġ" push ", Ġ" push ", Ġ" top ", Ġ" pop ", Ġ" empty "] Ċ // [[ ], Ġ[ 1 ], Ġ[ 2 ], Ġ[], Ġ[], Ġ[] ] Ċ // è¾ĵåĩº ï¼ļ Ċ // [ null , Ġnull , Ġnull , Ġ 2 , Ġ 2 , Ġfalse ] Ċ // Ċ // è§£éĩĬ ï¼ļ Ċ // My Stack Ġmy Stack Ġ= Ġnew ĠMy Stack (); Ċ // my Stack . push ( 1 ); Ċ // my Stack . push ( 2 ); Ċ // my Stack . top (); Ġ// Ġè¿ĶåĽŀ Ġ 2 Ċ // my Stack . pop (); Ġ// Ġè¿ĶåĽŀ Ġ 2 Ċ // my Stack . empty (); Ġ// Ġè¿ĶåĽŀ ĠFalse Ċ // Ġ Ċ // Ċ // Ġ Ċ // Ċ // ĠæıĲ ç¤º ï¼ļ Ġ Ċ // Ċ // Ġ Ċ // Ġ 1 Ġ<= Ġx Ġ<= Ġ 9 Ġ Ċ // Ġ æľĢ å¤ļ è°ĥçĶ¨ 1 0 0 Ġæ ¬ ¡ Ġpush ãĢģ pop ãĢģ top ĠåĴĮ Ġempty Ġ Ċ // Ġæ¯ı æ¬¡ è°ĥçĶ¨ Ġpop ĠåĴĮ Ġtop Ġ éĥ½ ä¿Ŀè¯ģ æłĪ ä¸į ä¸ºç©º Ġ Ċ // Ġ Ċ // Ċ // Ġ Ċ // Ċ // Ġ è¿Ľ éĺ¶ ï¼ļ ä½ł èĥ½ åĲ¦ å®ŀçİ° æ¯ı ç§į æĵįä½ľ çļĦ åĿĩ æĳ Ĭ æĹ¶éĹ´ å¤įæĿĤ åº¦ ä¸º ĠO ( 1 ) ĠçļĦ æłĪ ï¼Ł æį¢ åı¥ è¯Ŀ è¯´ ï¼Į æī§è¡Į Ġn Ġä¸ª æĵįä½ľ çļĦ æĢ» æĹ¶éĹ´ å¤įæĿĤ åº¦ ĠO ( n ) Ġï¼Į å°½ ç®¡ åħ¶ä¸Ń æŁĲä¸ª æĵįä½ľ åı¯èĥ½ éľĢè¦ģ æ¯Ķ åħ¶ä»ĸ æĵįä½ľ æĽ´ éķ¿ çļĦ Ċ // æĹ¶éĹ´ ãĢĤ ä½łåı¯ä»¥ ä½¿çĶ¨ ä¸¤ä¸ª ä»¥ ä¸ĬçļĦ éĺŁåĪĹ ãĢĤ Ġ Ċ // ĠRelated ĠTop ics Ġ æłĪ Ġ è®¾è®¡ Ġ Ċ // ĠðŁĳį Ġ 2 7 4 ĠðŁĳ İ Ġ 0 ĊĊ Ċ // leetcode Ġsubmit Ġregion Ġbegin ( Pro hibit Ġmodification Ġand Ġdeletion ) Ċ class ĠMy Stack () Ġ{ ĊĊĠĠĠ Ġ// ç®Ĺæ³ķ ï¼ļ ä½¿çĶ¨ ä¸¤ä¸ª éĺŁåĪĹ æĿ¥ æ¨¡ æĭŁ æłĪ ï¼Į åıª ä¿Ŀè¯ģ ä¸Ģä¸ª éĺŁåĪĹ æľī æķ°æį® ï¼Į æľī æķ°æį® æĵįä½ľ åĪĻ åĩº éĺŁ æķ´ä¸ª æľī æķ°æį® éĺŁåĪĹ åĪ° åı¦ ä¸Ģä¸ª éĺŁåĪĹ ĊĊĊĠĠĠ Ġ/** ĠInitialize Ġyour Ġdata Ġstructure Ġhere . Ġ*/ ĊĊĠĠĠ Ġvar Ġdata 1 : LinkedList < Int > Ġ= ĠLinkedList < Int >() ĊĠĠĠ Ġvar Ġdata 2 : LinkedList < Int > Ġ= ĠLinkedList < Int >() ĊĊĊĠĠĠ Ġ/** ĠPush Ġelement Ġx Ġonto Ġstack . Ġ*/ ĊĠĠĠ Ġfun Ġpush ( x : ĠInt ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġif (! data 1 . isEmpty ()){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdata 1 . add Last ( x ) ĊĠĠĠĠĠĠĠ Ġ} else { ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdata 2 . add Last ( x ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĠRemoves Ġthe Ġelement Ġon Ġtop Ġof Ġthe Ġstack Ġand Ġreturns Ġthat Ġelement . Ġ*/ ĊĠĠĠ Ġ// æłĪ åħĪ è¿Ľ åĲİ åĩº ĊĠĠĠ Ġfun Ġpop (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif (! data 1 . isEmpty ()){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// å°Ĩ data 1 Ġæķ°æį® æĶ¾ åħ¥ Ġdate 2 Ġ çķĻ ä¸ĭ ä¸Ģä¸ª ä¾¿ æĺ¯ éĺŁåĪĹ æľĢåĲİ ä¸Ģä¸ª æķ° Ġ ä¹Łå°±æĺ¯ æ¨¡ æĭŁ æłĪ é¡¶ çļĦ æķ° ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( data 1 . size > 1 ){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata 2 . add Last ( data 1 . remove First ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdata 1 . remove First () ĊĠĠĠĠĠĠĠ Ġ} else { ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( data 2 . size > 1 ){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata 1 . add Last ( data 2 . remove First ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdata 2 . remove First () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĠGet Ġthe Ġtop Ġelement . Ġ*/ ĊĠĠĠ Ġfun Ġtop (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġtop Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġif (! data 1 . isEmpty ()){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// å°Ĩ data 1 Ġæķ°æį® æĶ¾ åħ¥ Ġdate 2 Ġ çķĻ ä¸ĭ ä¸Ģä¸ª ä¾¿ æĺ¯ éĺŁåĪĹ æľĢåĲİ ä¸Ģä¸ª æķ° Ġ ä¹Łå°±æĺ¯ æ¨¡ æĭŁ æłĪ é¡¶ çļĦ æķ° ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( data 1 . size > 1 ){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata 2 . add Last ( data 1 . remove First ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtop Ġ= Ġdata 1 . remove First () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdata 2 . add Last ( top ) ĊĠĠĠĠĠĠĠ Ġ} else { ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( data 2 . size > 1 ){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata 1 . add Last ( data 2 . remove First ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtop Ġ= Ġdata 2 . remove First () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdata 1 . add Last ( top ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġtop ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĠReturns Ġwhether Ġthe Ġstack Ġis Ġempty . Ġ*/ ĊĠĠĠ Ġfun Ġempty (): ĠBoolean Ġ{ ĊĠĠĠĠĠĠ Ġreturn Ġdata 1 . isEmpty () Ġ&& Ġdata 2 . isEmpty () ĊĠĠĠ Ġ} Ċ Ċ } Ċ Ċ /** Ċ Ġ* ĠYour ĠMy Stack Ġobject Ġwill Ġbe Ġinstantiated Ġand Ġcalled Ġas Ġsuch : Ċ Ġ* Ġvar Ġobj Ġ= ĠMy Stack () Ċ Ġ* Ġobj . push ( x ) Ċ Ġ* Ġvar Ġparam _ 2 Ġ= Ġobj . pop () Ċ Ġ* Ġvar Ġparam _ 3 Ġ= Ġobj . top () Ċ Ġ* Ġvar Ġparam _ 4 Ġ= Ġobj . empty () Ċ Ġ*/ Ċ // leetcode Ġsubmit Ġregion Ġend ( Pro hibit Ġmodification Ġand Ġdeletion ) Ċ