.NET Tips | جستجوها: نتایج مشابه «Stack Overflow برای کاربران Português»، صفحه: ۴۸

مطالب

بررسی استراتژی‌های تشخیص تغییرات در برنامه‌های Angular

وقتی تغییری را در اشیاء خود به وجود می‌آورید، Angular بلافاصله متوجه آن‌ها شده و viewها را به روز رسانی می‌کند. هدف از این مکانیزم، اطمینان حاصل کردن از همگام بودن اشیاء مدل‌ها و viewها هستند. آگاهی از نحوه‌ی انجام این عملیات، کمک شایانی را به بالابردن کارآیی یک برنامه‌ی با رابط کاربری پیچیده‌ای می‌کند. یک شیء مدل در Angular عموما به سه طریق تغییر می‌کند:
- بروز رخ‌دادهای DOM مانند کلیک
- صدور درخواست‌های Ajax ایی
- استفاده از تایمرها (setTimer, setInterval)

ردیاب‌های تغییرات در Angular

تمام برنامه‌های Angular در حقیقت سلسله مراتبی از کامپوننت‌ها هستند. در زمان اجرای برنامه، Angular به ازای هر کامپوننت، یک تشخیص دهنده‌ی تغییرات را ایجاد می‌کند که در نهایت سلسله مراتب ردیاب‌ها را همانند سلسله مراتب کامپوننت‌ها ایجاد خواهد کرد. هر زمانیکه ردیابی فعال می‌شود، Angular این درخت را پیموده و مواردی را که تغییراتی را گزارش داده‌اند، بررسی می‌کند. این پیمایش به ازای هر تغییر رخ داده‌ی در مدل‌های برنامه صورت می‌گیرد و همواره از بالای درخت شروع شده و به صورت ترتیبی تا پایین آن ادامه پیدا می‌کند:

این پیمایش ترتیبی از بالا به پایین، از این جهت صورت می‌گیرد که اطلاعات کامپوننت‌ها از والدین آن‌ها تامین می‌شوند. تشخیص دهنده‌های تغییرات، روشی را جهت ردیابی وضعیت پیشین و فعلی یک کامپوننت ارائه می‌دهد تا Angular بتواند تغییرات رخ‌داده را منعکس کند. اگر Angular گزارش تغییری را از یک تشخیص دهنده‌ی تغییر دریافت کند، کامپوننت مرتبط را مجددا ترسیم کرده و DOM را به روز رسانی می‌کند.

استراتژی‌های تشخیص تغییرات در Angular

برای درک نحوه‌ی عملکرد سیستم تشخیص تغییرات نیاز است با مفهوم value types و reference types در JavaScript آشنا شویم. در JavaScript نوع‌های زیر value type هستند:

• Boolean
• Null
• Undefined
• Number
• String

و نوع‌های زیر Reference type محسوب می‌شوند:

• Arrays
• Objects
• Functions

مهم‌ترین تفاوت بین این دو نوع، این است که برای دریافت مقدار یک value type فقط کافی است از stack memory کوئری بگیریم. اما برای دریافت مقادیر reference types باید ابتدا در جهت یافتن شماره ارجاع آن، از stack memory کوئری گرفته و سپس بر اساس این شماره ارجاع، اصل مقدار آن‌را در heap memory پیدا کنیم.
این دو تفاوت را می‌توان در شکل زیر بهتر مشاهده کرد:

استراتژی Default یا پیش‌فرض تشخیص تغییرات در Angular

همانطور که پیشتر نیز عنوان شد، Angular تغییرات یک شیء مدل را در جهت تشخیص تغییرات و انعکاس آن‌ها به View برنامه، ردیابی می‌کند. در این حالت هر تغییری بین حالت فعلی و پیشین یک شیء مدل برای این منظور بررسی می‌گردد. در اینجا Angular این سؤال را مطرح می‌کند: آیا مقداری در این مدل تغییر یافته‌است؟
اما برای یک reference type می‌توان سؤالات بهتری را مطرح کرد که بهینه‌تر و سریعتر باشند. اینجاست که استراتژی OnPush تشخیص تغییرات مطرح می‌شود.

استراتژی OnPush تشخیص تغییرات در Angular

