Tumpukan dan antrian:
Ini umumnya digunakan sebagai alat bagi pemrogram untuk membantu dalam konsepsi algoritma, dengan siklus hidup yang singkat dan dibuat hanya saat runtime;
Akses dibatasi, dan pada saat tertentu, hanya satu data yang dapat dibaca atau dihapus;
Ini adalah struktur abstrak, dengan mekanisme implementasi internal yang tidak terlihat oleh pengguna, seperti menggunakan array dan daftar tertaut untuk mengimplementasikan tumpukan.
Simulasi struktur tumpukan
Pada saat yang sama, hanya satu data yang diakses untuk diakses, dan kompleksitas waktu dari yang terakhir di-pertama untuk di dalam tumpukan maupun keluar adalah O (1), yaitu, itu tidak tergantung pada jumlah item data dalam tumpukan. Operasi relatif cepat, menggunakan array sebagai struktur penyimpanan tumpukan
Tumpukan kelas publik <T> {private int max; Private t [] ary; private int top; // pointer, subskrip ke elemen teratas tumpukan publik tumpukan (ukuran int) {this.max = size; ary = (t []) objek baru [max]; top = -1; } // menumpuk public void push (data t) {if (! Isfull ()) ary [++ top] = data; } // stack public t pop () {if (isEmpty ()) {return null; } return ary [top--]; } // Lihat bagian atas tumpukan publik t peek () {return ary [top]; } // adalah tumpukan public boolean yang kosong () {return top == -1; } // adalah stack full public boolean isfull () {return top == max - 1; } // ukuran ukuran int publik () {return top + 1; } public static void main (string [] args) {stacks <integer> stack = stack baru <Integer> (3); untuk (int i = 0; i <5; i ++) {stack.push (i); System.out.println ("size:" + stack.size ()); } untuk (int i = 0; i <5; i ++) {integer peek = stack.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + stack.size ()); } untuk (int i = 0; i <5; i ++) {integer pop = stack.pop (); System.out.println ("Pop:" + Pop); System.out.println ("size:" + stack.size ()); } System.out.println ("----"); untuk (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("size:" + stack.size ()); } untuk (int i = 5; i> 0; i--) {integer peek = stack.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + stack.size ()); } untuk (int i = 5; i> 0; i--) {integer pop = stack.pop (); System.out.println ("Pop:" + Pop); System.out.println ("size:" + stack.size ()); }}} Dalam contoh di atas, ada regulasi maksimum, karena array harus berukuran. Jika Anda ingin tidak memiliki batasan, Anda dapat menggunakan struktur lain untuk penyimpanan, dan tentu saja Anda juga dapat baru dan baru dengan panjang baru.
Contoh, gunakan penyimpanan LinkedList untuk mengimplementasikan tumpukan
Stackss kelas publik <T> {private LinkedList <T> data; stackss publics () {dataS = new LinkedList <T> (); } // letakkan stack public void push (data t) {datas.addLast (data); } // letakkan stack public t pop () {return datas.removelast (); } // Periksa bagian atas tumpukan publik t peek () {return datas.getLast (); } // apakah tumpukannya kosong boolean public isempty () {return datas.isempty (); } // ukuran ukuran int publik () {return datas.size (); } public static void main (string [] args) {stacks <integer> stack = stack baru <Integer> (3); untuk (int i = 0; i <5; i ++) {stack.push (i); System.out.println ("size:" + stack.size ()); } untuk (int i = 0; i <5; i ++) {integer peek = stack.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + stack.size ()); } untuk (int i = 0; i <5; i ++) {integer pop = stack.pop (); System.out.println ("Pop:" + Pop); System.out.println ("size:" + stack.size ()); } System.out.println ("----"); untuk (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("size:" + stack.size ()); } untuk (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("size:" + stack.size ()); } untuk (int i = 5; i> 0; i--) {integer peek = stack.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + stack.size ()); } untuk (int i = 5; i> 0; i--) {integer pop = stack.pop (); System.out.println ("Pop:" + Pop); System.out.println ("size:" + stack.size ()); }}}Contoh, urutan balik kata, menggunakan struktur statck
Public Class Wordreverse {public static void main (string [] args) {reverse ("co., ltd."); } static void reverse (string word) {if (word == null) return; Stackss <chorate> stack = Stackss baru <caracter> (); char [] chararray = word.tochararray (); int len = chararray.length; untuk (int i = 0; i <len; i ++) {stack.push (chararray [i]); } StringBuilder SB = StringBuilder baru (); while (! stack.isempty ()) {sb.append (stack.pop ()); } System.out.println ("Setelah inversi:" + sb.tostring ()); }}Mencetak:
Setelah pembalikan: gaya sosial
Antrian Simulasi (Antrian Umum, Antrian Ganda, Antrian Prioritas)
antre:
Pertama di First Out, berurusan dengan masalah antrian. Antrian pertama, proses pertama, baris pertama, baris kedua, dll. Proses sebelumnya selesai, dan kompleksitas waktu operasi penyisipan dan penghapusan adalah O (1). Sisipkan dari belakang dan lepaskan antrian ganda dari depan:
Yaitu, Anda dapat memasukkan dan menghapus di kedua ujung antrian: masukkan, intertright, removeleft, removeright
Fungsi yang berisi tumpukan dan antrian. Jika Anda menghapus insertleft dan removeleft, itu akan sama dengan tumpukan; Jika Anda menghapus insertleft dan removeright, itu akan sama dengan antrian. Secara umum, frekuensi penggunaannya rendah, dan kompleksitas waktu O (1)
Antrian Prioritas:
Pertahankan urutan internal yang diurutkan berdasarkan prioritas. Saat memasukkan, Anda perlu membandingkan dan menemukan posisi penyisipan, kompleksitas waktu o (n), hapus o (1)
/** Antrian pertama di First Out, pointer menunjukkan posisi penyisipan, dan pointer menunjukkan posisi item data yang diambil*/ kelas publik QueueQ <T> {private int max; Private t [] ary; Private Int Front; // Kepala tim menunjukkan posisi item data yang dikeluarkan di belakang pribadi; // ekor tim menunjukkan posisi item data yang dimasukkan secara pribadi; // Jumlah aktual item data Queueq publik (ukuran int) {this.max = size; ary = (t []) objek baru [max]; depan = 0; belakang = -1; nitem = 0; } // Masukkan ekor dari antrian public void insert (tt) {if (belakang == maks - 1) {// telah mencapai ujung antrian yang sebenarnya, mulai dari awal, belakang = -1; } ary [++ belakang] = t; nitem ++; } // Hapus kepala tim publik t lepaskan () {t temp = ary [front ++]; if (front == max) {// Antrian telah mencapai akhir, mulai dari awal, mulai dari awal, mulai dari awal, mulai dari awal, 0; } nitem--; kembalikan suhu; } // Lihat Kepala Tim Publik T Peek () {return ary [Front]; } public boolean isEmpty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (string [] args) {queueq <integer> queue = queueq baru <integer> (3); untuk (int i = 0; i <5; i ++) {queue.insert (i); System.out.println ("Size:" + Queue.size ()); } untuk (int i = 0; i <5; i ++) {integer peek = queue.peek (); System.out.println ("Peek:" + Peek); System.out.println ("Size:" + Queue.size ()); } untuk (int i = 0; i <5; i ++) {integer reme = queue.remove (); System.out.println ("Hapus:" + Hapus); System.out.println ("Size:" + Queue.size ()); } System.out.println ("----"); untuk (int i = 5; i> 0; i--) {queue.insert (i); System.out.println ("Size:" + Queue.size ()); } untuk (int i = 5; i> 0; i--) {integer peek = queue.peek (); System.out.println ("Peek:" + Peek); System.out.println ("Size:" + Queue.size ()); } for (int i = 5; i> 0; i--) {integer reme = queue.remove (); System.out.println ("Hapus:" + Hapus); System.out.println ("Size:" + Queue.size ()); }}} /** Antrian ganda <span style = "white-space: pre"> </span> masukkan dan hapus di kedua ujungnya*/kelas publik QueueQt <T> {daftar private linkedList <T>; queueqt publik () {list = new LinkedList <T> (); } // masukkan kepala antrian public void insertleft (tt) {list.addfirst (t); } // Masukkan antrian public void inertright (tt) {list.addLast (t); } // Hapus head public t public t removeleft () {return list.removefirst (); } // Hapus akhir dari tim public t removeright () {return list.removelast (); } // Lihat Kepala Tim Publik T Peekleft () {return list.getFirst (); } // lihat akhir dari tim publik t peekright () {return list.getLast (); } public boolean isEmpty () {return list.isempty (); } public int size () {return list.size (); }} /** Antrian prioritas diurutkan berdasarkan prioritas, dan itu adalah antrian yang dipesan*/ kelas publik antrian {private int max; private int [] ary; nitem pribadi; // Jumlah aktual item data QueueQP publik (ukuran int) {this.max = size; ary = int new [max]; nitem = 0; } // Masukkan ujung antrian public void insert (int t) {int j; if (nitems == 0) {ary [nitems ++] = t; } else {for (j = nitems-1; j> = 0; j--) {if (t> ary [j]) {ary [j + 1] = ary [j]; // Tetapkan yang sebelumnya ke yang berikutnya setara dengan menggunakan penyortiran penyisipan. Urutan yang diberikan awalnya dipesan, sehingga efisiensi o (n)} else {break; }} ary [j + 1] = t; nitem ++; } System.out.println (arrays.tostring (ARY)); } // Hapus kepala tim int rape () {return ary [-nitems]; // Hapus prioritas kecil} // Lihat prioritas terendah dari tim publik int peekmin () {return ary [nitems - 1]; } public boolean isEmpty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (string [] args) {queueqp queue = queueqp baru (3); Queue.insert (1); Queue.insert (2); Queue.insert (3); int hapus = queue.remove (); System.out.println ("Hapus:" + Hapus); }}