სტეკი (LIFO) და გამოსახულების გამოთვლა

პროგრამის ყოველი ფუნქციის გამოძახება სტეკში თავსდება, ყოველი Ctrl+Z კი სტეკიდან იღებს ერთ ელემენტს. იგივე პატარა სტრუქტურა აძლევს კომპილატორს კოდის ანალიზის, კალკულატორს კი ოპერაციების პრიორიტეტის დაცვის საშუალებას.

★ ლექცია: STL_stack · ზაზა გამეზარდაშვილი▶ ვიდეო დამწყები⏱ 15 წთ

←ეყრდნობა

0რეკურსია და გამოძახებათა სტეკიგამოძახებათა სტეკი სტეკია: რეკურსია შენიღბული LIFO-ა.1მასივები და დინამიური მასივებისტეკი არის დინამიური მასივი, რომელიც მხოლოდ ბოლოში ამატებს და ბოლოდან იღებს.

გზას უხსნის→

3მონოტონური სტეკიმონოტონური სტეკი ჩვეულებრივი სტეკია, რომელიც ამოაგდებს ყველაფერს, რაც პასუხი ვეღარ იქნება.3რიგი (FIFO) და დეკირიგი სტეკის ტყუპია, რომელიც მეორე ბოლოდან იღებს: FIFO და არა LIFO.4უკუსვლა და მოკვეთა: N ლაზიერიდაბრუნებისას არჩევანის გაუქმება არის მისი ამოღება უკვე გაკეთებული არჩევანების სტეკიდან.6სიღრმეში ძებნა (DFS)BFS-ის რიგი სტეკით შეცვალე და ტალღა ჩაყვინთვად იქცევა.

1ისწავლე 2უყურე 3ითამაშე 4შეამოწმე 5ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ბოლოს მოვიდა, პირველი წავიდა

სტეკი მონაცემთა აბსტრაქტული ტიპია: ელემენტთა სია, რომლის ელემენტებიდან წვდომა მხოლოდ ერთზეა შესაძლებელი, სათავეში მოთავსებულზე. ახალ ელემენტს თავზე ვდებთ და თავიდანვე ვიღებთ, ამიტომ მოქმედების პრინციპია „ბოლოს მოვიდა, პირველი წავიდა“ (LIFO). წარმოიდგინე თეფშების დასტა.

სტეკში მოთავსებული ელემენტების ინდექსაცია არ ხდება: st[2] არ არსებობს. სწორედ ეს შეზღუდვაა მთავარი. რადგან მხოლოდ სათავეს ვეხებით, ყოველი ოპერაცია O(1)-ია, სტეკზე აგებული კოდი კი ადვილად გასაგებია.

სტეკი ფართოდ გამოიყენება პროგრამირების ყველა ენაში: მისი დახმარებით კომპილატორი ახორციელებს სინტაქსურ ანალიზს, ხდება არითმეტიკული გამოსახულების გამოთვლა, რეკურსია კი გამოძახებების სტეკზე მუშაობს.

02STL-ის სტეკი და მისი ხუთი ფუნქცია

C++-ში სტეკს საკუთარი ბიბლიოთეკა აქვს, #include <stack>, მისი გამოცხადება კი ჩვეულებრივი ცვლადივით შეიძლება: stack<int> st1;, stack<string> st2;, stack<char> st3;, stack<pair<int,int>> st4;, stack<double> st5;.

push(x): ელემენტის ჩამატება. ახლად დამატებული ელემენტი ყოველთვის ხდება სათავე, ძველი სათავე კი მისი მომდევნო.
pop(): სათავეში მყოფი ელემენტის წაშლა; მისი მომდევნო ხდება ახალი სათავე.
top(): მიმართვა სათავეში მყოფ ელემენტზე.
size(): ელემენტთა რაოდენობა.
empty(): ბულის ტიპის ფუნქცია, true ან false.

C++-ის ორი დეტალი: pop() არაფერს აბრუნებს, ამიტომ მნიშვნელობა თუ გჭირდება, ჯერ top() წაიკითხე. ცარიელ სტეკზე top()-ის ან pop()-ის გამოძახება განუსაზღვრელი ქცევაა: ჯერ empty() შეამოწმე.

03ლექციის პროგრამის კვალდაკვალ