ایده اصلی استراتژی OnPush تشخیص تغییرات در Angular در immutable فرض کردن reference types نهفته‌است. در این حالت هر تغییری در شیء مدل، سبب ایجاد یک ارجاع جدید به آن در stack memory می‌شود. به این ترتیب می‌توان تشخیص تغییرات بسیار سریعتری را شاهد بود. چون دیگر در اینجا نیازی نیست تمام مقادیر یک شیء را مدام تحت نظر قرار داد. همینقدر که ارجاع آن در stack memory تغییر کند، یعنی مقادیر این شیء در heap memory تغییر یافته‌اند.
در این حالت Angular دو سؤال را مطرح می‌کند: آیا ارجاع به یک reference type در stack memory تغییر یافته‌است؟ اگر بله، آیا مقادیر آن در heap memory تغییر کرده‌اند؟ برای مثال جهت بررسی تغییرات یک آرایه‌ی با 30 عضو، دیگر در ابتدای کار نیازی نیست تا هر 30 عضو آن بررسی شوند (برخلاف حالت پیش‌فرض بررسی تغییرات). در حالت استراتژی OnPush، ابتدا مقدار ارجاع این آرایه در stack memory بررسی می‌شود. اگر تغییری در آن صورت گرفته بود، به معنای تغییری در اعضای آرایه‌است.
استراتژی OnPush در یک کامپوننت به نحو ذیل فعال و انتخاب می‌شود و مقدار پیش‌فرض آن ChangeDetectionStrategy.Default است:

 import {ChangeDetectionStrategy, Component} from '@angular/core';
@Component({
  // ...
  changeDetection: ChangeDetectionStrategy.OnPush
})
export class OnPushComponent {
  // ...
}

استراتژی OnPush تغییرات یک کامپوننت را در حالت‌های ذیل نیز ردیابی می‌کند:
- اگر مقدار یک خاصیت از نوع Input@ تغییر کند.
- اگر یک event handler رخ‌دادی را صادر کند.
- اگر سیستم ردیابی به صورت دستی فراخوانی شود.
- اگر سیستم ردیاب تغییرات child component آن، اجرا شود.

نوع‌های ارجاعی Immutable

همانطور که عنوان شد، شرط کار کردن استراتژی OnPush، داشتن نوع‌های ارجاعی immutable است. اما نوع ارجاعی immutable چیست؟
Immutable بودن به زبان ساده به این معنا است که ما هیچگاه جهت تغییر مقدار خاصیتی در یک شیء، آن خاصیت را مستقیما مقدار دهی نمی‌کنیم؛ بلکه کل شیء را مجددا مقدار دهی می‌کنیم.
برای نمونه در مثال زیر، خاصیت foo شیء before مستقیما مقدار دهی شده‌است:

static mutable() {
  var before = {foo: "bar"};
  var current = before;
  current.foo = "hello";
  console.log(before === current);
  // => true
}

اما اگر بخواهیم با آن به صورت Immutable «رفتار» کنیم، کل این شیء را جهت اعمال تغییرات، مقدار دهی مجدد خواهیم کرد:

static immutable() {
  var before = {foo: "bar"};
  var current = before;
  current = {foo: "hello"};
  console.log(before === current);
  // => false
}

البته باید دقت داشت در هر دو مثال، شیء‌های ایجاد شده در اصل mutable هستند؛ اما در مثال دوم، با این شیء به صورت immutable «رفتار» شده‌است و صرفا «تظاهر» به رفتار immutable با یک شیء ارجاعی صورت گرفته‌است.

معرفی کتابخانه‌ی Immutable.js

جهت ایجاد اشیاء واقعی immutable کتابخانه‌ی Immutable.js توسط Facebook ایجاد شده‌است و برای کار با استراتژی تشخیص تغییرات OnPush در Angular بسیار مناسب است.
برای نصب آن دستور ذیل را صادر نمائید:

npm install immutable --save

یک نمونه مثال از کاربرد ساختارهای داده‌ی List و Map آن برای کار با آرایه‌ها و اشیاء:

import {Map, List} from 'immutable';

var foobar = {foo: "bar"};
var immutableFoobar = Map(foobar);
console.log(immutableFooter.get("foo"));
// => bar

var helloWorld = ["Hello", "World!"];
var immutableHelloWorld = List(helloWorld);
console.log(immutableHelloWorld.first());
// => Hello
console.log(immutableHelloWorld.last());
// => World!
helloWorld.push("Hello Mars!");
console.log(immutableHelloWorld.last());
// => Hello Mars!

