Let’s talk about the Stack data structure

Introduction

DSA တွေထဲမှာ တော်တော်လေးရိုးရှင်းလွယ်ကယ်တဲ့ data structure တစ်ခုပါ။ Stack အကြောင်း အများစုကတော့ သိပြီးဖြစ်မှာပါ။ မေ့နေမှာစိုးလို့ရယ် စာပြန်နွှေးပြီးသားဖြစ်အောင်ရယ် နောက်ဆက်ပြောမယ့် recursion, tree, graph, dp တွေက stack နဲ့ပတ်သက်တာတွေဖြစ်နေတာကြောင့်ရယ် ဒီမှာပြန်နွှေးပေးလိုက်ပါတယ်။

Prerequisites

• Array
• For loop

What is Stack?

Stack ဆိုတာကတော့ last-in-first-out (LIFO) ပေါ့။ နောက်ဆုံးဝင်လာတဲ့ကောင်က ပထမဆုံး priority အနေနဲ့ ပြန်ထွက်သွားတာမျိုးပေါ့။ တစ်နည်းပြောရရင်တော့ နောက်ဆုံး latest item တွေကို ကြည့်ချင်ရင် stack ကိုသုံးသင့်တာပေါ့။ ဥပမာပေးရရင် စားသောက်ဆိုင်တစ်ခုမှာ ပန်းကန်တွေကို ဆေးပြီးတော့ ထပ်ထားတယ်ပေါ့။

သုံးတော့မယ်ဆိုတဲ့အချိန်ကျတော့ ထပ်ထားတဲ့ပန်းကန်တွေထဲက အပေါ်ဆုံးတစ်ချပ် (နောက်ဆုံးဆေးပြီး ထပ်လိုက်တဲ့ပန်းကန်) ကနေ စယူတာပေါ့။ ပန်းကန်အချပ် ၁၀၀ ထပ်ထားရင် ဘယ်သူမှ ဟိုးအောက်ဆုံး ပန်းကန်ကနေ စမယူဘူးလေ နော်။ မတော် အပေါ်ကထပ်ထားတာတွေပါ ကျကွဲနိုင်တာကိုး။ ဒီတော့ အပေါ်ဆုံးထပ်ထားတဲ့အချပ်ကနေ စယူတာပေါ့။

Code အနေနဲ့ ကြည့်မယ်ဆိုရင်

let stack = [1, 2, 3, 4, 5]

ပြန်ထုတ်ကြည့်မယ်ဆိုရင် 5, 4, 3, 2, 1 ဆိုပြီး နောက်ဆုံးကကောင်က ပထမဆုံးထွက်လာတာပေါ့။ ဒီမှာ numeric value ကို example အနေနဲ့ပေးထားပေမယ့် stack ထဲမှာ ဘာမဆိုဖြစ်နိုင်တယ်။ နောက်ပိုင်း usecase တွေကိုပြောတဲ့အချိန်ကျရင် ပိုမြင်လာပါလိမ့်မယ်။

Standard stack operations

Standard stack operations ဆိုတာက stack တစ်ခုမှာ ဘယ်လို functionality တွေပါသင့်သလဲ stack တစ်ခုကို ကျွန်တော်တို့ developer တွေအနေနဲ့ ဘယ်လိုမျိုး interact လုပ်ကြမလဲဆိုတာကို လေ့လာကြမှာဖြစ်ပါတယ်။

Push

Stack ထဲကို value အသစ်ထပ်ထည့်တာပေါ့။

var stack = [1, 2, 3]
stack.push(4) // stack = [1, 2, 3, 4]
stack.push(5) // stack = [1, 2, 3, 4, 5]

Pop

Stack ရဲ့ ထိပ်ဆုံးက value ကို remove လုပ်ပြီး အဲ့ value ကို return ပြန်ပေးတာပေါ့။

var stack = [1, 2, 3]
var value = stack.pop() // value = 3, stack = [1, 2]
value = stack.pop() // value = 2, stack = [1]

Peek or Top

Stack ရဲ့ ထိပ်ဆုံးက value ကို remove မလုပ်ဘဲနဲ့ value ကို return ပြန်ပေးတာပေါ့။ Pop နဲ့တူတယ်ထင်ရနိုင်ပေမယ့် peek က remove မလုပ်ပါဘူး။

var stack = [1, 2, 3]
var value = stack.peek() // value = 3, stack = [1, 2, 3]
value = stack.peek() // value = 3, stack = [1, 2, 3]

isEmpty

Stack က empty ဖြစ်နေသလား စစ်တာ။

isFull (Optional)

တစ်ချို့ stack တွေက fixed-size ဖြစ်နေတာမျိုးရှိတယ်။ အဲ့လိုဆိုရင် item အသစ်ထပ်ထည့်လို့ရသေးလား မရလား စစ်တာပေါ့။

