webhostinggeeks.com

У гэтым раздзеле пад капітальнае будаўніцтва.

Стэкі і чэргі.

У гэтым раздзеле мы ўводзяцца два цесна звязаных тыпаў дадзеных для кіравання калі заўгодна вялікіх калекцый аб'ектаў: стэк і чарга. Кожны вызначаецца двума асноўнымі аперацыямі: ўключыць новы пункт, і выдаліць элемент. Калі мы ўстаўляем пункт, нашы намеры ясныя. Але калі мы выдалення элемента, які з іх выбраць? Правіла, якое выкарыстоўваецца для чарзе, каб заўсёды выдалення элемента, які быў у калекцыі больш за ўсё часу. Гэтая палітыка вядомая як першы ў першы выйшаў або FIFO. Правіла, якое выкарыстоўваецца для стэка заўсёды выдалення элемента, які быў у калекцыі найменшую колькасць часу. Гэтая палітыка вядомая як апошні ў першым-аўт або ЛИФО.

Крамнага стэкаў.

Крамнага стэка (ці проста стэк) уяўляе сабой калекцыю, заснаваную на апошніх-у-першы выйшаў (LIFO) палітыкі. Пры пераходзе па спасылцы, Ваш браўзэр адлюстроўвае новую старонку (і ўстаўляе яго ў стэк). Вы можаце захаваць націснуўшы на гіперспасылкі, каб наведаць новыя старонкі. Вы заўсёды можаце вярнуцца на папярэднюю старонку, націснуўшы кнопку назад (выдаліць яго з стэка). Лифо палітыкі, прапанаваныя крамнага стэк забяспечвае толькі паводзіны, якое вы чакаеце.

Па традыцыі, мы называем метадам ўстаўкі стэка Push () і стэк аперацыяй выдалення поп (). Мы таксама ўключаюць метад для праверкі таго, стэк пусты. Наступныя API сумуе аперацыі:

Зорачка паказвае, што мы будзем разглядаць больш за адну рэалізацыі гэтага API.

Масіў рэалізацыі.

Прадстаўляючы складаецца з масівамі натуральная ідэя. Першая праблема, з якімі можна сутыкнуцца рэалізуе канструктар ArrayStackOfStrings (). Пераменная асобніка [] з масівам радкоў правесці стэк пунктаў відавочна, што неабходна, але, наколькі вялікі павінна быць? На дадзены момант, мы будзем тонкасці гэтай праблемы, якія маюць кліента прадаставіць аргумент для канструктара, што дае максімальны памер стэка. Мы працягваем элементы ў зваротным парадку іх паступлення. Гэтая палітыка дазваляе дадаваць і выдаляць элементы ў канцы без перамяшчэння якіх-небудзь іншых элементаў у стэку.

Мы наўрад ці надзея на больш просты рэалізацыі ArrayStackOfStrings.java : усе метады жартамі! Напрыклад зменныя масіва [], якія ўтрымліваюць элементы ў стэк і цэлае N, якая падлічвае колькасць элементаў у стэку. Каб выдаліць элемент, мы декремента N, а затым вярнуцца [N];, каб ўставіць новы элемент, пакладзем [N] роўна новы элемент, а затым прырост N. Гэтыя аперацыі захоўваюць наступнымі ўласцівасцямі: элементы ў масіве знаходзяцца ў парадку іх дадання стэк пусты, калі значэнне N роўна 0 вяршыню стэка (калі яно не пуста) знаходзіцца на [N-1]

Асноўнай характарыстыкай дадзенай рэалізацыі з'яўляецца тое, што штуршок і поп аперацыі маюць фіксаваны час. Недахоп гэтай рэалізацыі ў тым, што яна патрабуе кліенту ацаніць максімальны памер стэка загадзя і заўсёды выкарыстоўвае прастору прапарцыйна, што максімум, які можа быць неразумнымі ў некаторых сітуацыях.

Змяненні, спісы.

Для класаў, такіх як стэкі, якія рэалізуюць калекцыі аб'ектаў, важнай задачай з'яўляецца забеспячэнне таго, аб'ём прасторы, які выкарыстоўваецца заўсёды прапарцыйны колькасці элементаў у калекцыі. Зараз разгледзім выкарыстанне фундаментальнай структуры дадзеных, вядомых як звязаны спіс, які можа забяспечыць рэалізацыі калекцый (і, у прыватнасці, стэкі), які дасягае гэтай важнай мэты.

Звязаны спіс рэкурсіўнае структуры дадзеных вызначаецца наступным чынам: звязаны спіс або пуста (нуль) або спасылку на вузел, якія маюць спасылкі на звязаны спіс. Вузел у гэтым вызначэнні з'яўляецца абстрактным аб'ектам, які можа правесці любы від дадзеных у дадатак да вузла спасылку, якая характарызуе яго роля ў стварэнні звязаных спісаў. З аб'ектна-арыентаванага праграмавання, рэалізацыя звязаных спісаў не складана. Пачнем з простага прыкладу клас для вузла абстракцыі:

class Node { 
   String item; 
   Node next; 
} 
Вузел складаецца з двух зменных асобніка: струнных і Node. Радок запаўняльніка ў гэтым прыкладам для любых дадзеных, якія мы маглі б структура з звязаны спіс (мы можам выкарыстоўваць любы набор зменных асобніка); зменнай асобніка тыпу вузла характарызуе звязаны характар структуры дадзеных. Зараз з рэкурсіўнае вызначэнне, мы можам прадставіць звязаны спіс на зменную тыпу вузла проста, гарантуючы, што яго значэнне з'яўляецца або нулявым або спасылкі на вузле якога наступнае поле з'яўляецца спасылкай на звязаны спіс.
Мы ствараем аб'ект тыпу вузла, выклікаючы яго (без аргументаў) канструктара. Гэта стварае спасылку на вузле аб'екта, напрыклад зменныя і ініцыялізуецца значэннем NULL. Напрыклад, каб пабудаваць складны спіс, які змяшчае пункты "у", "быць", і "ці" мы ствараем вузлоў для кожнага элементы:
Node first  = new Node(); 
 Node second = new Node(); 
  Node third  = new Node();   
і ўсталяваць поле элемента ў кожным з вузлоў да патрэбнага пункта значэнне:
first.item  = "to";   second.item = "be";   third.item  = "or";  
і ўсталяваць наступныя палі для стварэння звязанага спісу:
first.next  = second; 
  second.next = third; 
  third.next  = null;  
Пры трасіроўкі кода, які выкарыстоўвае звязаныя спісы і іншыя звязаныя структуры, мы выкарыстоўваем візуальнае прадстаўленне змены, дзе мы малюем прастакутнік для прадстаўлення кожнага аб'екта пакласці значэння зменных асобніка ў прастакутнік мы малююць спасылак у выглядзе стрэлак, якія паказваюць на паказаны аб'ект Гэта візуальнае прадстаўленне адлюстроўвае істотную характарыстыку звязаныя спісы і дазваляе нам засяродзіцца на спасылкі.
Уставіць. Выкажам здагадку, што вы хочаце ўставіць новы вузел у звязаным спісе. Лягчэй за ўсё зрабіць гэта ў пачатку спісу. Напрыклад, каб ўставіць радок "не" у пачатку дадзенага звязанага спісу, першы вузел-першае, мы эканомім першы ў oldfirst, прызначылі першым новым вузлом, назначце яго пункт полі "не" і яго наступным полі oldfirst.
Выдаліць. Выкажам здагадку, што вы хочаце выдаліць первый вузел з спісу. Гэтая аперацыя стала яшчэ прасцей: проста прысвоіць першае значэнне first.next. Як правіла, вы павінны атрымаць значэнне элемента (шляхам прызначэння яго на некаторыя радкі зменнай), перш чым рабіць гэта прызначэнне, таму што як толькі вы зменіце значэнне па-першае, вы не можаце мець ніякага доступу да вузла, да якога ён меў на ўвазе. Як правіла, вузел аб'ект становіцца сіратой, і памяць, якую ён займае, у рэшце рэшт утылізаваны ў сістэме кіравання памяццю Java.
Гэтыя дзве аперацыі маюць пастаяннае час (залежыць ад даўжыні спісу).
Рэалізацыя стэкаў са звязанымі спісамі.
Праграма LinkedStackOfStrings.java выкарыстоўвае звязаны спіс для рэалізацыі стэка радкоў. Рэалізацыя заснавана на ўкладзены вузел класа, як той, які мы выкарысталі. Java дазваляе вызначыць і выкарыстоўваць іншыя класы ў рамках рэалізацыі класа ў гэтым натуральным чынам. Клас прыватных, так як кліенты не трэба ведаць ніякіх дэталяў звязаных спісаў.

