Pythonのデータ構造 - スタックとキューの実装 (2)

1. リストは 2 つのスタックを実装します

class Twostacks(object):
    def __init__(self):
        self.stack=[]
        self.a_size=0
        self.b_size=0
        self.top=0
    def a_isEmpty(self):
        return self.a_size==0
    def a_push(self,item):
        self.stack.insert(self.a_size,item)
        self.a_size+=1        
    def a_pop(self):
        if self.a_size>=1:
            item=self.stack[self.a_size-1]
            self.stack.remove(item)
            self.a_size-=1
            return item
    def b_isEmpty(self):
        return self.b_size==0
    def b_push(self,item):
        self.stack.insert(self.a_size,item)
        self.b_size+=1
    def b_pop(self):
        if self.b_size>=1:
            item=self.stack[self.a_size]
            self.stack.remove(item)
            self.b_size-=1
            return item

2. 2 つのスタックはキューを実装します

2 つのスタック s1 と s2 があります。キューに入れるときは、要素を s1 にプッシュします。デキューするときに、s2 が空かどうかを判断します。空でない場合は、先頭の要素を直接ポップアップします。空の場合は、s1 の要素を 1 つずつ s2 に「注ぎ」、最後の要素をキューからポップします。

class Stack(object):
    def __init__(self):
        self.stack=[]
    def isEmpty(self):
        return self.stack==[]
    def push(self,item):
        self.stack.append(item)
    def pop(self):
        if self.isEmpty():
            raise IndexError,'pop from empty stack'
        return self.stack.pop()
    def size(self):
        return len(self.stack)
class Queue_with_stacks(object):
    def __init__(self):
        self.stackA=Stack()
        self.stackB=Stack()
    def isEmpty(self):
        return self.stackA.isEmpty() and self.stackB.isEmpty()
    def enqueue(self,item):
        self.stackA.push(item)
    def dequeue(self):
        if self.stackB.isEmpty():
            if self.stackA.isEmpty():
                raise IndexError,'queue is empty.'
            while self.stackA.size()>=2:
                self.stackB.push(self.stackA.pop())
            
            return self.stackA.pop()
        else:
            return self.stackB.pop()

3. 2 つのキューで 1 つのスタックを実装します

class Queue(object):
    def __init__(self):
        self.queue=[]
    def isEmpty(self):
        return self.queue==[]
    def enqueue(self,x):
        self.queue.append(x)
    def dequeue(self):
        if self.queue:
            a=self.queue[0]
            self.queue.remove(a)
            return a
        else:
            raise IndexError,'queue is empty'
    def size(self):
        return len(self.queue)
class Stack_with_queues(object):
    def __init__(self):
        self.queueA=Queue()
        self.queueB=Queue()
    def isEmpty(self):
        return self.queueA.isEmpty() and self.queueB.isEmpty()
    def push(self,item):
        if self.queueB.isEmpty():
            self.queueA.enqueue(item)
        else:
            self.queueB.enqueue(item)
    def pop(self):
        if self.isEmpty():
            raise IndexError,'stack is empty'
        elif self.queueB.isEmpty():
            while not self.queueA.isEmpty():
                cur=self.queueA.dequeue()
                if self.queueA.isEmpty():
                    return cur
                self.queueB.enqueue(cur)
        else:           
             while not self.queueB.isEmpty():
                cur=self.queueB.dequeue()
                if self.queueB.isEmpty():
                    return cur
                self.queueA.enqueue(cur)

上記は、Python データ構造 - スタックとキューの実装 (2) の内容です。その他の関連記事については、PHP 中国語 Web サイト (www.php.ん）！