ლექციაში ეს პროგრამა ცარიელ stack<int> st-ზე სრულდება: დაბეჭდე empty(), ჩადე 37, 22 და 29, დაბეჭდე size(), pop(), დაბეჭდე top(), pop(), დაბეჭდე empty(), ჩადე 16, დაბეჭდე size().

თვალი ადევნე სათავეს. სამი push-ის შემდეგ სტეკშია 37, 22, 29 და სათავეში 29-ია, ამიტომ size() ბეჭდავს 3-ს. პირველი pop() შლის 29-ს, ბოლოს მოსულს, და top() ბეჭდავს 22-ს. მეორე pop() შლის 22-ს, რჩება მხოლოდ 37, ამიტომ empty() ბეჭდავს false-ს. ბოლოს 16 ეწყობა 37-ის თავზე და size() ბეჭდავს 2-ს.

პროგრამის შესრულების შედეგია true 3 22 false 2. გაუშვი ქვემოთ ვიზუალიზატორში და ყოველი სტრიქონი წინასწარ გამოიცანი.

04ინფიქსური ჩანაწერიდან პოსტფიქსურამდე

(A+B)*(C+D)-E-ს ინფიქსური სახით ვწერთ: ოპერაცია ოპერანდებს შორისაა, ამიტომ ფრჩხილები და პრიორიტეტები გვჭირდება. პოსტფიქსურ ჩანაწერში ოპერაცია ოპერანდების შემდეგ მოდის: A B + C D + * E -. არც ფრჩხილები, არც პრიორიტეტები. არითმეტიკულ ოპერაციებს მივანიჭოთ პრიორიტეტები: ^ მაღალი, * და / საშუალო, + და - დაბალი. ვკითხულობთ მარცხნიდან მარჯვნივ, სტეკში ოპერაციებს ვინახავთ:

ა) იდენტიფიკატორი (ან რიცხვი) პირდაპირ გადაიწერება გამომავალ სტრიქონში;
ბ) თუ სტეკი ცარიელია, ან სტეკის ზედაპირზე მყოფ ოპერაციას ნაკლები პრიორიტეტი აქვს, განსახილველი ოპერაცია თავსდება სტეკში;
გ) წინააღმდეგ შემთხვევაში ოპერაცია გამომავალ სტრიქონში „გამოაძევებს“ მისი ტოლი ან მეტი პრიორიტეტის ყველა ოპერაციას (უახლოეს მარცხენა ფრჩხილამდე) და შემდეგ თავსდება სტეკში;
დ) მარცხენა ფრჩხილი ყოველთვის თავსდება სტეკში;
ე) მარჯვენა ფრჩხილი „გამოაძევებს“ ყველა ოპერაციას უახლოეს მარცხენა ფრჩხილამდე; თავად წყვილი უბრალოდ იშლება.

ბოლოს სტეკში დარჩენილი ოპერაციები გამომავალ სტრიქონში გადადის. (ერთი დაზუსტება, რომელიც სლაიდზე არ არის: ^ ჩვეულებრივ მარჯვნიდან ასოციაციურია, ანუ 2^3^2 ნიშნავს 2^(3^2)-ს. ამიტომ ახლად მოსული ^ მხოლოდ მასზე მკაცრად მაღალი პრიორიტეტის ოპერაციებს გამოაძევებს და სხვა ^-ს არა.)

სლაიდი 8: (A+B)*(C+D)-E-ის 13 სიმბოლო, სტეკი თითოეულის შემდეგ და ის, რაც გამომავალ სტრიქონში გადავიდა.

05პოსტფიქსური ჩანაწერის გამოთვლა

პოსტფიქსური ჩანაწერი, ცხადია, თვითმიზანი არ არის: ასე ჩაწერილი გამოსახულების მნიშვნელობა იოლად გამოითვლება იმავე სტეკით, ოღონდ ახლა მასში რიცხვებს ვინახავთ.

ა) რიცხვი პირდაპირ თავსდება სტეკში;
ბ) ოპერაციის ნიშნის ⊕ შემთხვევაში სტეკის ზედაპირიდან ვიღებთ x-ს, მის ქვემოდან y-ს, ორივეს ვაძევებთ და ვათავსებთ y ⊕ x-ს;
გ) ყველა ოპერაციის შემდეგ სტეკში დარჩენილი რიცხვი გამოსახულების მნიშვნელობაა.

