|
Ma’ruza Stek
|
| bet | 4/4 | | Sana | 16.02.2024 | | Hajmi | 261,72 Kb. | | #157914 |
Bog'liq Ma\'ruza 5. SteklarSamaradorligi
n - stekdagi elementlar soni bo'lsin. Ushbu o'lchamdagi stek amallari uchun xotira va vaqt bahosi quyidagicha:
Xotira sarfi(n ta kiritish amali uchun) − O(n);
Stekkar element qo’shish Push() amali uchun vaqt sarfi − O(1);
Stekda elementni olib tashlash Pop() amali uchun vaqt sarfi − O(1);
Peek() orqali elementni olish uchun vaqt sarfi − O(1);
IsEmpty() uchun vaqt sarfi − O(1);
n ta elementni qo’shish uchun umumiy vaqt sarfi - O(n);
Stekdagi elementlar ro‘yxatini olish Print() amali uchun vaqt sarfi − O(n).
Ajratilgan xotiraning ikki barobarga oshirishi xotiraning to'lib ketishiga olib kelishi mumkin.
.
Bir bog’lamli ro’yxat asosida stekni amalga oshirish
Bog'langan ro'yxatlardan foydalanganda, Push qo’shish amali elementni ro'yxatning boshiga kiritish sifatida amalga oshiriladi. Pop amali boshlang'ich tugunni olib tashlash orqali amalga oshiriladi.
Ro'yxat orqali stekni amalga oshirish dasturi quyida keltirilgan:
using System;
using System.Collections.Generic;
using System.Text;
namespace ListStack
{
public class Node
{
public Node(T data)
{
Data = data;
}
public T Data { get; set; }
public Node Next { get; set; }
}
public class LStack
{
Node head;
int count;
public bool IsEmpty
{
get { return count == 0; }
}
public int Count
{
get { return count; }
}
public void Push(T item)
{
// Stekni kattalashtiramiz
Node node = new Node(item);
node.Next = head; // stek uchini yangi elementga qayta o’rnatish
head = node;
count++;
}
public T Pop()
{
// Stek bo’sh bo’lsa istisno xolatini yuzaga keltirish
if (IsEmpty)
throw new InvalidOperationException("Stek bo’sh");
Node temp = head;
head = head.Next; // stek uchini keyingi elementga qayta o’rnatish
count--;
return temp.Data;
}
public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException("Stek bo’sh");
return head.Data;
}
public void Clear()
{
head = null;
count = 0;
}
public bool Contains(T data)
{
Node current = head;
while (current != null)
{
if (current.Data.Equals(data))
return true;
current = current.Next;
}
return false;
}
public void Print()
{
Node current = head;
while (current != null)
{
Console.WriteLine(current.Data);
current = current.Next;
}
}
}
}
Ro'yxat asosidagi stekdan foydalanishga misol:
using System;
namespace ListStack
{
class Program
{
static void Main(string[] args)
{
try
{
LStack stack = new LStack();
stack.Push("Petr");
stack.Push("Alice");
stack.Push("Rustam");
stack.Push("Sarvar");
stack.Print();
Console.WriteLine();
string header = stack.Peek();
Console.WriteLine($"Stek uchi: {header}");
Console.WriteLine();
header = stack.Pop();
stack.Print();
}
catch (InvalidOperationException ex)
{
Console.WriteLine(ex.Message);
}
Console.Read();
}
}
}
Samaradorligi
n - stekdagi elementlar soni bo'lsin. Ushbu o'lchamdagi stek amallari uchun xotira va vaqt bahosi quyidagicha:
Xotira sarfi(n ta kiritish amali uchun) − O(n);
Stekkar element qo’shish Push() amali uchun vaqt sarfi − O(1);
Stekda elementni olib tashlash Pop() amali uchun vaqt sarfi − O(1);
Peek() orqali elementni olish uchun vaqt sarfi − O(1);
IsEmpty() uchun vaqt sarfi − O(1);
n ta elementni qo’shish uchun umumiy vaqt sarfi - O(n);
Stekdagi elementlar ro‘yxatini olish Print() amali uchun vaqt sarfi − O(n).
Stek BATni massiv va bog'langan ro'yxat asosida amalga oshirishni solishtirish
Massiv asosida amalga oshirish
• amallar doimiy vaqtni oladi O(1);
• Vaqti o’tishi bilan qimmat ikkilantirish amali.
Bog'langan ro'yxat asosida amalga oshirish
• Chiroyli tarzda o'sib boradi va qisqaradi;
• Har bir amal doimiy O(1) vaqtni oladi.
• Har bir amal havolalar bilan ishlash uchun qo'shimcha joy va vaqt talab qiladi.
|
| |
