数据结构-栈和队列

两个栈实现队列
class QueueWithTwoStacks:
    '''思路：栈1用来进栈，栈2用来出栈'''

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def append(self, key):
        self.stack1.append(key)

    def popleft(self):
        ##stack2 没有值添加
        if not self.stack2:
            while self.stack1:
                # 进栈
                self.stack2.append(self.stack1.pop())

        if not self.stack2:
            raise Exception('empty')
        # stack2 有值pop
        return self.stack2.pop()


q = QueueWithTwoStacks()

q.append(1)
q.append(2)
print(q.popleft())
q.append(3)

print(q.popleft())
print(q.popleft())

q.append(5)
q.append(6)
print(q.popleft())

什
么
都
看
不
见

两个队列实现栈
from collections import deque


class StackWithTwoQueues:
    '''一个队列用来进队，删除操作：长度>1，先把另一个队列 除过最后一元素，全部插入到另一个队列，删除最后一个即可'''
    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()

    def append(self, key):
        self.queue1.append(key)

    def pop(self):
        if not self.queue1 and not self.queue2:
            raise IndexError('stack is empty')

        if not self.queue2:
            if len(self.queue1) == 1:
                return self.queue1.popleft()

            # 留每个队列的最后一个元素即可
            for i in range(len(self.queue1) - 1):
                self.queue2.append(self.queue1.popleft())
            return self.queue1.popleft()  # 此时队列1空

        if not self.queue1:
            if len(self.queue2) == 1:
                return self.queue2.popleft()

            # 留每个队列的最后一个元素即可
            for i in range(len(self.queue2) - 1):
                self.queue1.append(self.queue2.popleft())
            return self.queue2.popleft()  # 此时队列2空


stack=StackWithTwoQueues()


stack.append('a')
stack.append('b')
stack.append('c')

print(stack.pop())
print(stack.pop())
print(stack.queue1)
print(stack.queue2)

stack.append('d')

print(stack.pop())

数据结构-栈和队列

相关推荐