Python data structure - implementation of stack and queue (2)

1. A list implements two stacks

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. Two stacks implement a queue

There are two stacks s1 and s2. When enqueuing, push the element into s1. When dequeuing, determine whether s2 is empty. If it is not empty, pop up the top element directly; if it is empty, "pour" the elements of s1 into s2 one by one, pop the last element out of the queue.

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. Two queues implement one stack

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)

The above is the content of Python data structure - implementation of stack and queue (2). For more related articles, please pay attention to the PHP Chinese website (www.php.cn)!