|
Ma’lumotlar tuzilmasi va algoritmlar” fanidan 2-mustaqil ishi tuzuvchi: Qo’ziboyev Xasanboy
|
| bet | 4/4 | | Sana | 16.12.2023 | | Hajmi | 356,54 Kb. | | #120363 |
Bog'liq Xasanboy MT MaruzaNatija:
4-MASALA
4-masala. Stek tuzilmasini bog‘langan ro‘yxat orqali qayta ishlashga misol:
Ushbu tasvirda berilgan amallarni bajarish uchun bir bog'langan ro'yxat berilgan deb hisoblang. Ushbu bog'langan ro'yxat yordamida stek tuzilmasini hosil qilish talab etilgan. Buning uchun quyidagi jadvalda berilgan dastur kodiga
to’ldirishlar kiritish kerak bo’ladi. Ya’ni, stek klassidagi push() va pop() funksiyalari uchun kod yozing.
Masalan:
Masalaning qo‘yilishi:
Push() va pop() ikkita metodni ishlab chiqing. Push() metodi bitta argumentni oladi, ya'ni stekga qo’shiladigan "x" butun son va pop() metodi argumentsiz bo’lib,
stekning top elementi - butun sonni qaytaradi. Agar stek bo'sh bo'lsa, pop() metodi -1 ni qaytaradi.
Kutilayotgan vaqt murakkabligi: push() va pop() uchun O(1).
Kutilayotgan yordamchi xotira: push() va pop() uchun O(1).
Cheklovlar:
1 ≤ Q ≤ 100
1 ≤ x ≤ 100
Masalaning javobi:
class StackNode:
def __init__(self, data):
self.data = data
self.next = None
class MyStack:
def __init__(self):
self.top = None
#mening kodim
def push(self, data):
qosh_elem = StackNode(data)
qosh_elem.next = self.top
self.top = qosh_elem
#mening kodim
def pop(self):
if self.isEmpty():
return -1
ochgan_elem = self.top.data
self.top = self.top.next
return ochgan_elem
def isEmpty(self):
return self.top is None
# Asosiy dastur
t = int(input("So'rovnoma soni: "))
for _ in range(t):
s = MyStack()
q = int(input("So'rovlar soni: "))
q1 = list(map(int, input("So'rovlarni kiriting: ").split()))
i = 0
while i < len(q1):
if q1[i] == 1:
s.push(q1[i + 1])
i += 2
elif q1[i] == 2:
popped_item = s.pop()
if popped_item != -1:
print(popped_item, end=" ")
else:
print(-1)
i += 1
elif s.isEmpty():
print(-1)
print()
|
| |
