Stek
Oshxonadagi likopchalar turadigan quti, brovserning orqaga(«nazad») tugmasi, ixtiyoriy matn muxarriridagi bekor qilish(«CTRL-Z») amali, bularning barchasi Stek ma’lumotlar strukturasiga misoldir. «LIFO» y’ani oxirgi kegan birinchi ketadi qoidasi asosiga qurilgan bo’lib kompyuter olamida eng ko’p ishlatiladigan ma’lmumotlar strukturasidan biri. Demak, bugun Stek(Stack) ma’lumotlar strukturasini o’rganamiz.
Quyidagi rasmda stekning sodda ifodasi berilgan.
Rasmda ko’rinib turganidek, stek bu obyektlarning ro’yxati bo’lib, eng oxirgi qo’shilgan obyekt xar doim birinchi bo’lib qaytadi. Masalan, ushbu rasmdagi stekka yangi qiymat qo’shilsa A bitta pastga tushadi, yangi qo’shilgan obyekt «top» o’rinni egallaydi. Keyingi murojaat vaqtida aynan yangi qo’shilgan obyekt qaytariladi.
Ushbu ro’yxatda Stekning tarkibida bo’lgan operatsiyalar berilgan.
Push(value)stekka yangi qiymat qo’shadi. Aytib o’tilganidek, yangi qaiymat «top» o’ringa borib tushadi.Pop()eng oxirgi qo’shilgan obyekt qaytariladi va stekdan o’chiriladi.Peek()eng oxirgi qo’shilgan qaytariladi leki stekdan o’chirilmaydi.IsEmpty()stek bo’shmi? degan savolga javobgar metod.Size()stekdagi obyektlar sonini qaytaradi.
Stekning implementasiyasi ikki xil usulda bajarilishi mumkin. Zanjir(Linked) va Massiv. Ularning farqiga to’xtalib o’tamiz, lekin undan oldin IStack interfacega diqqat qilamiz. Yuqorida berilgan amallarni kelajakda ushbu interfacedan meros olinadigan classlar uchun qoidaga aylantiramiz.
//Stek uchun iterface, T tipidagi obeyektlar bilan ishlaydi.
public interface IStack
{
///
/// Stack element qo'shish.
///
/// Qo''shilishi lozim bo'lgan element.
void Push(T value);
///
/// Stackning boshidagi element o'chirib qiymatini qaytaradi.
///
T Pop();
///
/// Stackning boshidagi element qaytaradi, lekin o'chirmaydi.
///
T Peek();
///
/// Stack bo'shmi?
///
bool IsEmpty();
///
/// Stackdagi elementlar soni.
///
int Size();
}
1. Zanjir yoki Linked Stek. Esingizda bo’sla LinkedList haqida gaplashganimizda Node ma’lumotlar strukturasi haqida so’z yuritganmiz. Stekning bu ko’rinishini asosini ham ushmu MS tashkil qiladi. Stekdagi barcha element o’zidan keyingi elementga bo’glangan bo’ladi va ushbu ketma-ketlik yordamida stekdagi «top» elementni aniqlab olamiz. Ushbu usulda yaratilga Stekning vaqt murakkabligi quyidagi jadvalda berilgan.
Barcha amallarni asosini o’zlashtirish amali tashkil qilgani sababi barcha metodlar O(1) vaqtda bajariladi.
// Linkedga asoslangan Stack
public class LStack : IStack
///
/// Stackning tashkil etuvchisi.
///
protected class Node
{
public Node(T value, Node next)
{
Value = value;
Next = next;
}
public T Value { get; set; }
public Node Next { get; set; }
}
// Stackdagi elementlarning soni.
private int _counter;
//Stackning boshi.
private Node _top;
///
/// Stack element qo'shish.
///
/// Qo'shilishi lozim bo'lgan element.
public void Push(T value)
{
Node node = new Node(value, _top);
_top = node;
_counter++;
}
///
/// Stackning boshidagi element o'chirib qiymatini qaytaradi.
///
public T Pop()
{
if (_counter != 0)
{
Node node = _top;
_top = _top.Next;
_counter--;
return node.Value;
}
return default(T);
}
///
/// Stackning boshidagi element qaytaradi, lekin o'chirmaydi.
///
public T Peek()
{
if (_counter != 0)
{
return _top.Value;
}
return default(T);
}
///
/// Stack bo'shmi?
///
public bool IsEmpty()
{
return _counter == 0;
}
///
/// Stackdagi elementlar soni.
///
public int Size()
{
return _counter;
}
}
private static void Main(string[] args)
{
LStack stack = new LStack();
stack.Push("A");
stack.Push("B");
stack.Push("C");
stack.Push("D");
stack.Push("E");
stack.Push("F");
//Stekning hajmi
Console.WriteLine(stack.Size());
//Stekning barcha elementlarini ekranga chiqarish
while (!stack.IsEmpty())
{
Console.WriteLine(stack.Pop());
}
}
2. Massivga asoslangan Stek. Massivning qulayliklaridan biri bu indeks orqali massivda joylashgan elementni O(1) vaqtda qaytara olishdir. Lekin massivdagi elementlar soni ko’payib ketsa qimmatbaho amal — hajmni kengaytirish lozim bo’ladi. O’z hajmini o’zi o’zgartira oladigan massiv dinamik massiv deyiladi. .Net dasturlash tili oilasidagi List
Nazariyaga ko’ra Push(T value) O(n) bu eng yomon holatdur, lekin Resize() ning chaqirilish ehtimolligi har chaqirilgandan so’ng pasayib boradi. Natijada, yuqoridagi metodni O(1) vaqt murakkablikka ega deb qabul qilishimiz mumkin. Buning sababi esa, massivning yangi o’lchami oldingisidan ikki baravar kattaligidadur. Ya’ni aytayik massivni yaratdik, uning boshlang’ish o’lchami 50 edi. Massivning kengayib borish tartibi esa; 50,100,200,400,800,160,320… Ahamiyat bergan bo’lsangiz bir necha marta chaqirilgandan so’ng yetarlicha o’lchamdagi massivga ega bo’lamiz. Bu jihatni amortizatsiya analiz usuli bilan aniqlashimiz mumkin. Keyingi maqolalarimizda analizning ushbu usulini e’tioborga olishga harakat qilamiz.
//Massivga asoslangan Stack
public class AStack : IStack
{
//Elementlarni saqlash uchun
private T[] _array;
// Stackdagi elementlarning soni.
private int _counter;
public AStack()
{
_array = new T[50];
_counter = 0;
}
public AStack(int maxSize)
{
_array = new T[maxSize];
_counter = 0;
}
///
/// Stack element qo'shish.
///
/// Qo'shilishi lozim bo'lgan element.
public void Push(T value)
{
_counter++;
if (_counter >= _array.Length)
Resize();
_array[_counter] = value;
}
///
/// Stackning boshidagi element o'chirib qiymatini qaytaradi.
///
public T Pop()
{
if (_counter == 0)
return default(T);
return _array[_counter--];
}
///
/// Stackning boshidagi element qaytaradi, lekin o'chirmaydi.
///
public T Peek()
{
if (_counter == 0)
return default(T);
return _array[_counter];
}
///
/// Stack bo'shmi?
///
public bool IsEmpty()
{
return _counter == 0;
}
///
/// Stackdagi elementlar soni.
///
public int Size()
{
return _counter;
}
///
/// Stackdagi hajmini o'zgartiradi.
///
private void Resize()
{
T[] tempArray = new T[2 * _array.Length];
for (int i = 0; i LStack vs AStack. Xo'p, ikkala usulda ham amallar O(1) murakkablikka ega bo'lsa, qaysi birida foydalanishimiz lozim? Yaxshi savol, so'raganizdan hursandman. AStack ning kamchiligi, egalllanadigan hotiraning isrof bo'lishi, ya'ni boshlang'ich vaziyatda ma'lum bir o'lchamda massiv yaratishi va ushbu massivning hamma xonasi ham ishlatilmay qolishligidadir.LStack esa faqat kerak bo'lgan taqdirdagina hotiradan joy egallaydi. AStack ning ham qulayliklari bor masalan, massivda "locality" degan hususiyat bo'lib, missivdagi elementlarning bir-biriga yaqinroq joylashgani hisobiga tezroq ishlashi mumkin.
Manba:
Algoritm
Stek