Спіс абыходу.
Адзін з самых распаўсюджаных аперацый мы выконваем ў калекцыях для перабору элементаў калекцыі. Напрыклад, мы, магчыма, пажадае ажыццяўляць ToString () для спрашчэння адладкі наш стэк код са слядамі. Для ArrayStackOfStrings, гэтая рэалізацыя знакам:
public String toString() 
{      String s = "";      
for (int i = 0; i < N; i++)  
       s += a[i] + " ";    
  return s;   }   
Як звычайна, гэта рашэнне прызначана для выкарыстання толькі тады, калі N мала - патрабуецца квадратычны час, таму што аб'яднанне строк займае лінейнае час. У цэнтры нашай увагі зараз знаходзіцца толькі на стадыі разгляду кожнага пункта. Існуе адпаведная ідыёмы для наведвання элементаў у звязаным спісе: Мы ініцыялізуем індэкс цыклу зменнай х, які спасылаецца на першы вузел звязанага спісу. Затым, мы знаходзім значэнне элемента, звязанага з х, зайшоўшы x.item, а затым абнавіць х для абазначэння наступнага вузла ў звязаны спіс прысваення ёй значэння x.next, паўтараючы гэты працэс, пакуль х з'яўляецца нулявым ( які паказвае, што мы дасягнулі канца звязанага спісу). Гэты працэс вядомы як абыход спісу, і коратка выказаў у гэтай рэалізацыі ToString () для LinkedStackOfStrings:
public String toString()
 {      String s = "";  
    for (Node x = first;
 x != null; x = x.next) 
        s += x.item + " ";    
  return s;   }   
Масіў падваеньня.
Далей мы разгледзім падыход да размяшчэння адвольны рост і спад прапановы на структуру дадзеных, якая з'яўляецца прывабнай альтэрнатывай для звязаных спісаў. Як і звязаныя спісы, ідэя заключаецца ў змене рэалізацыі масіваў дынамічна наладжваць памер масіва [], каб ён (я) як досыць вялікі для захоўвання ўсіх прадметаў і (II), не настолькі вялікія, каб адыходы празмернае колькасць прасторы. Праграма DoublingStackOfStrings.java з'яўляецца мадыфікацыяй ArrayStackOfStrings.java, якая дасягае гэтых мэтаў.
Па-першае, у штуршку (), мы правяраем масіў занадта малы. У прыватнасці, мы правяраем, ці ёсць месца для новага элемента ў масіве шляхам праверкі памер стэка N роўная a.length памер масіва. Калі няма, то проста устаўце яго [N + +] = пункт як і раней, калі гэта так, мы падвойвае памер масіва, ствараючы новы масіў у два разы больш, капіяванне стэк элементаў новага масіва і скід [] пераменная асобніка для спасылкі на новы масіў. Акрамя таго, у поп-(), мы пачынаем з праверкі, ці з'яўляецца масіў занадта вялікі, і мы яго памер ўдвая, калі справа ідзе менавіта так.
Параметризованные тыпы дадзеных.
Мы распрацаваў адзін стэк рэалізацыя, якая дазваляе нам будаваць стэк аднаго пэўнага тыпу (String). У іншых прыкладаннях, мы, магчыма, спатрэбіцца стэк цэлых лікаў або стос апельсіны ці чэргі пакупнікоў.
Стварыць стэк аб'ектаў. Мы маглі б распрацаваць адной чаркі рэалізацыі StackOfObjects.java, элементы якога маюць тып Object. Выкарыстанне атрымання ў спадчыну, мы можам ўставіць аб'ект любога тыпу. Аднак, калі мы поп, мы павінны прывесці яго да адпаведнага тыпу. Такі падыход можа пацягнуць узнікненне ў нас тонкія памылкі ў нашых праграмах, якія не могуць быць выяўлены толькі падчас выканання. Напрыклад, няма нічога, каб спыніць праграміста ад здачы розныя тыпы аб'ектаў на тым жа стэку, то сутыкаецца выканання праверкі тыпу памылкі, як у наступным прыкладзе:
StackOfObjects stack = new StackOfObjects(); 
 Apple  a = new Apple();
  Orange b = new Orange(); 
 stack.push(a);  stack.push(b); 
 a = (Apple)  (stack.pop()); 
  // throws a ClassCastException  b = (Orange) (stack.pop());  
Гэтая цацка прыкладзе асноўная праблема. Калі мы выкарыстоўваем тып ліцця з рэалізацыі, такія як стэк для розных тыпаў элементаў, мы мяркуем, што кліенты будуць адкідаць аб'екты здабываюцца з стэка для адпаведнага тыпу. Гэта невідавочнае здагадка супярэчыць нашым патрабаваннем для АТД, што аперацыі, якія павінны быць даступныя толькі праз відавочны інтэрфейс. Адна з прычын, што праграмісты выкарыстоўваюць дакладна вызначаных АТД з'яўляецца абарона будучых кліентаў ад памылак, якія ўзнікаюць з такіх няяўных дапушчэнняў. Код не можа быць тыпу правяраецца падчас кампіляцыі: не можа быць няправільным адценне, які адбываецца ў складаны кавалак кода, якія маглі б застацца незаўважанымі, пакуль які-небудзь канкрэтных абставінах выканання ўзнікае. Такія памылкі, якіх варта пазбягаць любой цаной, таму што гэта можа адбыцца неўзабаве пасля рэалізацыі дастаўляецца кліенту, хто б ніякай магчымасці гэта выправіць.
Java-дженеріков. Мы выкарыстоўваем Java-дженеріков для абмежавання аб'ектаў на стэк або чаргу, каб усе яны аднаго і таго ж тыпу ў межах дадзенага прыкладання. Асноўная перавага заключаецца ў выяўленні памылкі неадпаведнасці тыпаў падчас кампіляцыі, а не падчас выканання. Гэта ўключае ў сябе невялікі фрагмент сінтаксісу новых Java. Мы называем агульным Стэк класа. Яна ідэнтычная StackOfStrings выключэннем таго, што мы заменім усе ўваходжанні радкі з пунктам і абвясціць клас наступным чынам:
 грамадскіх <Item> Стэк клас 
Праграма Stack.java рэалізуе агульны стэк з дапамогай гэтага падыходу. Кліент
Stack<Apple> stack = new Stack<Apple>(); 
 Apple  a = new Apple();
  Orange b = new Orange();
  stack.push(a); 
 stack.push(b); 
    // compile-time error  