Simple Stack Implementation

public struct Stack<Value> {
  private var array = [Value]()

  public var isEmpty: Bool { array.isEmpty }
  
  public var peek: Value? { array.last }

  public mutating func push(_ element: Value) { array.append(element) }

  public mutating func pop() -> Value? { array.popLast() }

}

Array ကိုပဲ လုပ်သွားတာဆိုတော့ တော်တော်လေးဖတ်ရရှင်းမှာပါ။

Swift developer တွေအတွက် ဒီ stack ကို for loop နဲ့သုံးချင်တယ်ဆိုရင်တော့ Sequence protocol ကို implement လုပ်လိုက်ရင်ရပါတယ်။

extension Stack: Sequence {
  public func makeIterator() -> AnyIterator<Value> {
    var current = self
    return AnyIterator {
      return current.pop()
    }
  }
}

ဒီနေရာမှာ တစ်ခုသတိထားစေချင်တာက struct နဲ့ class အသုံးလေးပါ။ တစ်ကယ်လို့သာ Stack က class သာဆိုရင် ကျွန်တော်တို့ for loop နဲ့ pop လုပ်သွားရင် stack ထဲမှာ ဘာမှကျန်တော့မှာမဟုတ်ပါဘူး။ ဒါပေမယ့် ကျွန်တော်က struct ကိုသုံးထားတဲ့အတွက် var current = self ဆိုပြီး အရင် copy ပြီးတော့မှ အဲ့ copy ကို pop လုပ်သွားတာမို့လို့ original stack ရဲ့ element တွေကို မထိခိုက်တာပါ။

Use cases

Stack ကိုအသုံးများတဲ့နေရာတွေကတော့ navigation မှာပါ။ SwiftUI မှာဆိုရင် navigation stack, UIKit မှာဆိုရင် UINavigationController အားလုံးက stack တွေပဲဖြစ်ပါတယ်။

Usecase 1

