# -*- coding: utf-8 -*-
"""
Stack and Queue — scratch থেকে বানানো implementation, শেখার জন্য।

এখানে যা যা আছে:
  1. Stack       — Python list-এর উপর LIFO (push/pop/peek)।
  2. Queue       — collections.deque-র উপর FIFO (enqueue/dequeue/front)।
  3. MinStack    — twin-stack history trick দিয়ে O(1) get_min।
  4. is_balanced — bracket matching, classic stack pattern।
  5. next_greater_elements — monotonic stack, O(n)।
  6. sliding_window_max    — monotonic deque, O(n)। Chapter-এর centerpiece।

সবকিছু শুধু Python standard library ব্যবহার করে।
File-টা সরাসরি চালাও:  python implementation.py
Demo-র সব assert pass করতেই হবে।
"""

from collections import deque


class Stack:
    """Python list-এর উপর LIFO stack। List-এর ডান প্রান্তটাই top,
    কারণ ডান প্রান্তে append/pop-ই হলো list-এর O(1) operation।"""

    def __init__(self):
        self._items = []

    def push(self, item):
        """O(1) amortized — একটা dynamic-array append।"""
        self._items.append(item)

    def pop(self):
        """O(1)। খালি হলে IndexError ওঠায় (list.pop-এর মতো)।"""
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        """O(1)। না সরিয়ে top-টা দেখো।"""
        if not self._items:
            raise IndexError("peek at empty stack")
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0

    def __len__(self):
        return len(self._items)


class Queue:
    """collections.deque-র উপর FIFO queue।

    List কেন না? list.pop(0) বাকি প্রতিটা element shift করে: প্রতি
    dequeue-তে O(n), n operation-এ O(n^2)। deque.popleft() O(1)
    কারণ deque শুধু একটা internal front marker এগিয়ে নেয়।
    """

    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        """O(1): লাইনের পেছনে যোগ দাও।"""
        self._items.append(item)

    def dequeue(self):
        """O(1): লাইনের সামনের জনকে serve করো।"""
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

    def front(self):
        """O(1): পরে কে serve হবে সেটা peek করো।"""
        if not self._items:
            raise IndexError("front of empty queue")
        return self._items[0]

    def is_empty(self):
        return len(self._items) == 0

    def __len__(self):
        return len(self._items)


class MinStack:
    """এমন একটা stack যেটা get_min()-এর উত্তরও O(1)-এ দেয়।

    Trick: একটা twin stack `_mins` যেখানে _mins[i] = stack-এ এখনো
    থাকা প্রথম i+1-টা push করা element-এর minimum। Twin-টাকে
    lockstep-এ push আর pop করো, আর minimum-এর HISTORY সংরক্ষিত
    থাকে — তাই current minimum pop করলে আপনা থেকেই আগেরটা
    বেরিয়ে আসে।
    """

    def __init__(self):
        self._stack = []
        self._mins = []      # _mins[-1] সবসময়ই current minimum

    def push(self, x):
        self._stack.append(x)
        current_min = x if not self._mins else min(x, self._mins[-1])
        self._mins.append(current_min)

    def pop(self):
        if not self._stack:
            raise IndexError("pop from empty MinStack")
        self._mins.pop()                 # lockstep: history aligned থাকে
        return self._stack.pop()

    def top(self):
        if not self._stack:
            raise IndexError("top of empty MinStack")
        return self._stack[-1]

    def get_min(self):
        """O(1) — কোনো scanning না, twin stack আগে থেকেই জানে।"""
        if not self._mins:
            raise IndexError("get_min of empty MinStack")
        return self._mins[-1]


# ---------------------------------------------------------------------- #
# Pattern functions
# ---------------------------------------------------------------------- #

def is_balanced(s):
    """Stack দিয়ে bracket matching। O(n)।

    Stack ধরে রাখে প্রতিটা opening bracket যেটা এখনো বন্ধ হয়নি।
    Fail করার তিনটা উপায়:
      1. stack খালি থাকা অবস্থায় একটা closer আসে (underflow),
      2. একটা closer top-এর opener-এর সাথে মেলে না (mismatch),
      3. input শেষ হওয়ার পরেও opener রয়ে যায় (leftovers)।
    """
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False             # underflow অথবা mismatch
    return not stack                     # leftovers => False


def next_greater_elements(nums):
    """Monotonic stack: প্রতিটা element-এর জন্য তার ডানদিকের প্রথম
    STRICTLY greater value, না থাকলে -1। O(n)।

    Stack ধরে রাখে INDEX যাদের answer unknown; তাদের value গুলো
    bottom থেকে top decreasing। প্রতিটা নতুন আসা element pop করে
    (= answer দেয়) প্রতিটা index-কে যাদের সে হারায়। প্রতি index-এ
    একবার push + বড়জোর একবার pop
    => O(n) total, nested-দেখতে while loop সত্ত্বেও।
    """
    n = len(nums)
    answer = [-1] * n
    stack = []                           # index গুলো, value decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            answer[stack.pop()] = x      # x-ই তাদের next greater
        stack.append(i)
    return answer                        # leftover-রা নিজেদের -1 রাখে