Праграма DoublingStack.java рэалізуе агульны стэк з дапамогай масіва. Па тэхнічных прычынах, адна з адліванага неабходна пры выдзяленні масіва дженеріков.
Autoboxing.
Мы распрацавалі нашы стэкі, каб яны маглі захоўваць любы універсальны тып аб'екта. Апішам функцыю мовы Java, вядомы як аўта-бокс і аўтаматычнай распакавання, якая дазваляе нам выкарыстоўваць гэты ж самы код з прымітыўных тыпаў, а таксама. З кожным прымітыўнага тыпу, напрыклад, INT, з'яўляецца поўнамаштабная тыпу аб'екта, напрыклад, Integer. Калі мы прысвоіць прымітыўных да адпаведнага тыпу аб'екта (ці наадварот), Java аўтаматычна выконвае пераўтварэнне. Гэта дазваляе нам пісаць код, падобны наступнага.
Stack<Integer> stack = new Stack<Integer>();
  stack.push(17); 
 // auto-boxing   (converts int to Integer)  int a = stack.pop(); 
      // auto-unboxing (converts Integer to int)  
Значэнне 17, аўтаматычна прыводзяцца да тыпу Integer, калі мы перадаць яго штурхаць () метад. Поп () вяртае цэлае, і гэта значэнне прыведзена да Int, калі мы прысвоіць яго зменнай a. Мы павінны ведаць, што адбываецца за кулісамі, так як гэта можа паўплываць на прадукцыйнасць.
Java пастаўкі ўбудаваных тыпаў абгорткі для ўсіх прымітыўных тыпаў: Boolean, Byte, знак, падвойны, Float, Integer, Long, і кароткія. Гэтыя класы складаюцца ў асноўным з статычных метадаў (напрыклад, Integer.parseInt (), Integer.reverse ()), але яны таксама ўключаюць некаторыя не статычныя метады (СотрагеТо (), роўна (), doubleValue ()).
Чэргі.
Чарга падтрымлівае ўстаўкі і выдаленні аперацый з выкарыстаннем FIFO дысцыпліны. Па дамове, мы называем аперацыяй чарзе пастаноўкі ўстаўкі і выдалення з чаргі аперацыяй выдалення. Лінкальн тунэлю. Студэнт мае задачы, якія павінны быць завершаны. Пакладзеце на чарзе. Ці ёсць задачы, у тым жа парадку, што яны з'явяцца.
public class Queue<Item> {     public boolean isEmpty();     public void enqueue(Item item);     public Item dequeue();  }  
Звязаны спіс ажыццяўленні. Праграме Queue.java рэалізуе FIFO чаргу радкоў з выкарыстаннем звязанага спісу. Як стэка, мы падтрымліваем спасылкай першымі найменш нядаўна дададзеных вузлоў па чарзе. Для большай эфектыўнасці, мы таксама захоўваць спасылку апошнім найменш нядаўна дададзеных вузлоў па чарзе.
Масіў рэалізацыі. Як і ў масіве рэалізацыі стэка, але крыху больш складана, бо трэба абгарнуць вакол. Праграма DoublingQueue.java рэалізуе чарзе інтэрфейс. Масіў дынамічна зменены пры дапамозе паўтараецца два разы.
Ітэрацый.
Часам кліенту неабходна атрымаць доступ да ўсіх прадметы калекцыі, па адным за раз, не выдаляючы іх. Каб захаваць інкапсуляцыю, мы не хочам раскрыць ўнутранае прадстаўленне чаргі (масіва або звязанага спісу) для кліента. "Аддзяліць рэч, якая павінна прайсці з спісу дэталі атрымання кожнага элемента з яго". Мы вырашаем гэтую задачу дызайну з дапамогай java.util.Iterator інтэрфейс ў Java:

