การจำลองคิวและสแตกซึ่งกันและกัน

เหตุใดจึงจำลองโครงสร้างหนึ่งด้วยอีกโครงสร้างหนึ่ง

คิวโดยใช้สแตกสองตัว (วิธีเลื่อนการย้าย)

class MyQueue:
    def __init__(self):
        self.inbox  = []
        self.outbox = []

    def push(self, x):
        self.inbox.append(x)

    def _transfer(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._transfer()
        return self.outbox.pop()

    def peek(self):
        self._transfer()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek())  # 1
print(q.pop())   # 1
print(q.pop())   # 2
q.push(4)
print(q.pop())   # 3

การวิเคราะห์ O(1) แบบเฉลี่ยตัดจำหน่ายสำหรับคิวจากสแตก

# Trace transfer costs for 10 push/pop interleaved
class TrackedQueue:
    def __init__(self):
        self.inbox = []; self.outbox = []; self.transfers = 0

    def push(self, x): self.inbox.append(x)

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.transfers += 1
        return self.outbox.pop()

q = TrackedQueue()
for i in range(5):
    q.push(i)
for _ in range(5):
    q.pop()
q.push(10); q.push(20)
q.pop()
print('Total transfer operations:', q.transfers)  # at most n

สแตกโดยใช้คิวสองตัว (นำออกแบบเลื่อนเวลา)

from collections import deque

class MyStack:
    def __init__(self):
        self.main = deque()
        self.temp = deque()

    def push(self, x):
        self.main.append(x)   # O(1)

    def pop(self):
        # Move all but last element to temp
        while len(self.main) > 1:
            self.temp.append(self.main.popleft())
        val = self.main.popleft()   # the 'top'
        self.main, self.temp = self.temp, self.main  # swap
        return val

    def top(self):
        while len(self.main) > 1:
            self.temp.append(self.main.popleft())
        val = self.main[0]
        self.temp.append(self.main.popleft())
        self.main, self.temp = self.temp, self.main
        return val

    def empty(self):
        return len(self.main) == 0

s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.pop())  # 2

สแตกโดยใช้คิวตัวเดียว (หมุนเมื่อเพิ่มสมาชิก)

from collections import deque

class MyStackOneQueue:
    def __init__(self):
        self.q = deque()

    def push(self, x):
        self.q.append(x)
        # Rotate: move all preceding elements behind x
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

    def top(self):
        return self.q[0]

    def empty(self):
        return len(self.q) == 0

s = MyStackOneQueue()
s.push(1); s.push(2); s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.top())  # 2

สรุปข้อแลกเปลี่ยน: ควรเลือกแบบใด

print('Queue from 2 stacks: push O(1), pop O(1) amortised')
print('Stack from 2 queues: push O(1), pop O(n)')
print('Stack from 1 queue:  push O(n), pop O(1)')

เหตุใดการกลับลำดับจึงทำให้ได้ FIFO

# Demonstrate double-reversal = FIFO
inbox  = [1, 2, 3]   # pushed in this order
outbox = []
while inbox:
    outbox.append(inbox.pop())
print('outbox (one reversal):', outbox)  # [3, 2, 1] top-to-bottom

# Pop from outbox gives FIFO
result = []
while outbox:
    result.append(outbox.pop())
print('dequeued:', result)  # [1, 2, 3] — FIFO!

LeetCode 232: สร้างคิวโดยใช้สแตก

class MyQueue:
    def __init__(self):
        self.inbox  = []
        self.outbox = []

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        self.peek()             # ensure outbox is populated
        return self.outbox.pop()

    def peek(self):
        if not self.outbox:
            while self.inbox:   # transfer lazily
                self.outbox.append(self.inbox.pop())
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

# Simulation
q = MyQueue()
q.push(1); q.push(2)
print(q.peek())  # 1
print(q.pop())   # 1
print(q.empty()) # False

LeetCode 225: สร้างสแตกโดยใช้คิว

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x):       # O(n)
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):           # O(1)
        return self.q.popleft()

    def top(self):           # O(1)
        return self.q[0]

    def empty(self):
        return len(self.q) == 0

s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.top())  # 2
print(s.empty()) # False

การขยายเป็นสแตกสามชุดในอาร์เรย์เดียว

class ThreeStacks:
    def __init__(self, size):
        self.data = [0] * (3 * size)
        self.tops = [-1, -1, -1]  # relative top of each stack
        self.size = size

    def push(self, stack_num, val):
        self.tops[stack_num] += 1
        if self.tops[stack_num] >= self.size:
            raise OverflowError('stack full')
        self.data[stack_num * self.size + self.tops[stack_num]] = val

    def pop(self, stack_num):
        if self.tops[stack_num] < 0:
            raise IndexError('stack empty')
        val = self.data[stack_num * self.size + self.tops[stack_num]]
        self.tops[stack_num] -= 1
        return val

ts = ThreeStacks(5)
ts.push(0, 10); ts.push(1, 20); ts.push(2, 30)
print(ts.pop(0), ts.pop(1), ts.pop(2))  # 10 20 30

ประเด็นสำคัญ: รูปแบบการจำลอง

ตรวจสอบความเข้าใจ

สรุปบทเรียน