နောက်ထပ် typical usecase ကတော့ bracket တွေ အဖွင့်အပိတ် ညီ/မညီ စစ်တဲ့ပုစ္ဆာမျိုးမှာပါ။ ဆိုကြပါစို့ string တစ်ခုပေးထားတယ် “(())()” ဆိုပါစို့။​ ဒါဆိုရင် အဖွင့်ကွင်းနဲ့ အပိတ်ကွင်းက တူတဲ့အတွက် မှန်တယ်။​ အဲ့လိုမဟုတ်ပဲနဲ့ “(()” ဆိုရင် ကွင်းက နှစ်ခါဖွင့်ပြီး တစ်ခါပဲ ပတ်ထားတဲ့အတွက် မှားတယ်ပေါ့။ ဒီလိုပုစ္ဆာမျိုးကို ဖြေရှင်းတဲ့နေရာမှာ stack ကို သုံးပြီး ဖြေရှင်းလို့ရပါတယ်။

func isValid(_ string: String) -> Bool {
  // 1
  var stack = Stack<Character>()
  
  // 2
  for char in string {
    // 3
    if char == "(" {
      stack.push(char)
    } else {
      // 4
      if stack.peek == "(" {
        // 5
        stack.pop()
      } else {
        // 6
        return false
      }
    }
  }
  
  // 7
  return stack.isEmpty
}

print(isValidString("(())()")) // true
print(isValidString("(())())")) // false

1. Character stack တစ်ခု ဆောက်ပါတယ်။
2. String ထဲက character တစ်လုံးချင်းစီကို loop ပတ်ထုတ်ပါတယ်။
3. တစ်ကယ်လို့ လက်ရှိ character က ကွင်းဖွင့် “(“ ဆိုရင်တော့ stack ထဲကိုထည့်လိုက်ပါမယ်။
4. တစ်ကယ်လို့ လက်ရှိ character က ကွင်းပိတ် “)” ဆိုရင် stack ထဲမှာ နောက်ဆုံးထည့်ထားတာက ကွင်းဖွင့် “(“ လား​ရှာရပါမယ်။
5. တစ်က​ယ်လို့ stack ကို peek လုပ်လိုက်တော့ နောက်ဆုံးထည့်ထားတာက “(” ဆိုရင်တော့ အဖွင့်အပိတ် တစ်တွဲရပြီဖြစ်တဲ့အတွက် နောက်ဆုံးထည့်ထားတဲ့ကောင်ကို pop လုပ်ပါမယ်။
6. တစ်ကယ်လို့ နောက်ဆုံးထည့်ထားတာကလည်း ကွင်းပိတ် “)”​ဆိုရင် အပိတ်က နှစ်ခါထပ်သွားပြီဖြစ်တဲ့အတွက် ဆက်ကြည့်စရာမလိုပါဘူး။ ကွင်းပိတ် နှစ်ခါထပ်သွားတဲ့အတွက် မမှန်နိုင်တော့ပါဘူး။
7. တစ်ကယ်လို့ loop ပတ်ပြီးတဲ့အချိန်မှာ stack ထဲမှာ item တစ်ခုမှမကျန်တော့ရင်လည်း valid ဖြစ်ပါတယ်။
   Code ကိုဒီအထိရှင်းပြပြီးပြီဆိုတော့ ကိုယ့်ဘာသာ အခြေအနေအမျိုးမျိုးကို dry run လုပ်ကြည့်ပါ။

input string: "( ( ) ) ( ) "

[1st iteration]
string: "( ( ) ) ( ) "
         👆
char: "("
stack: []
### since it is not the closing ")", we will push it to stack ###

[2nd iteration]
string: "( ( ) ) ( ) "
           👆
char: "("
stack: ["("]
### push again ###

[3rd iteration]
string: "( ( ) ) ( ) "
             👆
char: ")"
stack: ["(", "("]
### since the top element is "(", we will pop ###

[4th iteration]
string: "( ( ) ) ( ) "
               👆
char: ")"
stack: ["("]
### we will pop again ###

[5th iteration]
string: "( ( ) ) ( ) "
                 👆
char: "("
stack: []
### push ###

[6th iteration]
string: "( ( ) ) ( ) "
                   👆
char: ")"
stack: ["("]
### pop ###

Now, loop is ended, and stack is empty, so, 
the given string is valid (return true)

ဒါက ကျွန်တော် example run ပြထားတာပါ။ အင်တာဗျူးတွေဖြေတဲ့အခါမှာ compiler အကူအညီမလိုပဲ debug လိုက်နိုင်ဖို့လိုတဲ့အတွက် အခုကတည်းက ကိုယ့်ဘာသာ dry run ချရေးတတ်တဲ့အလေ့အကျင့်လုပ်ထားပါ။ ကျွန်တော်ကတော့ google docs နဲ့ကျင့်ပါတယ်။ အပေါ်ကပုစ္ဆာမျိုးမေးလာမယ်ဆိုရင် ကိုယ့်ဘက်က code စမရေးခင် အရင်ဆုံး clarifying questions တွေမေးရပါမယ်။

• String က empty ဆိုရင် true ပြန်ရမလား false ပြန်ရမလား
• Whitespace “ “ တွေပါလာရင် skip ရမလား?
• “(“ နဲ့ “)” မဟုတ်တဲ့ character ပါလာနိုင်ချေရှိလား ပါလာရင်ဘယ်လိုလုပ်ရမလဲ?

Usecase 2

ထပ်ပြီးရှိနိုင်တာက သင်္ချာ expression တွေကိုဖြေရှင်းတဲ့ ပုစ္ဆာမျိုးပါ။

Question: Given a string expression containing operands and operators (e.g., 3 + 5 * (2 - 8)), implement an algorithm to evaluate it using stack(s). The expression may contain:

• Operands (numbers or variables)
• Operators +, -, *, /
• Parentheses ( and )

You must respect operator precedence (multiplication/division before addition/subtraction) and associativity.

လွယ်တဲ့ပုစ္ဆာကိုကိုယ့်ဘာသာဖြေပြီး ခက်တဲ့ပုစ္ဆာ အိမ်စာပေးတယ်မထင်ပါနဲ့။ နည်းနည်းလေးစဥ်းစားပြီး ဖြေရှင်းကြည့်ပါ။

func evaluate(_ expression: String) -> Double {
  fatalError("Unimplemented")
}

Hint: you should maintain two stacks, one for operands and one for operators (+, -, *, /, etc)

Complex ဖြစ်တဲ့ expression တွေမရရင်တောင် simple expression လောက်တော့ ရေးလို့ရမှာပါ။

Usecase 3

Undo/redo တွေကလည်း stack တွေနဲ့ထိန်းတာပါပဲ။ Command pattern မှာဆိုရင် command တွေကို stack အနေနဲ့သိမ်းထားပြီး undo/redo လုပ်ခိုင်းလို့ရပါတယ်။ Text editor တွေ graphic editor တွေလို app မျိုးတွေမှာသုံးပါတယ်။

Conclusion

Stack နဲ့ပတ်သက်တဲ့ ဂုဏ်သတ္တိတွေ အသုံးဝင်ပုံ သုံးတဲ့နေရာတွေကို ဆွေးနွေးပေးထားပါတယ်။ အားလုံးလည်း နားလည်မယ်လို့ ထင်ပါတယ်။

Until next time!