public interface Iterator<Item> { boolean hasNext(); Item next(); void remove(); // optional }

Гэта значыць, любы тып дадзеных, які рэалізуе інтэрфейс Iterator абяцае рэалізаваць два метаду: hasNext () і Next (). Кліент выкарыстоўвае гэтыя метады для доступу да элементаў спісу адзін раз, выкарыстоўваючы наступны стыль.

Queue<String> queue = new Queue<String>(); ... Iterator<String> i = queue.iterator(); while (i.hasNext()) { String s = i.next(); StdOut.println(s); }

Queue iterator in Java. Queue.java illustrates how to implement an Iterator when the items are stored in a linked list.

public Iterator iterator() { return new QueueIterator(); } private class QueueIterator implements Iterator<Item> { Node current = first; public boolean hasNext() { return current != null; } public Item next() { Item item = current.item; current = current.next; return item; } }

Ён абапіраецца на прыватныя укладзеныя QueueIterator падклас, які рэалізуе інтэрфейс Iterator. Метад итератора () стварае асобнік тыпу QueueIterator і вяртае яе як Iterator. Гэта забяспечвае ітэрацыі абстракцыі, так як кліент будзе толькі праз пункты hasNext () і Next () метады. Кліент не мае доступу да вантробы чарзе ці нават QueueIterator. У абавязкі кліента толькі дадаць элементы ў спіс, калі не итератор ў дзеянні.
Пашыраныя цыклу. Ітэрацыі такая карысная абстракцыя, Java забяспечвае кампактны сінтаксіс (вядомы як палепшаны цыкл) для перабору элементаў калекцыі (або масіў).

Iterator<String> i = queue.iterator(); while (i.hasNext()) { String s = i.next(); StdOut.println(s); } for (String s : queue) StdOut.println(s);

Каб скарыстацца перавагамі пашырэння сінтаксісу Java, Еогеасп, тып дадзеных павінен рэалізоўваць Iterable інтэрфейсу Java.

public interface Iterable<Item> { Iterator<Item> iterator(); }

Гэта значыць, тып дадзеных павінен быць рэалізаваны метад, званы итератор (), якая вяртае итератор базавай калекцыі. Так як наша чаргу ADT зараз уключае ў сябе такі метад, трэба проста аб'явіць яго як рэалізацыю Iterable інтэрфейс, і мы гатовыя выкарыстоўваць Еогеасп пазначэнняў.

public class Queue<Item> implements Iterable<Item>

Стэк і чарга прыкладанняў.
Стэкі і чэргі маюць мноства карысных прыкладанняў.
Чэргі прыкладанняў: Вылічальныя ужывання: абслугоўванне запытаў з аднаго агульнага рэсурсу (прынтэр, дыск, працэсар), перадача дадзеных асінхронна (дадзеныя не абавязкова атрыманыя на той жа хуткасцю, перасылаюцца) паміж двума працэсамі (IO буфера), напрыклад, трубы, файл уводу-высновы, сокеты. Буферы на MP3-плэеры і партатыўныя прайгравальнікі кампакт-дыскаў, IPod плэйліст. Плэйліст для музычнага аўтамата - дадаваць песні да канца, гуляць з пярэдняй частцы спісу. Перапыненне апрацоўкі: Пры праграмаванні сістэмы рэальнага часу, які можа быць перапынены (напрыклад, шляхам націску кнопкі мышы або бесправоднае падключэнне), неабходна заклапаціцца перапынення адразу, перш чым прыступіць да бягучай дзейнасці. Калі перапынення павінны быць ручкі ў тым жа парадку іх паступлення, то чэргі FIFO з'яўляецца прыдатнай структуры дадзеных.
Ацэнка арыфметычныя выразы. Праграма Evaluate.java ацэньвае цалкам дужкі арыфметычнае выраз.
Важным ужываннем стэка знаходзіцца ў разборы. Напрыклад, кампілятар павінен разбору арыфметычных выразаў, напісаныя з выкарыстаннем инфиксной натацыі. Напрыклад наступнае выраз инфиксной ацэньваецца як 212.
(2 + ((3 + 4) * (5 * 6)))
Разаб'ем праблема разбору инфиксной выразы ў два этапы. Па-першае, мы ператвараем з инфиксной да іншага прадстаўленні называецца Postfix. Затым мы разбіраем постфиксное выраз, якое некалькі прасцей, чым праблема непасрэдна разбор инфиксной.
Ацэнка постфиксное выраз. Постфиксное выраз гэта....
2 3 4 + 5 6 * * +
Па-першае, мы апішам, як аналізаваць і ацэньваць постфиксное выраз. Мы чытаем жэтоны ў адной за раз. Калі гэта лік, штурхаць яго на стэк, калі гэта бінарны аператар, поп двух верхніх элементаў з стэка, прымяніць аператар двух элементаў, і націсніце вынік зваротна ў стэк. Праграма Postfix.java чытае і ацэньвае постфиксного выразы, якія выкарыстоўваюць гэты алгарытм.
Пераўтварэнне з инфиксной да Postfix. Цяпер мы апішам, як перайсці ад инфиксной да Postfix. Мы чытаем у жэтонаў па адным за раз. Калі гэта аператар, мы змяшчаем яго ў стэк, а калі гэта лік, то раздрукаваць яго, калі ён з'яўляецца правай дужкі, мы поп верхні элемент з стэка і раздрукаваць яго, калі ён левых дужак, мы яго ігнаруем. Праграма Infix.java счытвае выраз инфиксной, і выкарыстоўвае стэк для высновы эквівалентнае выраз постфикс па алгарытме, апісанаму вышэй. Суаднясіце вернемся да прыкладу дрэва разбору ў раздзеле 4.3.
Выклікі функцый. Мабыць, найбольш важным ужываннем стэка з'яўляецца рэалізацыя выклікаў функцый. Большасць кампілятараў ажыццяўляць выклікі функцый з дапамогай стэка. Гэта таксама забяспечвае спосаб ліквідацыі рекурсии з праграмы: замест выкліку функцыі рэкурсіўна, праграміст выкарыстоўвае стэк для мадэлявання выклікаў функцый такім жа чынам, што кампілятар зрабіў бы гэта. Наадварот, мы часта можам выкарыстоўваць рекурсию замест выкарыстання відавочнага стэка. Некаторыя мовы праграмавання падаюць механізм рекурсии, але не для выкліку функцый.
Мовы праграмавання маюць убудаваную падтрымку стэка (рекурсия), але не аналагічны механізм для барацьбы з чэргамі.
Postscript і FORTH мовы праграмавання стэку. Java байт-код інтэрпрэтуецца на (віртуальны) працэсар на базе стэка. Microsoft Intermediate Language (MSIL), што. NET дадатку кампілююцца ст.
M/M/1 чэргі. Маркава / Маркава / Single-Server мадэль з'яўляецца фундаментальнай мадэлі чэргаў ў даследаванні аперацый і тэорыі верагоднасцяў. Задачы прыбыць у адпаведнасці з пуассоновским працэсам на пэўным λ стаўкі. Гэта азначае, што λ кліенты прыходзяць у гадзіну. У прыватнасці, якія прыбылі прытрымлівацца экспанентна размеркаванне з сярэднім 1 / λ: верагоднасць прыбыцця да часу паміж 0 і Т (λ т) ^ цы ^ (-λ т) / k!. Задачы абслугоўваюцца ў парадку FIFO ў адпаведнасці з пуассоновским працэсам з інтэнсіўнасцю μ. Стандартныя две M для Маркаў: гэта азначае, што сістэма памяці: час паміж паступленнямі не залежыць, а час паміж адпраўленнямі не залежыць.
Аналіз M/M/1 мадэлі. Мы зацікаўлены ў разуменні сістэмы масавага абслугоўвання. Калі λ> μ памер чарзе неабмежавана расце. Для простых мадэляў, як M/M/1 мы можам прааналізаваць гэтыя велічыні аналітычна з выкарыстаннем тэорыі верагоднасці. Мяркуючы, μ> λ, верагоднасць роўна п кліентаў у сістэме (λ / μ) ^ п (1 - λ / μ).
L = сярэдні лік кліентаў у сістэме = λ / (μ - λ).
LQ = сярэдняя колькасць кліентаў у чарзе = λ2 / (μ (μ - λ)).
W = сярэдні час, кліент марнуе ў сістэме = 1 / (μ - λ).
WQ = сярэдні час кліент праводзіць у чарзе = W - 1 / μ.
Праграма MM1Queue.java Для больш складаных мадэляў мы павінны звяртацца да мадэлявання, як гэта. Варыянты: некалькі чэргаў, некалькі сервераў, паслядоўная шматступенная серверах, выкарыстоўваючы канчатковыя чэргі і вымярэння колькасці спажыўцоў, якія адвярнуліся. Вобласці ўжывання: кліентаў у Макдональдс, пакеты ў Інтэрнэт маршрутызатар,
Закон Літл сцвярджае, што сярэдні лік кліентаў у (стабільны) сістэмы масавага абслугоўвання роўная сярэдняй хуткасці прыбыцця іх сярэдні час знаходжання ў сістэме. Але дысперсіі кліент задавальняе чакання: Var (FIFO) <Var (SIRO) <Var (ЛИФО).
Размеркаванне колькасці патрабаванняў у сістэме не залежыць ад чэргаў дысцыпліны (пакуль яна не залежыць ад іх час абслугоўвання). Тое ж самае для чаканага часу чакання.
M/D/1 чэргі. Праграма MD1Queue.java падобная, але паслугі адбываецца па фіксаваным курсе (а не выпадковым чынам).
Балансіроўка нагрузкі. Напішыце праграму LoadBalance.java, які выконвае балансаванне нагрузкі мадэлявання.
Q + A.
Пытанне: Калі я магу выкарыстоўваць новыя з вузлом?
А. Гэтак жа, як і любы іншы клас, вы павінны выкарыстоўваць толькі новыя, калі вы хочаце стварыць новы аб'ект Node (Новы элемент у звязаны спіс). Вы не павінны выкарыстоўваць новыя, каб стварыць новую спасылку на існуючы аб'ект Node. Напрыклад, код

Node oldfirst = new Node(); oldfirst = first;

стварае новы аб'ект Node, то адразу губляе магчымасць адсочваць толькі спасылку на яго. Гэты код не прыводзіць да памылкі, але гэта крыху неахайна стварыць сірот без усялякай прычыны.
Пытанне: Чаму абвясціць вузла як укладзены клас? Чаму прыватныя?
А. Аб'яўляючы падкласа вузла для прыватных Мы абмяжоўваем доступ да метадаў у ўключае класа. Адной з характэрных рысаў прыватных ўкладзенага класа з'яўляецца тое, што яго зменныя асобніка могуць быць даступныя непасрэдна з навакольнага яго класа, але нідзе, так што няма неабходнасці аб'яўляць іх дзяржаўнай або прыватнай. Заўвага: укладзены клас, які не стаіць на месцы, як вядома, як унутраны клас, так што тэхнічна нашы класы вузлоў з'яўляюцца ўнутранымі класамі, хоць і тыя, якія не з'яўляюцца агульнымі могуць быць статычнымі.
В. Чаму Javac LinkedStackOfStrings.java стварае файл LinkedStackOfStrings $ Node.class а таксама LinkedStackOfStrings.class?
А. Гэта файл прызначаны для укладзеных вузлоў класа. Наймення ў Java з'яўляецца выкарыстанне $ аддзяліць імя знешняга класа ад ўкладзенага класа.
Пытанне: Калі кліент дапускаецца, каб уставіць пусты элементы на стэк або чаргу? A. Гэтае пытанне часта ўзнікае пры рэалізацыі калекцый у Java. Наша рэалізацыя (а таксама Java-стэк і чарга бібліятэк) зрабіць дазвол ўстаўкі пустых значэнняў.
В. Ці ёсць Java-бібліятэкі для стэкаў і чэргаў?
Адказ: Так, і няма. Java мае убудаваную бібліятэку java.util.Stack, але вы павінны пазбягаць выкарыстання яго, калі вы хочаце стэк. Ён мае некалькі дадатковых аперацый, якія звычайна не звязаны з стэк, напрыклад, атрыманне й элемент. Яна таксама дазваляе дадаваць элемент да ніжняй часткі стэка (замест таго, каб зверху), таму ён можа рэалізаваць чарзе! Хоць наяўнасць такіх дадатковых аперацый можа здацца, што бонус, на самай справе праклён. Мы выкарыстоўваем тыпы дадзеных, не таму што яны забяспечваюць усе даступныя аперацыі, але хутчэй таму, што яны дазваляюць сапраўды вызначыць аперацыі нам трэба. Прэм'ер карысць гэтага з'яўляецца тое, што сістэма можа перашкодзіць нам выконваць аперацыі, якія мы на самай справе не хочуць. Java.util.Stack API з'яўляецца прыкладам шырокага інтэрфейс, які мы звычайна стараемся пазбягаць.
Пытанне: Я хачу выкарыстоўваць масіў паказ для агульных стэк, але падобны код не будзе кампілявацца. У чым праблема?

private Item[] a = new Item[max]; oldfirst = first;

А. Добра паспрабаваць. На жаль, стварэння масіваў дженеріков не дапускаецца ў Java 1.5. Эксперты да гэтага часу актыўна абмяркоўваюць гэтае рашэнне. Як звычайна, жалячыся, занадта гучна аб магчымасці мовы ставіць вас на слізкі шлях да станаўленню мовы дызайнера. Існуе выхад, выкарыстоўваючы ролях: вы можаце Write:

private Item[] a = (Item[]) new Object[max]; oldfirst = first;

Асноўнай прычынай з'яўляецца тое, што масівы ў Java з'яўляюцца ковариантными, але дженеріков не з'яўляюцца. Іншымі словамі, String [] з'яўляецца падтыпам Object [], але стэк <String> ня падтып Стэк <Object>. Каб абыйсці гэты недахоп, неабходна выканаць бесперашкодна кінута як у DoublingStack.java. Многія праграмісты лічаць ковариантной масіваў у якасці дэфекту ў сістэме тыпаў Java (і гэта прывяло да неабходнасці «reifiable тыпаў" і "тыпу пры спробе ачысціць»). Тым не менш, у свеце без дженеріков, ковариантные масівы з'яўляюцца карыснымі, напрыклад, для рэалізацыі Arrays.sort (Супастаўныя []), і ён будзе выклікацца пры ўваходным масіў тыпу String [].
Пытанне: Ці магу я выкарыстаць Еогеасп будаўніцтва з масівамі?
Адказ: Так (хоць масівы не рэалізуюць Iterator інтэрфейсу). Наступныя друкуе аргументы каманднага радка:

public static void main(String[] args) { for (String s : args) StdOut.println(s); }

Пытанне: Ці з'яўляецца ітэрацыі звязанага спісу больш эфектыўным з пятлёй або рекурсии?
А. аптымізуе кампілятар, хутчэй за ўсё, пераводзіць хвост рэкурсіўнай функцыі ў эквівалентную цыклу, так што можа быць не назіраецца зніжэнне прадукцыйнасці выкарыстання рекурсии.
Пытанне: Якім чынам аўта-бокс апрацоўваць наступны фрагмент кода?

Integer a = null; int b = a;

А. Гэта прыводзіць да памылкі падчас выканання. Прымітыўны тып можа захоўваць любое значэнне іх адпаведнага тыпу абгорткі, акрамя нулявы.
Пытанне: Чаму першая група аператараў друку і так, але другі две друку?

Integer a1 = 100; Integer a2 = 100; System.out.println(a1 == a2); // true Integer b1 = new Integer(100); Integer b2 = new Integer(100); System.out.println(b1 == b2); // false Integer c1 = 150; Integer c2 = 150; System.out.println(c1 == c2); // false

А. второе друкуе ілжывае, таму што b1 і b2 з'яўляюцца спасылкамі на розныя аб'екты Integer. Першы і трэці фрагменты кода спадзявацца на автобоксинг. Дзіўна первых адбіткаў дакладна, таму што значэнні ад -128 да 127 па ўсёй бачнасці, паказваюць на тыя ж нязменныя аб'екты Integer (меркавана, ёсць басейн з іх, якія выкарыстоўваюцца паўторна), у той час як Java стварае новыя аб'екты для кожнага цэлага па-за гэтага дыяпазону. Урок: як звычайна, не выкарыстоўвайце == для параўнання, ці з'яўляюцца два аб'екта маюць тое ж значэнне.

Пытанне: Ці з'яўляюцца джынэрыкі выключна для аўтаматычнага ліцця?
Адказ: Не, але гэта будзе адзінае, што мы выкарыстоўваць іх для. Гэта называецца "чыстым дженеріков" або "канкрэтныя параметризованных тыпаў." Бетонныя параметризованные тыпы працаваць амаль як нармальныя тыпы з некалькімі выключэннямі (стварэння масіва, апрацоўка выключэнняў, з InstanceOf, а ў клас літэрал). Больш прасунутыя выкарыстання дженеріков, у тым ліку "шаблоны", якія з'яўляюцца карыснымі для апрацоўкі падтыпаў і спадчыну. Вось генериков падручнік.
Пытанне: Чаму я атрымліваю несумяшчальных тыпаў памылка падчас кампіляцыі з дапамогай наступнага кода?

Stack stack = new Stack<String>(); stack.push("Hello"); String s = stack.pop();

А. Вы забыліся пазначыць канкрэтны тып пры аб'яўленні стэка. Варта Стэк <String>.

Пытанне: Чаму я атрымліваю выкарыстоўвае бескантрольна або небяспечных аперацый папярэджанне падчас кампіляцыі з наступнымі код?

Stack<String> stack = new Stack(); stack.push("Hello"); String s = stack.pop();

А. Вы забыліся пазначыць канкрэтны тып пры выкліку канструктара. Гэта павінны быць новыя <String> Stack ().

Практыкаванні
Дадайце метад isFull (), каб ArrayStackOfStrings.java.
Дайце выхад надрукаваныя Java ArrayStackOfStrings 5 за ўваход

it was - the best - of times - - - it was - the - -

Выкажам здагадку, што кліент выконвае перамяшаныя паслядоўнасць (стэк) штуршок і поп-аперацый. Штурхаць аперацый пакласці цэлыя лікі ад 0 да 9, каб у стэк; поп аперацый раздрукаваць вяртаецца значэння. Якія з наступных паслядоўнасцяў (ы) не магло адбыцца?
() 4 3 2 1 0 9 8 7 6 5 (Б) 4 6 8 7 5 3 2 9 0 1 (З) 2 5 6 7 8 9 4 3 1 0 (Г) 4 3 2 1 0 5 6 7 8 9 (Е) 1 2 3 4 5 6 9 8 7 0 (Е) 0 4 6 5 3 8 1 7 2 9 (Г) 1 4 7 9 8 6 5 3 0 2 (Ч) 2 1 4 3 6 5 8 7 9 0
Напісаць стэк кліента Reverse.java, што чырвоныя ў радкі з стандартнага ўводу і друкуе іх у зваротным парадку.
Калі выказаць здагадку, што стандартны ўвод мае некаторыя невядомыя N лік падвойных значэнняў. Напішыце метад, які счытвае ўсе значэння і вяртае масіў даўжынёй N, якія змяшчаюць іх, у іншых яны з'яўляюцца на стандартны ўвод.
Напісаць стэк кліента Parentheses.java, які чытае ў тэкставы паток са стандартнага ўводу і выкарыстоўвае стэк, каб вызначыць яго дужкі правільна збалансаваныя. Напрыклад, ваша праграма павінна друкаваць дакладна для [()]{}{[()()]()} і няслушна пры [(]). Падказка: Выкарыстоўвайце стэк.
Што робіць наступны фрагмент кода друку, калі N роўна 50? Дайце высокім узроўні апісанне таго, што фрагмент кода сапраўды пры прад'яўленні станоўчых N цэлае.

Stack stack = new Stack(); while (N > 0) { stack.push(N % 2); N = N / 2; } while (!stack.isEmpty()) StdOut.print(stack.pop()); StdOut.println();

Адказ: адбіткі бінарнае ўяўленне N (N 110010, калі ёсць 50).

Што робіць наступны фрагмент кода зрабіць, каб чэргі д?

Stack stack = new Stack(); while (!q.isEmpty()) stack.push(q.dequeue()); while (!stack.isEmpty()) q.enqueue(stack.pop());

Дадайце метад Peek (), каб Stack.java, якая вяртае апошні элемент адсутнічае ў стэк (без з'яўляцца яго).
Дайце ўтрыманне і памер масіва для DoublingStackOfStrings з уваходным

it was - the best - of times - - - it was - the - -

Дадайце метад даўжыні (), каб Queue.java, якая вяртае колькасць элементаў у чарзе. Падказка: Калі ласка, пераканайцеся, што ваш метад займае пастаяннае час, падтрымліваючы асобнік зменнай N, што Вы пачынаючы з 0, прырост пастаноўкі (), декремент з чаргі (), і вярнуцца ў даўжыню ().
Намалюйце схему выкарыстання памяці ў стылі дыяграм у раздзеле 04/01 для трох вузлоў прыклад выкарыстоўваецца для ўвядзення звязаных спісаў ў гэтым раздзеле.
Напішыце праграму, якая прымае з стандартнага ўводу выразы без дужак і друкуе эквівалентнае выраз инфиксной з дужках ўстаўленыя. Напрыклад, калі ўваходны

1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )

Ваша праграма павінна надрукаваць
((1 + 2) * ((3 - 4) * (5 - 6))
Напісаць фільтр InfixToPostfix.java, які пераўтворыць арыфметычныя выразы з инфиксной да Postfix.
Напішыце праграму, EvaluatePostfix.java, які прымае постфиксное выраз з стандартнага ўводу, вылічае яго і друкуе значэнне. (Перадача высновы вашай праграмы з папярэдняга практыкаванні, каб гэтая праграма дае эквівалентнае паводзіны Evaluate.java.)
Выкажам здагадку, што кліент выконвае перамяшаныя паслядоўнасць (чаргу) пастаноўкі і выдалення з чаргі аперацый. Пастаноўкі аперацый пакласці цэлыя лікі ад 0 да 9, каб на чарзе; з чаргі аперацый раздрукаваць вяртаецца значэння. Якія з наступных паслядоўнасцяў (ы) не магло адбыцца?
() 0 1 2 3 4 5 6 7 8 9 (б) 4 6 8 7 5 3 2 9 0 1 (з) 2 5 6 7 8 9 4 3 1 0 (г) 4 3 2 1 0 5 6 7 9 жніўня
Напісаць итерабельных кліента стэка, які з'яўляецца статычнай копіяй метадаў (), якая прымае стэк радкоў у якасці аргументу і вяртае копію стэка. Заўвага: Гэтая здольнасць яркім прыкладам каштоўнасць наяўнасці итератора, бо дазваляе развіццё такую функцыянальнасць, не змяняючы асноўных API.
Распрацоўка класа DoublingQueueOfStrings.java, які рэалізуе чарзе абстракцыі з масіва фіксаванага памеру, а затым пашырыць рэалізацыю выкарыстоўваць масіў падваенне зняць абмежаванне на памеры.
Напісаць Queue.java кліент, які прымае аргумент каманднага радка і выводзіць да-й з апошняга радка, знойдзенай на стандартны ўвод.
(Для матэматычна схільны.) Дакажыце, што масіў у DoublingStackOfStrings.java ніколі не менш чым на адну чвэрць поўным аб'ёме. Затым дакажам, што для любога кліента DoublingStackOfStrings, агульная кошт усіх стековых аперацый, дзялення на колькасць аперацый з'яўляецца канстантай.
Змяніць MD1Queue.java, каб зрабіць праграму MM1Queue.java, якая імітуе чарзе, для якіх абодва заезду і службы пояс Пуасона працэсаў. Праверце закон Літл для гэтай мадэлі.
Распрацоўка класа StackOfInts.java які выкарыстоўвае звязаны спіс прадстаўленне (але не джынэрыкі). Напісаць кліента, які параўноўвае прадукцыйнасць вашага <Integer> withStack рэалізацыі для вызначэння прадукцыйнасці штрафу ў памеры ад аўтаматычная ўпакоўка ў вашай сістэме.

Змяненні, Практыкаванні Спіс
Напішыце метад выдалення (), якая прымае Int K аргумент і выдаляе элемент й у звязаны спіс, калі ён існуе.
Рашэнне.

// we assume that first is a reference to the first Node in the list public void delete(int k) { if (k <= 0) throw new RuntimeException("Invalid value of k"); // degenerate case - empty linked list if (first == null) return; // special case - removing the first node if (k == 1) { first = first.next; return; } // general case, make temp point to the (k-1)st node Node temp = first; for (int i = 1; i < k; i++) { temp = temp.next; if (temp == null) return; // list has < k nodes } if (temp.next == null) return; // list has < k nodes // change temp.next to skip kth node temp.next = temp.next.next; }

Напішыце метад Find (), якая прымае звязаны спіс і радок ключ у якасці аргументаў і вяртае ісціну, калі нейкія вузла ў спіс ключавых пункта ў якасці поля, у адваротным выпадку.
Хай х звязаны спіс вузлоў. Што такое эфект наступны фрагмент кода?

x.next = x.next.next;

Адказ: Выдаленне з спісу вузел адразу пасля x.
Выкажам здагадку, што х ёсць звязаны спіс вузлоў. Што такое эфект наступны фрагмент кода?

t.next = x.next; x.next = t;

Адказ: т ўстаўляе вузел адразу пасля вузел x.
Чаму наступны фрагмент кода не маюць такі ж эфект як і ў папярэднім пытанні?

x.next = t; t.next = x.next;

Адказ: Калі прыходзіць час для абнаўлення t.next, x.next больш не з'яўляецца арыгінальным х наступны вузел, але замест т сам!
Напішыце метад removeAfter (), які прымае звязаны спіс вузлоў у якасці аргументу і выдаляе вузел, наступны дадзеным (і нічога не робіць, калі аргумент ці наступнае поле ў аргумент вузел з'яўляецца нулявым).
Напішыце метад InsertAfter (), якая прымаюць два звязаны спіс вузлоў аргументаў і ўстаўляе другі пасля першай у яго спісе (і нічога не робіць, калі любы аргумент роўны нулю).
Напішыце метад выдалення (), які прымае звязаны спіс і радок ключ у якасці аргументаў і выдаляе ўсе вузлы ў спісе, які ёсць ключ у якасці пункта вобласці.
Напішыце метад, макс (), якая спасылкай на першага вузла ў звязаны спіс у якасці аргументу і вяртае значэнне максімальнага ключ у спісе. Выкажам здагадку, што ўсе ключы цэлыя станоўчыя ліку, і вяртаць 0, калі спіс пусты.
Распрацоўка рэкурсіўных рашэнне папярэдняга практыкаванні.
Напішыце рэкурсіўны метад для друку элементы звязанага спісу ў зваротным парадку. Не змяняць любую з спасылак проста:. Выкарыстоўвайце квадратычны час, пастаяннае дадатковае прастору Таксама лёгка. Выкарыстанне лінейнага часу, лінейны дадатковае месца не так-то проста. Распрацоўка падзяляй і ўладар алгарытм, які выкарыстоўвае linearithmic часу і лагарыфмічныя дадатковае прастору.
Напішыце рэкурсіўны метад для выпадковага мяшання элементы звязанага спісу, змяніўшы спасылкі Лёгка:. Выкарыстоўвайце квадратычны час, пастаяннае дадатковае месца не так-то проста. Распрацоўка падзяляй і ўладар алгарытм, які выкарыстоўвае linearithmic часу і лагарыфмічныя дадатковае прастору.
Творчыя практыкаванні
Deque двухбаковая чаргу або двухбаковую чаргу (вымаўляецца як палуба) уяўляе сабой камбінацыю з стэка і і чэргі. Ён захоўвае параметризованные калекцыі элементаў і падтрымлівае наступныя API:
Напісаць Deque.java тып дадзеных, які рэалізуе двухбаковую чаргу API выкарыстаннем аднанакіраваныя спісу.
. Выпадковыя чарзе Стварыць абстрактны тып дадзеных RandomizedQueue.java, які падтрымлівае наступныя аперацыі:. IsEmpty (), уставіць (), выпадковае (), і removeRandom (), дзе аперацыі выдалення выдаляе і вяртае выпадковы аб'ект Падказка: для масіва аб'ектаў. Каб выдаліць аб'ект, своп выпадковых аб'екта (з індэксацыяй ад 0 да N-1) з апошняга аб'екта (індэкс N-1). Затым выдаліце і вяртанне апошняга аб'екта.

Лістынг файлаў. Каталогу Unix з'яўляецца спіс файлаў і дырэкторый. Праграма Directory.java прымае імя каталога ў якасці параметру каманднага радка і друкуе ўсе файлы, якія змяшчаюцца ў гэтым каталогу (і любых падкаталогах) на ўзроўні парадку. Ён выкарыстоўвае чаргу.
Іосіф праблема Праграма Josephus.java выкарыстоўвае чарзе для вырашэння Іосіф праблемы.
Выдаліць й элемент Стварыць ADT, які падтрымлівае наступныя аперацыі:. IsEmpty, ўстаўкі і выдаленні (INT я), дзе аперацыі выдалення выдаляе і вяртае й меры нядаўна дададзеных аб'ектаў на чарзе. Рабіце гэта з масівам, то рабіць гэта з звязанага спісу. Глядзіце практыкаванне XYZ для больш эфектыўнай рэалізацыі, якая выкарыстоўвае BST.
Дынамічнае сціск. З масіве рэалізацыі стэка і чэргі, мы падвоілі памер масіва, калі яна была недастаткова вялікая для захоўвання наступнага элемента. Калі мы будзем выконваць шэраг аперацый ўдвая, а затым выдаліць шмат элементаў, мы маглі бы ў канчатковым выніку з масівам, што нашмат больш, чым гэта неабходна. Рэалізацыя наступную стратэгію: кожны раз, калі масіў складае 1 / 4 поўнай або менш, паменшыць яго ў два разы менш. Растлумачце, чаму мы не паменшыць яго ў два разы менш, калі ён роўны 1 / 2 поўнай або менш.
Кальцавой буфер. Кальцавога буфера або кругавой чарзе FIFO структуры дадзеных фіксаванага памеру N. Гэта карысна для перадачы дадзеных паміж асінхроннымі працэсамі ці захоўвання файлаў часопіса. Калі буфер пусты, спажывец чакае, пакуль дадзеныя на захоўванне, калі буфер поўны, вытворца чакае дэпазіт дадзеных. Кальцавой буфер мае наступныя метады: IsEmpty (), isFull (), пастаноўкі (), і з чаргі (). Стварыць універсальны тып дадзеных RingBuffer выкарыстаннем масіва (з кругавым намотваецца вакол для эфектыўнасці).
Зліццё двух адсартаваных чэргаў. Улічваючы дзве чаргі са радкамі ў парадку ўзрастання, перамясціць усе радкі ў трэцяй чаргі, так што трэцяя чэргі заканчваецца радкамі ў парадку ўзрастання.
Зліццём. Улічваючы N радкоў, стварыце N чэргаў, кожная з якіх утрымоўвае адну з радкоў. Стварэнне чарзе N чэргаў. Затым некалькі разоў ўжыць аперацыю зліцця адсартаваных па першых двух чэргаў і зноў аб'ядналіся чэргі ў канцы. Паўтарайце, пакуль чэргі чэргаў змяшчае толькі адну чаргу.
. Чарга з двума стэкамі Паказаць, як рэалізаваць чаргу з выкарыстаннем двух стэкаў Падказка:. Калі Вы вылучае элементы ў стэк, а затым поп іх усіх, яны з'яўляюцца ў зваротным парадку. Калі вы паўторыце гэты працэс, яны цяпер у парадак.
Перамяшчэнне да фронту. Чытайце ў паслядоўнасць знакаў з стандартнага ўводу і падтрымліваць сімвалы ў звязаным спісе, без дублікатаў. Калі вы чытаеце ў раней не характар, уставіць яго ў пачатак спісу. Калі вы чытаеце ў дублікат характару, выдаліць яго з спісу і зноў устаўце яго ў пачатку. Гэта рух да пярэдняй стратэгія карысная для кэшавання і сціскі дадзеных (Burrows-Wheeler) алгарытмаў, дзе элементы, якія былі ў апошні час доступ да якіх хутчэй за ўсё, будзе паўторна доступ.
Тэкставы рэдактар буфера. Рэалізацыя АТД для буфера ў тэкставым рэдактары. Яна павінна падтрымліваць наступныя аперацыі:
устаўка (з): ўстаўка знака з у курсор
выдаліць (): выдаліць і вярнуць знак перад курсорам
налева (): перамяшчэнне курсора на адну пазіцыю ўлева
Права (): перамяшчэнне курсора на адну пазіцыю ўправа
атрымаць (я): вяртаць-га знака ў буферы
Рада: выкарыстоўвае дзве чаркі.
Тапалагічнымі роду. Вы павінны паслядоўнасць парадак працоўныя месцы N на працэсар. Некаторыя з работ павінна быць завершана да іншых можа пачацца. У прыватнасці, вам падаецца спіс парадку пар працоўных месцаў (I, J). Знайсці паслядоўнасць працоўных месцаў, што для кожнай пары (I, J) працу я запланаваны перад заданнем j. Выкарыстоўвайце наступны алгарытм.... Для кожнага вузла, весці спіс выходных дуг выкарыстаннем чарзе. Акрамя таго, падтрыманне заходу кожнага вузла. Нарэшце, падтрымліваць чарзе ўсе вузлы якога заходу роўная 0. Неаднаразова выдаліць вузел з нуля заходу, а таксама выдаліць усе выходныя дугі. Напішыце праграму, TopologicalSorter.java для дасягнення гэтай мэты.
Альтэрнатыўнае прымяненне: перадумоў для заканчэння ў вашай спецыяльнасці. Павінны прыняць COS 126 і COS 217 да COS 341, і г.д. Ці можаце вы выпускнік?
PERT / CPM. Зменіце папярэдняе практыкаванне для апрацоўкі грузаў (I, J, са) азначае працу я запланаваны па крайняй меры з адзінкі часу перад заданнем j.
Мноства цэлых лікаў. Стварыце тып дадзеных, які ўяўляе мноства цэлых лікаў (без дублікатаў) ад 0 да N-1. Падтрымка дадаць (я), існуе (я), выдаліць (я), памер (), перасякаюцца, розніца, symmetricDifference, саюз, isSubset, isSuperSet і isDisjointFrom.
Індэксацыя кнігі. Напішыце праграму, якая счытвае тэкставы файл са стандартнага ўводу і кампілюе алфавітны паказальнік, якія словы з'явіліся на якім лініі, як паказана ў наступным ўваходзе. Ігнараваць рэгістр і пунктуацыю. Як і ў FrequencyCount, але для кожнага слова весці спіс месцы, на якім ён з'яўляецца.
Зваротны звязаны спіс. Напішыце функцыю, якая займае першае вузла ў звязаны спіс, адмяніць яго і вяртае первый вузел у выніку звязанага спісу.
Рашэнне. Каб дасягнуць гэтага, мы падтрымліваем спасылкі на тры паслядоўных вузлоў у звязаным спісе, наадварот, па-першае, і другое. На кожнай ітэрацыі мы здабываем вузел першым з арыгінальнага звязаны спіс і ўставіць яго ў пачатку зваротны спіс. Мы падтрымліваем інварыянт, першым з'яўляецца першым вузлом, што засталося ад першапачатковага спісу, другі з'яўляецца другім вузлом, што засталося ад першапачатковага спісу, і зваротнае первый вузел у выніку зваротнай спіс.

public static Node reverse(Node list) { Node first = list; Node reverse = null; while (first != null) { Node second = first.next; first.next = reverse; reverse = first; first = second; } return reverse; }

Пры напісанні кода з удзелам звязаных спісаў, мы заўсёды павінны быць асцярожныя, каб належным чынам вырашыць выключных выпадках (калі звязаны спіс пусты, калі спіс мае толькі адзін ці два вузла) і межавыя выпадкі (справа з першым або апошнім пунктаў). Як правіла, гэта самая складаная частка, у адрозненне ад апрацоўкі звычайных выпадках.
Рэкурсіўнае рашэнне. Мяркуючы, звязанага спісу мае N элементаў, мы рэкурсіўна адмяніць апошняе N-1 элементаў, затым асцярожна дадаць першы элемент да канца.

public Node reverse(Node first) { if (first == null | | first.next == null) return first; Node second = first.next; Node rest = reverse(second); second.next = first; first.next = null; return rest; }

Вэб Практыкаванні
Цытата Распрацоўка тып дадзеных. Quote.java, які рэалізуе наступныя API:

public class Quote ------------------------------------------------------------------------------- Quote() create an empty quote void addWord(String w) add w to the end of the quote int count() return number of words in quote String getWord(int i) return the ith word starting at 1 void insertWord(int i, String w) add w after the ith word String toString() return the entire quote as a String

Для гэтага неабходна вызначыць укладзеныя карты класа, які займае адно слова цытаты і спасылкі на наступнае слова:

private class Card { private String word; private Card next; public Card(String word) { this.word = word; this.next = null; } }

Цыркуляр цытаты. Паўторныя папярэднім практыкаванні, але напісаць праграму CircularQuote.java, якія выкарыстоўваюць кругавыя звязанага спісу.
Напішыце рэкурсіўна функцыю, якая прымае ў якасці ўваходных дадзеных чарзе, і перабудоўвае яе так, каб гэта ў зваротным парадку. Падказка: з чаргі () першы элемент, рэкурсіўна адваротнае чарзе, і пастаноўкі першага элемента.
Дадайце метад Item [] MultiPOP (Int K), каб стэк, які з'яўляецца да элементаў з стэка і вяртае іх у выглядзе масіва аб'ектаў.
Дадайце метад Item [] ToArray () у чаргу, якая вяртае ўсё N элементаў на чарзе як масіў даўжыні N.
Што робіць наступны фрагмент кода рабіць?

IntQueue q = new IntQueue(); q.enqueue(0); q.enqueue(1); for (int i = 0; i < 10; i++) { int a = q.dequeue(); int b = q.dequeue(); q.enqueue(b); q.enqueue(a + b); System.out.println(a); }

Fibonacci

What data type would you choose to implement an "Undo" feature in a word processor?

Suppose you have a single array of size N and want to implement two stacks so that you won't get overflow until the total number of elements on both stacks is N+1. How would you proceed?

Suppose that you implemented push in the linked list implementation of StackList with the following code. What is the mistake?

public void push(Object value) { Node second = first; Node first = new Node(); first.value = value; first.next = second; }

Адказ: Па переобъявления па-першае, вы стварыць новую лакальную зменную з імем першага, які адрозніваецца ад асобніка пераменная з імем у першую чаргу.
Капіяванне чарзе Стварыце новы канструктар, так што LinkedQueue г = новы LinkedQueue (дз) робіць т спасылкай новага і незалежнага чарзе Падказка:.. Выдаліць усе элементы з д і дадаць да абодвух д і гэта.
Капіяванне стэка. Стварыце новы канструктар для звязанага спісу рэалізацыі Stack.java так, каб стэк т = новы стэк (ы) робіць т спасылкай новага і незалежнага копію стэка s. Вы павінны мець магчымасць вылучыць і поп-музыкі з з і т, не ўплываючы на іншыя.
Ці павінна яна працаваць, калі аргумент роўны нулю рэкурсіўнае рашэнне: стварыць копію канструктар для вузла і выкарыстоўваць гэта, каб стварыць новую пачак.

Node(Node x) { item = x.item; if (x.next != null) next = new Node(x.next); } public Stack(Stack s) { first = new Node(s.first); }

Нерекурсивных рашэнне (неправераныя):

Node(Node x, Node next) { this.x = x; this.next = next; } public Stack(Stack s) { if (s.first != null) { first = new Node(s.first.value, s.first.next) { for (Node x = first; x.next != null; x = x.next) x.next = new Node(x.next.value, x.next.next); } }

Стэк з адной чарзе Паказаць, як рэалізаваць стэк з дапамогай адной чарзе Падказка:.., Каб выдаліць элемент, атрымаць усе элементы па чарзе па адным за раз, і паклаў іх у канцы, за выключэннем апошняга, які вы павінны выдалення і вяртання.
Лістынг файлаў з стэку. Напішыце праграму, якая прымае імя каталога ў якасці аргументу каманднага радка, і раздрукоўвае ўсе файлы, якія змяшчаюцца ў гэтым каталогу і ўсіх яго падкаталогах. Таксама выводзіць памер файла (у байтах) кожнага файла. Выкарыстоўвайце стэк замест таго, каб чэргі. Паўтарыце з выкарыстаннем рекурсии і імя вашай праграмы DirectoryR.java. Змяніць DirectoryR.java так, каб ён друкуе кожны падкаталог і яе агульны аб'ём. Памер каталога роўная суме ўсіх якія змяшчаюцца ў ёй файлаў, або што яго падкаталогах ўтрымоўваюць.
Стэк + макс. Стварыце структуру дадзеных, якая эфектыўна падтрымлівае стэк аперацый (поп і штуршок), а таксама вяртанне максімальнага элемента. Выкажам здагадку, элементы цэлыя або рэчавыя ліку, каб вы маглі параўнаць іх Падказка:. Выкарыстанне двух стэкаў, адзін для захоўвання ўсіх элементаў і другі стэк для захоўвання максімумаў.
. Тэгаў сістэмы Напішыце праграму, якая чытае ў двайковай радкі з каманднага радка і прымяняе наступныя (00, 1101) тэг-сістэмы: калі першы біт роўны 0, выдаліць першыя тры біта і дадаць 00, калі першы біт 1, выключыць першыя тры біта і дадайце 1101. Паўтарыце, пакуль радок мае па меншай меры 3 біта. Паспрабуйце вызначыць, ці з'яўляецца наступныя ўваходы спыніцца або пайсці ў бясконцы цыкл: 10010, 100100100100100100. Выкарыстанне чарзе.
Reverse. Напішыце метад прачытаць у адвольнае колькасць радкоў са стандартнага ўводу і друкаваць іх у зваротным парадку.

public static void main(String[] args) { Stack<String> stack = new Stack<String>(); while (!StdIn.isEmpty()) { String s = StdIn.readString(); stack.push(s); } while (!stack.isEmpty()) { String s = stack.pop(); StdOut.println(s); } }

Дадаць памеру метадам Int (), каб DoublingStack.java і Stack.java, якая вяртае колькасць элементаў у стэку.
Дадайце метад зваротнай () для чарзе, які змяняе парадак элементаў у чарзе.
Дадаць метад капіявання (), каб ArrayStackOfStrings.java