كومة وقائمة الانتظار:
يتم استخدامه عمومًا كأداة للمبرمجين للمساعدة في تصور الخوارزميات ، مع دورة حياة قصيرة ويتم إنشاؤها فقط في وقت التشغيل ؛
الوصول مقيد ، وفي لحظة معينة ، يمكن قراءة أو حذف بيانات واحدة فقط ؛
إنه بنية مجردة ، مع آلية تنفيذ داخلية غير مرئية للمستخدمين ، مثل استخدام المصفوفات والقوائم المرتبطة بتنفيذ المكدس.
محاكاة هيكل المكدس
في الوقت نفسه ، لا يُسمح بالوصول إلى بيانات واحدة فقط ، والتعقيد الزمني في وقت لاحق في كل من داخل المكدس والخارج هو O (1) ، أي أنه لا يعتمد على عدد عناصر البيانات في المكدس. العملية سريعة نسبيًا ، باستخدام صفيف كهيكل تخزين للمكدس
مجموعات الفئة العامة <T> {private int max ؛ خاص t [] آري ؛ الجزء العلوي الخاص // Pointer ، subcript to the top element of the stack public acks (int size) {this.max = size ؛ ary = (t []) كائن جديد [max] ؛ أعلى = -1 ؛ } // stack public void push (t data) {if (! isfull ()) ary [++ top] = data ؛ } // stack public t pop () {if (isempty ()) {return null ؛ } إرجاع آري [TOP--] ؛ } // عرض الجزء العلوي من المكدس العام t peek () {return ary [top] ؛ } // هو المكدس الفارغ الفارغ المنطقي isempty () {return top == -1 ؛ } // هو المكدس الكامل boolean isfull () {return top == max - 1 ؛ } // size public int size () {return top + 1 ؛ } main static void main (string [] args) {stacks <integer> stack = new Stacks <integer> (3) ؛ لـ (int i = 0 ؛ i <5 ؛ i ++) {stack.push (i) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } لـ (int i = 0 ؛ i <5 ؛ i ++) {integer peek = stack.peek () ؛ System.out.println ("PEEK:" + PEEK) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } لـ (int i = 0 ؛ i <5 ؛ i ++) {Integer pop = stack.pop () ؛ System.out.println ("pop:" + pop) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } system.out.println ("----") ؛ لـ (int i = 5 ؛ i> 0 ؛ i--) {stack.push (i) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {integer peek = stack.peek () ؛ System.out.println ("PEEK:" + PEEK) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {Integer pop = stack.pop () ؛ System.out.println ("pop:" + pop) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ }}} في المثال أعلاه ، هناك تنظيم MaxSize ، لأن الصفيف يجب أن يكون حجمه. إذا لم تكن لديك أي حد ، فيمكنك استخدام هياكل أخرى للتخزين ، وبالطبع يمكنك أيضًا مجموعة جديدة من الطول الجديد.
على سبيل المثال ، استخدم LinkedList Storage لتنفيذ المكدس
مجموعات الفئة العامة <T> {private LinkedList <T> بيانات ؛ المكدس العام () {datas = new LinkedList <T> () ؛ } // ضع مكدس push push (t data) {datas.addlast (data) ؛ } // ضع المكدس العام t pop () {return datas.removelast () ؛ } // تحقق من الجزء العلوي من المكدس العام t peek () {return datas.getlast () ؛ } // ما إذا كان المكدس فارغًا منطقيًا isEmpty () {return datas.isempty () ؛ } // size public int size () {return datas.size () ؛ } main static void main (string [] args) {stacks <integer> stack = new Stacks <integer> (3) ؛ لـ (int i = 0 ؛ i <5 ؛ i ++) {stack.push (i) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } لـ (int i = 0 ؛ i <5 ؛ i ++) {integer peek = stack.peek () ؛ System.out.println ("PEEK:" + PEEK) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } لـ (int i = 0 ؛ i <5 ؛ i ++) {Integer pop = stack.pop () ؛ System.out.println ("pop:" + pop) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } system.out.println ("----") ؛ لـ (int i = 5 ؛ i> 0 ؛ i--) {stack.push (i) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {stack.push (i) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {integer peek = stack.peek () ؛ System.out.println ("PEEK:" + PEEK) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {Integer pop = stack.pop () ؛ System.out.println ("pop:" + pop) ؛ System.out.println ("الحجم:" + stack.size ()) ؛ }}}على سبيل المثال ، ترتيب عكسي للكلمة ، باستخدام بنية STATCK
الفئة العامة WordReverse {public static void main (string [] args) {revers ("co. ، ltd.") ؛ } عكس الفراغ الثابت (كلمة سلسلة) {if (word == null) return ؛ Stackss <farhtor> stack = acksss new <Charirm> () ؛ char [] chararray = word.tochararray () ؛ int len = chararray.length ؛ لـ (int i = 0 ؛ i <len ؛ i ++) {stack.push (chararray [i]) ؛ } StringBuilder SB = new StringBuilder () ؛ بينما (! stack.isempty ()) {sb.append (stack.pop ()) ؛ } system.out.println ("بعد الانقلاب:" + sb.toString ()) ؛ }}مطبعة:
بعد الانعكاس: النمط الاجتماعي
قائمة انتظار المحاكاة (قائمة الانتظار العامة ، قائمة الانتظار المزدوجة ، قائمة انتظار الأولوية)
طابور:
أولاً في البداية ، تعامل مع مشاكل الانتظار. قائمة الانتظار الأولى ، العملية الأولى ، الصف الأول ، الصف الثاني ، إلخ. تم الانتهاء من العملية السابقة ، وتعقيد الوقت لعمليات الإدراج والإزالة هو O (1). أدخل من الخلف وأزل قائمة الانتظار المزدوجة من الأمام:
وهذا هو ، يمكنك إدراج وإزالة في كلا طرفي قائمة الانتظار: insertleft ، insertright ، removeleft ، removeright
وظائف تحتوي على مكدس وقوائم. إذا قمت بإزالة insertleft و removeleft ، فسيكون هو نفسه المكدس ؛ إذا قمت بإزالة insertleft و readight ، فسيكون ذلك هو نفس قائمة الانتظار. بشكل عام ، يكون تواتر الاستخدام منخفضًا ، وتعقيد الوقت O (1)
قائمة انتظار الأولوية:
الحفاظ على تسلسل داخلي مرتبة حسب الأولوية. عند الإدخال ، تحتاج إلى مقارنة وإيجاد موضع الإدراج ، والتعقيد الزمني O (n) ، حذف O (1)
/** قائمة الانتظار أولاً في البداية ، يشير المؤشر إلى موضع الإدراج ، ويشير المؤشر إلى موضع عنصر البيانات الذي يتم إخراجه*/ Queueq الفئة العامة <T> {private int max ؛ خاص t [] آري ؛ الجبهة الخاصة // يشير رئيس الفريق إلى موضع عنصر البيانات الذي يتم إخراجه من الخلفية الخاصة ؛ // يشير ذيل الفريق إلى موضع عنصر البيانات الذي يتم إدراجه في nitems الخاصة ؛ // العدد الفعلي لعناصر البيانات العامة (int size) {this.max = size ؛ ary = (t []) كائن جديد [max] ؛ الجبهة = 0 ؛ الخلفية = -1 ؛ nitems = 0 ؛ } // أدخل ذيل قائمة انتظار الفراغ العام (t t) {if (rear == max - 1) {// لقد وصلت إلى نهاية قائمة الانتظار الفعلية ، ابدأ من البداية ، الخلفية = -1 ؛ } ary [++ الخلفية] = t ؛ nitems ++ ؛ } // قم بإزالة رأس الفريق العام t remove () {t temp = ary [Front ++] ؛ if (front == max) {// وصلت قائمة الانتظار إلى النهاية ، ابدأ من البداية ، ابدأ من البداية ، ابدأ من البداية ، ابدأ من البداية ، 0 ؛ } nitems-- ؛ عودة درجة الحرارة. } // عرض رئيس الفريق العام t peak () {return ary [Front] ؛ } boolean public isempty () {return nitems == 0 ؛ } boolean public isfull () {return nitems == max ؛ } size int public () {return nitems ؛ } public static void main (string [] args) {QueUeQ <integer> Queue = new QueUeQ <integer> (3) ؛ لـ (int i = 0 ؛ i <5 ؛ i ++) {queue.insert (i) ؛ system.out.println ("size:" + queue.size ()) ؛ } لـ (int i = 0 ؛ i <5 ؛ i ++) {integer peek = queue.peek () ؛ System.out.println ("PEEK:" + PEEK) ؛ system.out.println ("size:" + queue.size ()) ؛ } لـ (int i = 0 ؛ i <5 ؛ i ++) {integer remove = queue.remove () ؛ System.out.println ("إزالة:" + إزالة) ؛ system.out.println ("size:" + queue.size ()) ؛ } system.out.println ("----") ؛ لـ (int i = 5 ؛ i> 0 ؛ i--) {queue.insert (i) ؛ system.out.println ("size:" + queue.size ()) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {integer peek = queue.peek () ؛ System.out.println ("PEEK:" + PEEK) ؛ system.out.println ("size:" + queue.size ()) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {integer remove = queue.remove () ؛ System.out.println ("إزالة:" + إزالة) ؛ system.out.println ("size:" + queue.size ()) ؛ }}} /** قائمة انتظار مزدوجة النهاية <span style = "White-Space: Pre"> </span> أدخل وحذف في كلا الطرفين*/QueueQt <T> {Private LinkedList <T> ؛ public queueqt () {list = new LinkedList <T> () ؛ } // أدخل رأس قائمة الانتظار public void insertleft (t t) {list.addfirst (t) ؛ }. }. } // قم بإزالة نهاية فريق t removeright () {return list.removelast () ؛ } // عرض رئيس الفريق العام t peekleft () {return list.getFirst () ؛ } // عرض نهاية الفريق العام t peekright () {return list.getlast () ؛ } boolean public isempty () {return list.isempty () ؛ } public int size () {return list.size () ؛ }} /** يتم فرز قائمة انتظار الأولوية حسب الأولوية ، وهي قائمة انتظار مرتبة*/ QueueQp {private int max ؛ private int [] ary ؛ NITEMS الخاصة ؛ // العدد الفعلي لعناصر البيانات العامة QueUeQP (int size) {this.max = size ؛ ary = new int [max] ؛ nitems = 0 ؛ } // إدراج نهاية قائمة الانتظار public void insert (int t) {int j ؛ if (nitems == 0) {ary [nitems ++] = t ؛ } آخر {for (j = nitems-1 ؛ j> = 0 ؛ j--) {if (t> ary [j]) {ary [j + 1] = ary [j] ؛ // تعيين واحد سابق إلى واحد التالي يعادل استخدام فرز الإدراج. يتم ترتيب التسلسل المعطى في الأصل ، لذلك كفاءة o (n)} آخر {break ؛ }} ary [j + 1] = t ؛ nitems ++ ؛ } system.out.println (arrays.toString (ary)) ؛ } // قم بإزالة رأس الفريق العام int () {return ary [-nitems] ؛ . } boolean public isempty () {return nitems == 0 ؛ } boolean public isfull () {return nitems == max ؛ } size int public () {return nitems ؛ } public static void main (string [] args) {QueUeQP Queue = new QueUeQP (3) ؛ queue.insert (1) ؛ queue.insert (2) ؛ Queue.insert (3) ؛ int remove = queue.remove () ؛ System.out.println ("إزالة:" + إزالة) ؛ }}