تغییر ارجاع به یک شیء با استفاده از spread properties

const user = {
  name: 'Max',
  age: 30
}
user.age = 31

در این مثال تنها خاصیت age شیء user به روز رسانی می‌شود. بنابراین ارجاع به این شیء تغییر نخواهد کرد و اگر از روش changeDetection: ChangeDetectionStrategy.OnPush استفاده کنیم، رابط کاربری برنامه به روز رسانی نخواهد شد و این تغییر صرفا با بررسی عمیق تک تک خواص این شیء با وضعیت قبلی آن قابل تشخیص است (یا همان حالت پیش فرض بررسی تغییرات در Angular و نه حالت OnPush).
اگر علاقمند به استفاده‌ی از یک کتابخانه‌ی اضافی مانند Immutable.js در کدهای خود نباشید، روش دیگری نیز برای تغییر ارجاع به یک شیء وجود دارد:

const user = {
  name: 'Max',
  age: 30
}
const modifiedUser = { ...user, age: 31 }

در اینجا با استفاده از spread properties یک شیء کاملا جدید ایجاد شده‌است و ارجاع به آن با ارجاع به شیء user یکی نیست.

نمونه‌ی دیگر آن در حین کار با متد push یک آرایه‌است:

export class AppComponent {
  foods = ['Bacon', 'Lettuce', 'Tomatoes'];
 
  addFood(food) {
    this.foods.push(food);
  }
}

متد push، بدون تغییر ارجاعی به آرایه‌ی اصلی، عضوی را به آن آرایه اضافه می‌کند. بنابراین اعضای اضافه شده‌ی به آن نیز توسط استراتژی OnPush قابل تشخیص نیستند. اما اگر بجای متد push از spread operator استفاده کنیم:

addFood(food) {
  this.foods = [...this.foods, food];
}

اینبار this.food به یک شیء کاملا جدید اشاره می‌کند که ارجاع به آن، با ارجاع به شیء this.food قبلی یکی نیست. بنابراین استراتژی OnPush قابلیت تشخیص تغییرات آن‌را دارد.

آگاه سازی دستی موتور تشخیص تغییرات Angular در حالت استفاده‌ی از استراتژی OnPush

تا اینجا دریافتیم که استراتژی OnPush تنها به تغییرات ارجاعات به اشیاء پاسخ می‌دهد و به نحوی باید این ارجاع را با هر به روز رسانی تغییر داد. اما روش دیگری نیز برای وادار کردن این سیستم به تغییر وجود دارد:

 import { Component,  Input, ChangeDetectionStrategy, ChangeDetectorRef } from '@angular/core';
 
@Component({
  selector: 'app-child',
  templateUrl: './child.component.html',
  changeDetection: ChangeDetectionStrategy.OnPush
})
export class ChildComponent {
  @Input() data: string[];
 
  constructor(private cd: ChangeDetectorRef) {}
 
  refresh() {
      this.cd.detectChanges();
  }
}

در این کامپوننت از استراتژی OnPush استفاده شده‌است. در اینجا می‌توان همانند قبل با اشیاء و آرایه‌های موجود کار کرد (بدون اینکه ارجاعات به آن‌ها را تغییر دهیم و یا آن‌ها را immutable کنیم) و در پایان کار، متد detectChanges سرویس ChangeDetectorRef را به صورت دستی فراخوانی کرد تا Angular کار رندر مجدد view این کامپوننت را بر اساس تغییرات آن انجام دهد (کل کامپوننت به عنوان یک کامپوننت تغییر کرده به سیستم ردیابی تغییرات معرفی می‌شود).

کار با Observables در حالت استفاده‌ی از استراتژی OnPush

مطلب «صدور رخدادها از سرویس‌ها به کامپوننت‌ها در برنامه‌های Angular» را در نظر بگیرید. Observables نیز ما را از تغییرات رخ‌داده آگاه می‌کنند؛ اما برخلاف immutable objects با هر تغییری که رخ می‌دهد، ارجاع به آن‌ها تغییری نمی‌کند. آن‌ها تنها رخ‌دادی را به مشترکین، جهت اطلاع رسانی از تغییرات صادر می‌کنند.
بنابراین اگر از Observables و استراتژی OnPush استفاده کنیم، چون ارجاع به آن‌ها تغییری نمی‌کند، رخ‌دادهای صادر شده‌ی توسط آن‌ها ردیابی نخواهند شد. برای رفع این مشکل، امکان علامتگذاری رخ‌دادهای Observables به تغییر کرده پیش‌بینی شده‌است.
در اینجا کامپوننتی را داریم که قابلیت صدور رخ‌دادها را از طریق یک BehaviorSubject دارد:

 import { Component } from '@angular/core';