ლექციის მაგალითია ((13+7)-3*4)/2+16, პოსტფიქსურად 13 7 + 3 4 * - 2 / 16 +. სტეკი ასე იცვლება: 13 → 13 7 → 20 → 20 3 → 20 3 4 → 20 12 → 8 → 8 2 → 4 → 4 16 → 20.

ყურადღება მიაქციე რიგს: --სა და /-ზე ეს არის y - x, ქვედა ელემენტს გამოკლებული სათავე. ორივე გავლა ყოველ სიმბოლოს ერთხელ ეხება, ამიტომ მთელი გამოთვლა O(n)-ია. ვიზუალიზატორში საკუთარი გამოსახულება შეიყვანე და ორივე ეტაპს დააკვირდი.

ლექციის C++ კოდიC++

ლექციის მე-5 სლაიდი: მიჰყევი st სტეკზე push და pop ოპერაციებს და ყოველი დაბეჭდილი სტრიქონი ბოლოში მოცემულ შედეგს შეადარე.

#include<bits/stdc++.h>
using namespace std;
stack <int> st;
main(){
    cout<<boolalpha<<st.empty()<<endl;
    st.push(37);
    st.push(22);
    st.push(29);
    cout<<st.size()<<endl;
    st.pop();
    cout<<st.top()<<endl;
    st.pop();
    cout<<boolalpha<<st.empty()<<endl;
    st.push(16);
    cout<<st.size()<<endl;
}
// პროგრამის შესრულების შედეგი:
// true
// 3
// 22
// false
// 2

ფასი ერთი შეხედვით

push / pop / topO(1)

size / emptyO(1)

ინფიქსური → პოსტფიქსურიO(n)

პოსტფიქსურის გამოთვლაO(n)

დაიმახსოვრე

სტეკი წვდომას მხოლოდ სათავის ელემენტზე იძლევა: ბოლოს მოვიდა, პირველი წავიდა, ყოველი ოპერაცია O(1)-ში.
ოპერაციების სტეკითა და პრიორიტეტის წესებით ინფიქსური გამოსახულება პოსტფიქსურად ერთი გავლით გარდაიქმნება.
პოსტფიქსური გამოსახულება რიცხვების სტეკით გამოითვლება: ყოველი ოპერაცია იღებს x-სა და y-ს და ათავსებს y ⊕ x-ს.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: ნაგულისხმევი გაშვება სლაიდ 5-ის პროგრამაა: ყოველი cout სტრიქონი წინასწარ გამოიცანი. შემდეგ შეიყვანე (A+B)*(C+D)-E ან ((13+7)-3*4)/2+16 და ნახე სლაიდები 8 და 9.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

სტეკი st (LIFO: „ბოლოს მოვიდა, პირველი წავიდა“)

(ცარიელია)

გამოტანილი (cout)

ვაცხადებთ ცარიელ სტეკს. წვდომა ყოველთვის მხოლოდ სათავის ელემენტზეა: „ბოლოს მოვიდა, პირველი წავიდა“ (LIFO).

ფსევდოკოდი

 1 stack<int> st; 2 cout << st.empty();  // true 3 st.push(37); 4 st.push(22); 5 st.push(29); 6 cout << st.size();   // 3 7 st.pop(); 8 cout << st.top();    // 22 9 st.pop();10 cout << st.empty();  // false11 st.push(16);12 // your expression: infix → postfix (slide 8)13 for each symbol c of the infix:14   operand → copy it to the output15   "(" → push it16   ")" → pop ops to output until "(", drop both17   op → pop ops with priority ≥ op (for ^ only >), then push op18 pop all remaining ops to the output19 // evaluate the postfix (slide 9)20 for each symbol of the postfix:21   number → st.push(number)22   op ⊕ → x = pop, y = pop, push(y ⊕ x)23 answer = st.top()

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

ცარიელი სტეკი: push 5, push 8, pop, push 3, push 9, pop. რას დააბრუნებს top()?

№2

A-BC-ის გარდაქმნისას მოდის, სტეკში კი - დევს. რა ხდება?

№3

რას უდრის პოსტფიქსური გამოსახულება 8 2 - 3 *?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeValid Parentheses დამწყები↗LeetCodeMin Stack საშუალო↗LeetCodeEvaluate Reverse Polish Notation საშუალო↗LeetCodeBasic Calculator II საშუალო↗