Stek qo’llaniladigan masalalar

|
Stek qo’llaniladigan masalalar
|
bet | 2/4 | Sana | 16.02.2024 | Hajmi | 261,72 Kb. | | #157914 |
Bog'liq Ma\'ruza 5. SteklarStek qo’llaniladigan masalalar.
Quyida steklar muhim rol o'ynaydigan ba'zi masalalar mavjud.
To'g'ridan-to'g'ri stekdan foydalanadigan masalalar:
• Belgilarni muvozanatlash (masalan, qavslar);
• Infikslarni postfikslarga aylantirish;
• Postfiks ifodasini baholash;
• Funksiya chaqiruvlarini amalga oshirish (jumladan, rekursiya);
• Bo'shliqlarni topish (birja bozorlarida bo'shliqlarni qidirish);
• Web-brauzerdagi sahifalarga tashriflar tarixi (qaytish tugmalari);
• Matn muharriridagi bajarilgan amallar ketma-ketligini bekor qilish (Ctrl Z);
• HTML va XMLdagi teglarning qo’llanilishi.
Stekdan bilvosita foydalaniladigan masalalar:
• Boshqa algoritmlar uchun yordamchi berilganlar strukturasi (masalan: daraxt bo’ylab oʻtish algoritmlari);
• Boshqa berilganlar tuzilmalari komponenti (Misol: navbatlarni modellashtirish).
Stekni amalga oshirish
Stek BATni amalga oshirishning ko'plab usullari mavjud. Quyida eng ko'p qo'llaniladigan usullar keltirilgan.
• Statik massiv asosida oddiy amalga oshirish;
• Dinamik massiv asosida amalga oshirish;
• Bog'langan ro'yxat asosida amalga oshirish.
Statik massiv asosida amalga oshirish
Stek BATni amalga oshirishning ushbu turida oddiy statik massivdan foydalaniladi. Elementlar massivga chapdan o'ngga ketma-ket qo'shiladi va yuqori element indeksiga ishora qiluvchi o'zgaruvchidan foydalaniladi.
Stek elementlari saqlanayotgan massiv to'lishi mumkin va keyingi Push qo’shish amali stek to'lib ketishini anglatuvchi istisnoni yuzaga keltiradi qiladi.
Xuddi shunday, agar biz bo'sh stekdan elementni Pop olib tashlashga harakat qilsak, u stek bo'shaganligini bildiruvchi istisnoga olib keladi.
Quyida Stek BATni statik massiv orqali amalga oshirish misoli keltirilgan:
using System;
using System.Collections.Generic;
using System.Text;
namespace ArrayStack
{
public class ArrStack
{
private T[] items; // stek elementlari
private int count; // elementlar soni
const int n = 10; // kelishuv bo’yicha massivdagi elementlar soni
public ArrStack(int length = n)
{
items = new T[length];
}
// stekni bo’shlikka tekshirish
public bool IsEmpty
{
get { return count == 0; }
}
// stek o’lchami
public int Count
{
get { return count; }
}
// Stekka element qo’shish
public void Push(T item)
{
// agar stek to’la bo’lsa istisno xolatini yuzaga keltirish
if (count == items.Length)
throw new InvalidOperationException("Stek to’lgan");
items[count++] = item;
}
// Stekdan elementni olish
public T Pop()
{
// Agar stek bo’sh bo’lsa istisno xolatini yuzaga keltirish
if (IsEmpty)
throw new InvalidOperationException("Stek bo’sh");
T item = items[--count];
items[count] = default(T); //
return item;
}
// Stek oxiridan element qaytarish
public T Peek()
{
// Agar stek bo’sh bo’lsa istisno xolatini yuzaga keltirish
if (IsEmpty)
throw new InvalidOperationException("Stek bo’sh");
return items[count - 1];
}
// Stek elementlarini konsol ekraniga chiqarish
public void Print()
{
for (int i=0;i{
Console.WriteLine(items[i]);
}
}
}
}
Statik siklik massiv ko’rinishida stekdan foydalanishga doir misol:
using System;
namespace ArrayStack
{
class Program
{
static void Main(string[] args)
{
try
{
ArrStack stack = new ArrStack(8);
// 4 ta element qo’shamiz
stack.Push("Anvar");
stack.Push("Rustam");
stack.Push("Diana");
stack.Push("Sattor");
Console.WriteLine("Stekdagi elementlar soni:{0}",stack.Count);
Console.WriteLine("Stekdagi elementlar ro’yxati");
stack.Print();
Console.WriteLine("Stekdan olib tashlash");
// Stekdan 1 ta elementni olib tashlaymiz
var head = stack.Pop();
Console.WriteLine(head); // Sattor
head = stack.Pop();
Console.WriteLine(head);
head = stack.Pop();
Console.WriteLine(head);
// Stekdan element olib tashlamasdan oxiridan olish
head = stack.Peek();
Console.WriteLine(head); // Diana
Console.WriteLine("Stekdagi elementlar ro’yxati");
stack.Print();
}
catch (InvalidOperationException ex)
{
Console.WriteLine(ex.Message);
}
Console.ReadKey();
}
}
}
|
| |