import { BehaviorSubject } from 'rxjs/BehaviorSubject';
 
@Component({ ... })
export class AppComponent {
  foods = new BehaviorSubject(['Bacon', 'Letuce', 'Tomatoes']);
 
  addFood(food) {
     this.foods.next(food);
  }
}

و کامپوننت دیگری توسط خاصیت ورودی data از نوع Observable در متد ngOnInit، مشترک آن خواهد شد:

 import { Component, Input, ChangeDetectionStrategy, ChangeDetectorRef, OnInit } from '@angular/core';
import { Observable } from 'rxjs/Observable';
 
@Component({
  selector: 'app-child',
  templateUrl: './child.component.html',
  changeDetection: ChangeDetectionStrategy.OnPush
})
export class ChildComponent implements OnInit {
  @Input() data: Observable<any>;
  foods: string[] = [];
 
  constructor(private cd: ChangeDetectorRef) {}
 
  ngOnInit() {
     this.data.subscribe(food => {
        this.foods = [...this.foods, ...food];
     });
  }

در این حالت چون از ChangeDetectionStrategy.OnPush استفاده می‌شود و ارجاع به this.data این observable با هر بار صدور رخ‌دادی توسط آن، تغییر نمی‌کند، سیستم ردیابی تغییرات آن‌را به عنوان تغییر کرده درنظر نمی‌گیرد. برای رفع این مشکل تنها کافی است رخ‌دادگردان آن‌را با متد markForCheck علامتگذاری کنیم:

ngOnInit() {
  this.data.subscribe(food => {
      this.foods = [...this.foods, ...food];
      this.cd.markForCheck(); // marks path
   });
}

markForCheck به Angular اعلام می‌کند که این مسیر ویژه را در بررسی بعدی سیستم ردیابی تغییرات لحاظ کن.

‫۶ سال و ۱۰ ماه قبل، جمعه ۱۰ آذر ۱۳۹۶، ساعت ۲۲:۵۰

علی یگانه مقدم

مطالب

ساختار داده‌های خطی Linear Data Structure قسمت دوم

در قسمت قبلی به مقدمات و ساخت لیست‌های ایستا و پویا به صورت دستی پرداختیم و در این قسمت (مبحث پایانی) لیست‌های آماده در دات نت را مورد بررسی قرار می‌دهیم.

کلاس ArrayList

این کلاس همان پیاده سازی لیست‌های ایستایی را دارد که در مطلب پیشین در مورد آن صحبت کردیم و نحوه کدنویسی آن نیز بیان شد و امکاناتی بیشتر از آنچه که در جدول مطلب پیشین گفته بودیم در دسترس ما قرار می‌دهد. از این کلاس با اسم untyped dynamically-extendable array به معنی آرایه پویا قابل توسعه بدون نوع هم اسم می‌برند چرا که به هیچ نوع داده‌ای مقید نیست و می‌توانید یکبار به آن رشته بدهید، یکبار عدد صحیح، یکبار اعشاری و یکبار زمان و تاریخ، کد زیر به خوبی نشان دهنده‌ی این موضوع است و نحوه استفاده‌ی از این آرایه‌ها را نشان می‌دهد.

using System;
using System.Collections;
 
class ProgrArrayListExample
{
    static void Main()
    {
        ArrayList list = new ArrayList();
        list.Add("Hello");
        list.Add(5);
        list.Add(3.14159);
        list.Add(DateTime.Now);
 
        for (int i = 0; i < list.Count; i++)
        {
            object value = list[i];
            Console.WriteLine("Index={0}; Value={1}", i, value);
        }
    }
}

نتیجه کد بالا:

Index=0; Value=Hello
Index=1; Value=5
Index=2; Value=3.14159
Index=3; Value=29.02.2015 23:17:01

البته برای خواندن و قرار دادن متغیرها از آنجا که فقط نوع Object را برمی‌گرداند، باید یک تبدیل هم انجام داد یا اینکه از کلمه‌ی کلیدی dynamic استفاده کنید:

ArrayList list = new ArrayList();
list.Add(2);
list.Add(3.5f);
list.Add(25u);
list.Add(" ریال");
dynamic sum = 0;
for (int i = 0; i < list.Count; i++)
{
    dynamic value = list[i];
    sum = sum + value;
}
Console.WriteLine("Sum = " + sum);
// Output: Sum = 30.5ریال

مجموعه‌های جنریک Generic Collections

مشکل ما در حین کار با کلاس arrayList و همه کلاس‌های مشتق شده از system.collection.IList این است که نوع داده‌ی ما تبدیل به Object می‌شود و موقعی‌که آن را به ما بر می‌گرداند باید آن را به صورت دستی تبدیل کرده یا از کلمه‌ی کلیدی dynamic استفاده کنیم. در نتیجه در یک شرایط خاص، هیچ تضمینی برای ما وجود نخواهد داشت که بتوانیم کنترلی بر روی نوع داده‌های خود داشته باشیم و به علاوه عمل تبدیل یا casting هم یک عمل زمان بر هست.

برای حل این مشکل، از جنریک‌ها استفاده می‌کنیم. جنریک‌ها می‌توانند با هر نوع داده‌ای کار کنند. در حین تعریف یک کلاس جنریک نوع آن را مشخص می‌کنیم و مقادیری که از آن به بعد خواهد پذیرفت، از نوعی هستند که ابتدا تعریف کرده‌ایم.

یک ساختار جنریک به صورت زیر تعریف می‌شود:

GenericType<T> instance = new GenericType<T>();

نام کلاس و به جای T نوع داده از قبیل int,bool,string را می‌نویسیم. مثال‌های زیر را ببینید:

List<int> intList = new List<int>();
List<bool> boolList = new List<bool>();
List<double> realNumbersList = new List<double>();

کلاس جنریک <List<T

این کلاس مشابه همان کلاس ArrayList است و فقط به صورت جنریک پیاده سازی شده است.

List<int> intList = new List<int>();

تعریف بالا سبب ایجاد ArrayList ـی می‌باشد که تنها مقادیر int را دریافت می‌کند و دیگر نوع Object ـی در کار نیست. یک آرایه از نوع int ایجاد می‌کند و مقدار خانه‌های پیش فرضی را نیز در ابتدا، برای آن در نظر می‌گیرد و با افزودن هر مقدار جدید می‌بیند که آیا خانه‌ی خالی وجود دارد یا خیر. اگر وجود داشته باشد مقدار جدید، به خانه‌ی بعدی آخرین خانه‌ی پر شده انتقال می‌یابد و اگر هم نباشد، مقدار خانه از آن چه هست 2 برابر می‌شود. درست است عملیات resizing یا افزایش طول آرایه عملی زمان بر محسوب میشود ولی همیشه این اتفاق نمی‌افتد و با زیاد شدن مقادیر خانه‌ها این عمل کمتر هم می‌شود. هر چند با زیاد شدن خانه‌ها حافظه مصرفی ممکن است به خاطر زیاد شدن خانه‌های خالی بدتر هم بشود. فرض کنید بار اول خانه‌ها 16 تایی باشند که بعد می‌شوند 32 تایی و بعدا 64 تایی. حالا فرض کنید به خاطر یک عنصر، خانه‌ها یا ظرفیت بشود 128 تایی در حالی که طول آرایه (خانه‌های پر شده) 65 تاست و حال این وضعیت را برای موارد بزرگتر پیش بینی کنید. در این نوع داده اگر منظور زمان باشد نتجه خوبی را در بر دارد ولی اگر مراعات حافظه را هم در نظر بگیرید و داده‌ها زیاد باشند، باید تا حدامکان به روش‌های دیگر هم فکر کنید.

چه موقع از <List<T استفاده کنیم؟

استفاده از این روش مزایا و معایبی دارد که باید در توضیحات بالا متوجه شده باشید ولی به طور خلاصه:

استفاده از index برای دسترسی به یک مقدار، صرف نظر از اینکه چه میزان داده‌ای در آن وجود دارد، بسیار سریع انجام میگیرد.
جست و جوی یک عنصر بر اساس مقدار: جست و جو خطی است در نتیجه اگر مقدار مورد نظر در آخرین خانه‌ها باشد بدترین وضعیت ممکن رخ می‌دهد و بسیار کند عمل می‌کند. داده هر چی کمتر بهتر و هر چه بیشتر بدتر. البته اگر بخواهید مجموعه‌ای از مقدارهای برابر را برگردانید هم در بدترین وضعیت ممکن خواهد بود.
حذف و درج (منظور insert) المان‌ها به خصوص موقعی که انتهای آرایه نباشید، شیفت پیدا کردن در آرایه عملی کاملا کند و زمانبر است.
موقعی که عنصری را بخواهید اضافه کنید اگر ظرفیت آرایه تکمیل شده باشد، نیاز به عمل زمانبر افزایش ظرفیت خواهد بود که البته این عمل به ندرت رخ می‌دهد و عملیات افزودن Add هم هیچ وابستگی به تعداد المان‌ها ندارد و عملی سریع است.

با توجه به موارد خلاصه شده بالا، موقعی از لیست اضافه می‌کنیم که عملیات درج و حذف زیادی نداریم و بیشتر برای افزودن مقدار به انتها و دسترسی به المان‌ها بر اساس اندیس باشد.

<LinkedList<T

یک کلاس از پیش آماده در دات نت که لیست‌های پیوندی دو طرفه را پیاده سازی می‌کند. هر المان یا گره یک متغیر جهت ذخیره مقدار دارد و یک اشاره گر به گره قبل و بعد.

چه موقع باید از این ساختار استفاده کنیم؟

از مزایا و معایب آن :

افزودن به انتهای لیست به خاطر این که همیشه گره آخر در tail وجود دارد بسیار سریع است.
عملیات درج insert در هر موقعیتی که باشد اگر یک اشاره گر به آن محل باشد یک عملیات سریع است یا اینکه درج در ابتدا یاانتهای لیست باشد.
جست و جوی یک مقدار چه بر اساس اندیس باشد و چه مقدار، کار جست و جو کند خواهد بود. چرا که باید تمامی المان‌ها از اول به آخر اسکن بشن.
عملیات حذف هم به خاطر اینکه یک عمل جست و جو در ابتدای خود دارد، یک عمل کند است.

استفاده از این کلاس موقعی خوب است که عملیات‌های درج و حذف ما در یکی از دو طرف لیست باشد یا اشاره‌گری به گره مورد نظر وجود داشته باشد. از لحاظ مصرف حافظه به خاطر داشتن فیلدهای اشاره‌گر به جز مقدار، زیاد‌تر از نوع List می‌باشد. در صورتی که دسترسی سریع به داده‌ها برایتان مهم باشد استفاده از List باز هم به صرفه‌تر است.

پشته Stack

یک سری مکعب را تصور کنید که روی هم قرار گرفته اند و برای اینکه به یکی از مکعب‌های پایینی بخواهید دسترسی داشته باشید باید تعدادی از مکعب‌ها را از بالا بردارید تا به آن برسید. یعنی بر خلاف موقعی که آن‌ها روی هم می‌گذاشتید و آخرین مکعب روی همه قرار گرفته است. حالا همان مکعب‌ها به صورت مخالف و معکوس باید برداشته شوند.

یک مثال واقعی‌تر و ملموس‌تر، یک کمد لباس را تصور کنید که مجبورید برای آن که به لباس خاصی برسید، باید آخرین لباس‌هایی را که در داخل کمد قرار داده‌اید را اول از همه از کمد در بیاورید تا به آن لباس برسید.

در واقع پشته چنین ساختاری را پیاده می‌کند که اولین عنصری که از پشته بیرون می‌آید، آخرین عنصری است که از آن درج شده است و به آن LIFO گویند که مخفف عبارت Last Input First Output آخرین ورودی اولین خروجی است. این ساختار از قدیمی‌ترین ساختارهای موجود است. حتی این ساختار در سیستم‌های داخل دات نت CLR هم به عنوان نگهدارنده متغیرها و پارامتر متدها استفاده می‌شود که به آن Program Execution Stack می‌گویند.

پشته سه عملیات اصلی را پیاده سازی می‌کند: Push جهت قرار دادن مقدار جدید در پشته، POP جهت بیرون کشیدن مقداری که آخرین بار در پشته اضافه شده و Peek جهت برگرداندن آخرین مقدار اضافه شده به پشته ولی آن مقدار از پشته حذف نمی‌شود.

این ساختار میتواند پیاده سازی‌های متفاوتی را داشته باشد ولی دو نوع اصلی که ما بررسی می‌کنیم، ایستا و پویا بودن آن است. ایستا بر اساس آرایه است و پویا بر اساس لیست‌های پیوندی. شکل زیر پشته‌ای را به صورت استفاده از پیاده‌سازی ایستا با آرایه‌ها نشان می‌دهد و کلمه Top به بالای پشته یعنی آخرین عنصر اضافه شده اشاره می‌کند.

استفاده از لیست پیوندی برای پیاده سازی پشته:

لیست پیوندی لازم نیست دو طرفه باشد و یک طرف برای کار با پشته مناسب است و دیگر لازم نیست که به انتهای لیست پیوندی عمل درج انجام شود؛ بلکه مقدار جدید به ابتدای آن اضافه شده و برای حذف گره هم اولین گره باید حذف شود و گره دوم به عنوان head شناخته می‌شود. همچنین لیست پیوندی نیازی به افزایش ظرفیت مانند آرایه‌ها ندارد.

ساختار پشته در دات نت توسط کلاس Stack از قبل آماده است:

Stack<string> stack = new Stack<string>();
stack.Push("A");
stack.Push("B");
stack.Push("C");
 while (stack.Count > 0)
    {
        string letter= stack.Pop();
        Console.WriteLine(letter);
    }
//خروجی
//C
//B
//A

صف Queue

ساختار صف هم از قدیمی‌ترین ساختارهاست و مثال آن در همه جا و در همه اطراف ما دیده می‌شود؛ مثل صف نانوایی، صف چاپ پرینتر، دسترسی به منابع مشترک توسط سیستمها. در این ساختار ما عنصر جدید را به انتهای صف اضافه می‌کنیم و برای دریافت مقدار، عنصر را از ابتدا حذف می‌کنیم. به این ساختار FIFO مخفف First Input First Output به معنی اولین ورودی و اولین خروجی هم می‌گویند.

ساختار ایستا که توسط آرایه‌ها پیاده سازی شده است:

ابتدای آرایه مکانی است که عنصر از آنجا برداشته می‌شود و Head به آن اشاره می‌کند و tail هم به انتهای آرایه که جهت درج عنصر جدید مفید است. با برداشتن هر خانه‌ای که head به آن اشاره می‌کند، head یک خانه به سمت جلو حرکت می‌کند و زمانی که Head از tail بیشتر شود، یعنی اینکه دیگر عنصری یا المانی در صف وجود ندارد و head و Tail به ابتدای صف حرکت می‌کنند. در این حالت موقعی که المان جدیدی قصد اضافه شدن داشته باشد، افزودن، مجددا از اول صف آغاز می‌شود و به این صف‌ها، صف حلقوی می‌گویند.

عملیات اصلی صف دو مورد هستند enqueue که المان جدید را در انتهای صف قرار می‌دهد و dequeue اولین المان صف را بیرون می‌کشد.

پیاده سازی صف به صورت پویا با لیست‌های پیوندی

برای پیاده سازی صف، لیست‌های پیوندی یک طرفه کافی هستند:

در این حالت عنصر جدید مثل سابق به انتهای لیست اضافه می‌شود و برای حذف هم که از اول لیست کمک می‌گیریم و با حذف عنصر اول، متغیر Head به عنصر یا المان دوم اشاره خواهد کرد.

کلاس از پیش آمده صف در دات نت <Queue<T است و نحوه‌ی استفاده آن بدین شکل است:

static void Main()
{
    Queue<string> queue = new Queue<string>();
    queue.Enqueue("Message One");
    queue.Enqueue("Message Two");
    queue.Enqueue("Message Three");
    queue.Enqueue("Message Four");
 
    while (queue.Count > 0)
    {
        string msg = queue.Dequeue();
        Console.WriteLine(msg);
    }
}
//خروجی
//Message One
//Message Two
//Message Thre
//Message Four

‫۹ سال و ۸ ماه قبل، جمعه ۱ اسفند ۱۳۹۳، ساعت ۰۵:۴۰

وحید نصیری

بازخوردهای دوره