Java Stack
پشته(stack)
Java Stack
پشته یکی از انواع داده‌ساختارها است و برای ذخیره و بازیابی دادهها کاربرد دارد. پشته به شما اجازه دسترسی به یک شی (object) را میدهد، آخرین شی که وارد پشته شده است. اگر ما آخرین شی را حذف کنیم میتوانیم به شی یکی مانده به آخر دسترسی داشته باشیم و همینطور تا آخر …
برای توضیح دادن پشته بهتر است یک مثال ساده بزنیم.مثال در مورد قرار دادن نامه(email هم میشود)است. فرض کنید ما نامه هایی که به دستمان میرسد را روی هم قرار میدهیم پس میتوان نتیجه گرفت نامه ای که بالاتر از همه قرار دارد همین اواخر و زودتر از بقیه به دست شما رسیده است. دومین نامه نسبت به نامه های زیری خود همین ویژگی را دارد.اگر نامه ای بیاید شما آن را در اول قرار می دهید و روی همه نامه های دیگر. معمولا ما با نامه هایی کار داریم که جدید هستند و نامه های قدیمی بعضی از آنها نگه میداریم بعضی از آنها را به زباله می اندازیم!!!
این روند که توضیح داده شد تقریبا کاری است که پشته انجام میدهد. پشته مانند نامه ها اول خالی است سپس با آمدن نامه جدید به پشته یک عنصر وارد می شود. با مطالعه نامه میتوانید آن را دور بیندازید یا آن را سر جای قبلش قرار دهید در پشته شما میتوانید دقیقا همین اعمال انجام دهید. خلاصه کارهایی که با پشته میشود انجام داد:
- Push: اضافه کردن عنصری به پشته.(آمدن نامه جدید)
- Pop: حذف بالاترین(جدیدترین) عنصر در پشته(دور انداختن نامه)
- Peek: دسترسی به بالاترین(جدیدترین) عنصر در پشته(بررسی نامه های جدید)
- Size: تعداد عناصر پشته (تعداد نامه ها )
برای پیاده سازی ما میتوانیم از دو راه استفاده کنیم:
- پیاده سازی پشته با لیست پیوندی
- پیاده سازی پشته با آرایه
پیاده سازی پشته با لیست پیوندی
Java Stack
برای پیاده سازی پشته با لیست پیوندی ابتدا باید با لیست پیوندی و انواع آن آشنا باشید.
پیاده سازی لیست پیوندی به طوری که ما را به هدف خودمان برساند بسیار ساده است. برای این کار ما از single linkedlist استفاده میکنیم و هر عنصر جدید(push) که وارد لیست ما شد ما آن را first قرار می دهیم.
برای حذف یک عنصر(pop) ما اشاره گره first را به یک خانه جلوتر میبریم و تمام!!!!(به همین سادگی) برای peek صدا زدن ما فقط کافی است first را برگردانیم!!!! حال بهتر است کد توضیحات داده شده را بزنیم.ابتدا کلاس Node میسازیم.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public class Node<Item> { private Item data; private Node next_node; public Node(Item data, Node next_node) { this.data = data; this.next_node = next_node; } public Item getData() { return data; } public Node getNext_node() { return next_node; } } |
سپس کلاس دیگری به نام StackWithList میسازیم.در این کلاس stack را میسازیم.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | public class StackWithList<Item> { private int N; // size of the stack private Node first; // top of stack public StackWithList() { super(); N = 0; this.first = null; } public boolean isEmpty() { return first == null; } public int size() { return N; } public void push(Item item) { Node oldfirst = first; first = new Node(item, oldfirst); N++; } public Item pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); Item item = (Item) first.getData(); first = first.getNext_node(); // delete first node N--; return item; // return the saved item } public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return (Item) first.getData(); } public Iterator<Item> iterator() { return new ListIterator(first); } } |
کلاس iterator هم برای Stack خود مینویسیم.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class ListIterator<Item> implements Iterator<Item> { private Node<Item> current; public ListIterator(Node<Item> first) { current = first; } public boolean hasNext() { return current != null; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.getData(); current = current.getNext_node(); return item; } } |
یک main هم برای برنامه خود مینویسیم.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | public static void main(String[] args) { StackWithList<String> stack = new StackWithList<String>(); stack.push("jack"); stack.push("mike"); stack.push("dany"); System.out.println(stack.pop()); System.out.println("------ items after pop ------"); for (Iterator iterator = stack.iterator(); iterator.hasNext();) { String type = (String) iterator.next(); System.out.println(type); } } |
در متد main ما یک stack ساختیم و به آن سه string اضافه کردیم. سپس یک عنصر را pop کردیم(آخرین عنصر). سپس یک iterator ساختیم و کل stack را بعد از pop چاپ میکند.
پیاده سازی پشته با آرایه
Java Stack
در این قسمت به پیاده سازی پشته توسط آرایه خواهیم پرداخت.ایده کار به این صورت است که ابتدا یک آرایه کوچک در نظر میگیریم(ابتدا به طول دو) و هر بار آرایه ما پر شد طول آن را دو برابر می کنیم. محتوای این آرایه object هایی است که به stack اضافه میشوند. کد زیر پیاده سازی این نوع stack را نشان میدهد.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | public class StackWithArray<Item> { private Item[] a; // array of items private int N; public StackWithArray() { super(); a = (Item[]) new Object[2]; } public boolean isEmpty() { return N == 0; } public int size() { return N; } private void resize(int capacity) { assert capacity >= N; Item[] temp = (Item[]) new Object[capacity]; for (int i = 0; i < N; i++) { temp[i] = a[i]; } a = temp; } public void push(Item item) { if (N == a.length) resize(2 * a.length); // double size of array if necessary a[N++] = item; } public Item pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); Item item = a[N - 1]; a[N - 1] = null; N--; // shrink size of array if necessary if (N > 0 && N == a.length / 4) resize(a.length / 2); return item; } public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return a[N-1]; } public Iterator<Item> iterator() { return new ReverseIterator(N,a); } } |
در این جا چون آرایه استفاده میکنیم نیاز به یک iterator که از بالای Stack شروع به خواندن کند، داریم.اسم این کلاس reverseIterator میگذاریم.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public class ReverseIterator<Item> implements Iterator<Item> { private int i; private Item[] data; public ReverseIterator(int N,Item[] data) { i = N; this.data = data; } public boolean hasNext() { return i > 0; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); return data[--i]; } } |
متد main هم دقیقا شبیه پیاده سازی پشته با لیست پیوندی است.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public static void main(String[] args) { System.out.println("Stack with array"); StackWithArray<String> stack = new StackWithArray<String>(); stack.push("jack"); stack.push("mike"); stack.push("dany"); System.out.println(stack.pop()); System.out.println("------ items after pop ------"); for (Iterator iterator = stack.iterator(); iterator.hasNext();) { String type = (String) iterator.next(); System.out.println(type); } } |
Java Stack Java Stack Java Stack Java Stack
