در این جلسه تیم کدگیت را با آموزش پشته در سی پلاس پلاس همراهی کنید. پیش نیاز این جلسه شامل موارد زیر است:
پشته(stack)
پشته یکی از انواع داده‌ساختارها است و برای ذخیره و بازیابی دادهها کاربرد دارد. پشته به شما اجازه دسترسی به یک شی (object) را میدهد، آخرین شی که وارد پشته شده است. اگر ما آخرین شی را حذف کنیم میتوانیم به شی یکی مانده به آخر دسترسی داشته باشیم و همینطور تا آخر …… .ساختار پشته به صورت تصویر زیر است.
برای توضیح دادن پشته بهتر است یک مثال ساده بزنیم.مثال در مورد قرار دادن نامه(email هم میشود)است. فرض کنید ما نامه هایی که به دستمان میرسد را روی هم قرار میدهیم پس میتوان نتیجه گرفت نامه ای که بالاتر از همه قرار دارد همین اواخر و زودتر از بقیه به دست شما رسیده است. دومین نامه نسبت به نامه های زیری خود همین ویژگی را دارد.اگر نامه ای بیاید شما آن را در اول قرار می دهید و روی همه نامه های دیگر. معمولا ما با نامه هایی کار داریم که جدید هستند و نامه های قدیمی بعضی از آنها نگه میداریم بعضی از آنها را به زباله می اندازیم!!!
این روند که توضیح داده شد تقریبا کاری است که پشته انجام میدهد. پشته مانند نامه ها اول خالی است سپس با آمدن نامه جدید به پشته یک عنصر وارد می شود. با مطالعه نامه میتوانید آن را دور بیندازید یا آن را سر جای قبلش قرار دهید د پشته شما میتوانید دقیقا همین اعمال انجام دهید. خلاصه کارهایی که با پشته میشود انجام داد:
- Push: اضافه کردن عنصری به پشته.(آمدن نامه جدید)
- Pop: حذف بالاترین(جدیدترین) عنصر در پشته(دور انداختن نامه)
- Peek: دسترسی به بالاترین(جدیدترین) عنصر در پشته(بررسی نامه های جدید)
- Size: تعداد عناصر پشته (تعداد نامه ها )
برای پیاده سازی ما میتوانیم از دو راه استفاده کنیم:
- پیاده سازی پشته با لیست پیوندی
- پیاده سازی پشته با آرایه
در این آموزش فقط به پیاده سازی پشته با آرایه خواهیم پرداخت.
پیاده سازی پشته در سی پلاس پلاس با آرایه
در این قسمت به پیاده سازی پشته در سی پلاس پلاس توسط آرایه خواهیم پرداخت. ایده کار به این صورت است که ابتدا یک آرایه بزرگ در نظر می‌گیریم و عناصر خود را در آن می‌ریزیم. محتوای این آرایه اعدادی است که به stack اضافه می‌شوند. کد زیر پیاده سازی این نوع stack را نشان میدهد.
#define MAX 1000
class Stack {
int top;
public:
int a[MAX]; //Maximum size of Stack
Stack() {
top = -1;
}
bool push(int x);
int pop();
bool isEmpty();
};
bool Stack::push(int x) {
if (top >= (MAX - 1)) {
cout << "Stack Overflow";
return false;
} else {
a[++top] = x;
cout << x << " pushed into stack\n";
return true;
}
}
int Stack::pop() {
if (top < 0) {
cout << "Stack Underflow";
return 0;
} else {
int x = a[top--];
return x;
}
}
bool Stack::isEmpty() {
return (top < 0);
}
در کد بالا متغیری به نام top داریم که به به عنصری که در آخر وارد Stack شده است اشاره دارد. هنگام push یکی به top اضافه خواهد شد و در هنگام pop یکی از آن کم میشود. همچنین تابع main هم به صورت زیر است.
int main() {
struct Stack s;
s.push(10);
s.push(20);
s.push(30);
cout << s.pop() << " Popped from stack\n";
return 0;
}
خروجی کد بالا به صورت زیر است:
10 pushed into stack
20 pushed into stack
30 pushed into stack
30 Popped from stack