def sliding_window_max(nums, k):
    """Size k-এর প্রতিটা window-র maximum — monotonic deque। O(n)।

    Inherits from: sliding-window basic (এক step করে এগোতে থাকা
    একটা window, দেখো ../02-arrays-and-strings/patterns.md) + the
    queue (candidate-রা পেছনে ঢোকে, সামনে expire করে)।

    The thinking tweak: value x এলে, deque-র প্রতিটা element যার
    value SMALLER-OR-EQUAL, সেটা চিরকালের জন্য useless — x নতুন
    (তাদের চেয়ে বেশিদিন বাঁচবে) আর অন্তত তাদের সমান বড় (তাদের
    চেয়ে এগিয়ে থাকবে) — তাই তাদের পেছন থেকে eject করো। Deque-র
    value গুলো তাই front -> back কমতে থাকে, যার মানে
    THE FRONT ALWAYS HOLDS THE CURRENT WINDOW'S MAXIMUM।

    আমরা index রাখি (value না) যাতে ধরতে পারি front-টা কখন window
    থেকে বেরিয়ে গেছে। প্রতিটা index একবার ঢোকে আর বড়জোর একবার
    বের হয় (back-eject অথবা front-expire) => O(n) total।
    """
    if k <= 0:
        raise ValueError("window size must be positive")
    if not nums:
        return []

    dq = deque()                         # index গুলো; value decreasing
    result = []
    for i, x in enumerate(nums):
        # 1) পেছন থেকে useless element গুলো eject করো
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        # 2) নতুন আসা element পেছনে ঢোকে
        dq.append(i)
        # 3) front window [i-k+1 .. i] থেকে বেরিয়ে গেলে eject করো
        if dq[0] <= i - k:
            dq.popleft()
        # 4) প্রথম window complete হলেই, front-টাই answer
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result


# ---------------------------------------------------------------------- #
# Demo + tests
# ---------------------------------------------------------------------- #

if __name__ == "__main__":
    print("=== Stack: LIFO ===")
    st = Stack()
    assert st.is_empty()
    st.push(4)
    st.push(9)
    st.push(2)
    assert len(st) == 3
    assert st.peek() == 2                # top-ই সবচেয়ে নতুনটা
    assert st.pop() == 2                 # last in, first out
    assert st.pop() == 9
    assert st.pop() == 4
    assert st.is_empty()
    try:
        st.pop()
        raise AssertionError("expected IndexError")
    except IndexError:
        pass

    print("=== Queue: FIFO ===")
    q = Queue()
    q.enqueue('job1')
    q.enqueue('job2')
    q.enqueue('job3')
    assert q.front() == 'job1'           # সবচেয়ে পুরনোটা পরে serve হয়
    assert q.dequeue() == 'job1'         # first in, first out
    assert q.dequeue() == 'job2'
    assert len(q) == 1
    assert not q.is_empty()
    assert q.dequeue() == 'job3'
    assert q.is_empty()

    print("=== MinStack: O(1) minimum ===")
    ms = MinStack()
    ms.push(5)
    ms.push(2)
    ms.push(7)
    assert ms.get_min() == 2             # এখন পর্যন্ত 2-ই সবচেয়ে ছোট
    assert ms.top() == 7
    assert ms.pop() == 7
    assert ms.get_min() == 2             # অপরিবর্তিত
    assert ms.pop() == 2                 # minimum-টাকেই pop করো...
    assert ms.get_min() == 5             # ...history আগের min দেখিয়ে দেয়
    ms.push(1)
    assert ms.get_min() == 1

    print("=== Bracket matching ===")
    assert is_balanced("()[]{}") is True
    assert is_balanced("([{}])") is True
    assert is_balanced("(]") is False          # mismatch
    assert is_balanced("([)]") is False        # interleaved, nested না
    assert is_balanced("(((") is False         # leftovers
    assert is_balanced(")") is False           # underflow
    assert is_balanced("") is True             # কিছু না থাকায় কোনো দোষ নেই
    assert is_balanced("a(b)c") is True        # non-bracket গুলো ignore হয়

    print("=== Monotonic stack: next greater element ===")
    assert next_greater_elements([2, 1, 5, 3]) == [5, 5, -1, -1]
    assert next_greater_elements([1, 2, 3]) == [2, 3, -1]
    assert next_greater_elements([3, 2, 1]) == [-1, -1, -1]
    assert next_greater_elements([]) == []
    assert next_greater_elements([7]) == [-1]

    print("=== Monotonic deque: sliding window maximum ===")
    assert sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3) == \
        [3, 3, 5, 5, 6, 7]                     # worked example-টা
    assert sliding_window_max([1], 1) == [1]
    assert sliding_window_max([9, 8, 7, 6], 2) == [9, 8, 7]
    assert sliding_window_max([1, 2, 3, 4], 2) == [2, 3, 4]
    assert sliding_window_max([4, 4, 4], 3) == [4]
    assert sliding_window_max([], 3) == []
    assert sliding_window_max([5, 1, 5], 1) == [5, 1, 5]   # k=1: identity

    print("\nAll asserts passed. Order of processing: mastered.")