数据结构与算法python语言实现第6章课后习题答案

R-6.1 如果在一个初始化为空的栈上执行如下一系列操作，将返回什么值？
操作 返回值
push(5) 空
push(3) 空
pop() 3
push(2) 空
push(8) 空
pop() 8
pop() 2
push(9) 空
push(1) 空
pop() 1
push(7)
push(6)
pop() 6
pop() 7
push(4)
pop() 4
pop() 9
R-6.2 假设一初始化为空的栈S已经执行了25个push操作，12个top操作，和10个pop操作，其中3个触发了栈空错误。请问S目前的大小为多少

如果3个栈空错误是top触发的 说明10次pop操作成功 S目前大小为25-10=15
如果2个栈空错误是top触发的一个是pop触发的 说明pop操作成功9次S目前的大小为25 -9 =16
如果1个栈空错误是top触发的 说明8次pop操作成功 S目前大小为25-8=17
如果0个栈空错误是top触发的一个是pop触发的 说明pop操作成功7次S目前的大小为25 -7 =18

R-6.3 实现一个函数transfer（S,T)将栈S中的所有元素转移到栈T中，使位于S栈顶的元素被第一个插入栈中，使位于S栈底的元素最后被插入栈T的顶部

class Empty(Exception):
    pass #占位语句
class ArrayStack:
    def __init__(self):
        self._data=[]
    def __len__(self):
        return len(self._data)
    def is_empty(self):
        return len(self._data)==0
    def push(self,e):
        self._data.append(e)
    def top(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data[-1]
    def pop(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data.pop()
    def print_stack(self):
        print(self._data)
def transfer(S,T):
    while S.is_empty()!=True:
        (())
S=ArrayStack()
T=ArrayStack()
(8)
(7)
(6)
(5)
transfer(S,T)
T.print_stack()

R-6.4 给出一个用于从栈中移除所有元素的递归实现方法

class Empty(Exception):
    pass #占位语句
class ArrayStack:
    def __init__(self):
        self._data=[]
    def __len__(self):
        return len(self._data)
    def is_empty(self):
        return len(self._data)==0
    def push(self,e):
        self._data.append(e)
    def top(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data[-1]
    def pop(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data.pop()
    def print_stack(self):
        print(self._data)
def move(S):
    if S.is_empty()!=True:
        ()
        move(S)
S=ArrayStack()
(8)
(7)
(6)
(5)
S.print_stack()
move(S)
S.print_stack()

R-6.5 实现一个函数,通过将一个列表内的元素按顺序压入堆栈中,然后逆序把它们写回到列表中,实现列表的逆序

class Empty(Exception):
    pass #占位语句
class ArrayStack:
    def __init__(self):
        self._data=[]
    def __len__(self):
        return len(self._data)
    def is_empty(self):
        return len(self._data)==0
    def push(self,e):
        self._data.append(e)
    def top(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data[-1]
    def pop(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data.pop()
    def print_stack(self):
        print(self._data)
def reverse(S,data):
    while len(data)!=0:
        ((0))
    while S.is_empty()!=True:
        (())
data=[1,2,3,4,5,6,7,8,9,10]
S=ArrayStack()
reverse(S,data)
print(data)

R-6.7 如果在一个初始化为空的队列上执行如下一系列操作后,返回值是什么？

操作	返回值	队列
enqueue(5)	_	[5]
enqueue(3)	_	[5,3]
dequeue()	5	[3]
enqueue(2)	_	[3,2]
enqueue(8)	_	[3,2,8]
dequeue()	3	[2,8]
dequeue()	2	[8]
enqueue(9)	_	[8,9]
enqueue(1)	_	[8,9,1]
dequeue()	8	[9,1]
enqueue(7)	_	[9,1,7]
enqueue(6)	_	[9,1,7,6]
dequeue()	9	[1,7,6]
dequeue()	1	[7,6]
enqueue(4)	_	[7,6,4]
dequeue()	7	[6,4]
dequeue()	6	[4]

R-6.8 假设一个初始化为空的队列Q已经执行了32次入队操作,10次取首部元素操作和15次出队操作,其中5次触发了队列为空的错误。队列Q目前的大小是多少?

如果5个队列空错误是first触发的 说明15次dequeue操作成功 S目前大小为32-15=17
如果4个队列空错误是first触发的 说明14次dequeue操作成功 S目前大小为32-14=18
如果3个队列空错误是first触发的 说明13次dequeue操作成功 S目前大小为32-13=19
如果2个队列空错误是first触发的 说明12次dequeue操作成功 S目前大小为32-12=20
如果1个队列空错误是first触发的 说明11次dequeue操作成功 S目前大小为32-11=21
如果0个队列空错误是first触发的 说明10次dequeue操作成功 S目前大小为32-10=22

R-6.11 给出一个简单的适配器实现队列ADT，其中采用一个实例

from collections import deque
class Empty(Exception):
    pass #占位语句
class ArrayQueue:
    DEFAULT_CAPACITY=10
    def __init__(self):
        self._data=deque()
    def __len__(self):
        return self._data.__len__()
    def is_empty(self):
        return self._data.__len__()==0
    def dequeue(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        return  self._data.popleft()
    def enqueue(self,e):
        self._data.append(e)
Q=ArrayQueue()
(3)
(4)
print(Q.__len__())
print(())
print(())

R-6.12 在一个初始化为空的双端队列中执行以下一系列操作，将会返回什么结果?

操作	返回值	双端队列元素情况
add_first(4)	_	[4]
add_first(8)	_	[8,4]
add_first(9)	_	[9,8,4]
add_first(5)	_	[5,9,8,4]
delete_first()	5	[9,8,4]
delete_last()	4	[9,8]
add_last(7)	_	[9,8,7]
first()	9	[9,8,7]
last()	7	[9,8,7]
add_last(6)	_	[9,8,7,6]
delete_first()	9	[8,7,6]
delete_first()	8	[7,6]

R-6.13 假设有一个含有数字(1,2,3,4,5,6,7,8）并按这一顺序排列的双端队列D，并进一步假设有一个初始化为空的队列Q，给出一个只用D和Q（不包含其他变量)实现的代码片段，将元素（1，2，3，5，4，6，7，8）按这一顺序存储在D中

class Empty(Exception):
    pass #占位语句
class ArrayQueue:#队列
    DEFAULT_CAPACITY=10
    def __init__(self):
        self._data=[None]*ArrayQueue.DEFAULT_CAPACITY
        self._size=0
        self._front=0
    def __len__(self):
        return self._size
    def is_empty(self):
        return self._size==0
    def first(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        return self._data[self._front]
    def dequeue(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        answer=self._data[self._front]
        self._data[self._front]=None
        self._front=(self._front+1)%len(self._data)
        self._size=self._size-1
        return answer
    def enqueue(self,e):
        if self._size==len(self._data):
            self._resize(2*len(self._data))
        avail=(self._front+self._size)%len(self._data)
        self._data[avail]=e
        self._size+=1
    def _resize(self,cap):
        old=self._data
        self._data=[None]*cap
        walk=self._front
        for k in range(self._size):
            self._data[k]=old[walk]
            walk=(1+walk)%len(old)
        self._front=0
class DeQueue:#双端队列
    DEFAULT_CAPACITY=10
    def __init__(self):
        self._data=[None]*DeQueue.DEFAULT_CAPACITY
        self._size=0
        self._front=0
    def __len__(self):
        return self._size
    def is_empty(self):
        return self._size==0
    def add_first(self,e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        avail=(self._front-1)%len(self._data)
        self._data[avail]=e
        self._front = avail
        self._size+=1
    def add_last(self,e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        avail = (self._front +self._size) % len(self._data)
        self._data[avail] = e
        self._size += 1
    def delete_first(self):
        if self.is_empty():
            raise Empty("DeQueue is empty")
        answer=self._data[self._front]
        self._data[self._front]=None
        self._front=(self._front+1)%len(self._data)
        self._size-=1
        return answer
    def delete_last(self):
        if self.is_empty():
            raise Empty("DeQueue is empty")
        de=(self._front+self._size-1)%len(self._data)
        answer=self._data[de]
        self._data[de]=None
        self._size-=1
        return answer
    def first(self):
        if self.is_empty():
            raise Empty("DeQueue is empty")
        return self._data[self._front]
    def last(self):
        if self.is_empty():
            raise Empty("DeQueue is empty")
        return self._data[(self._front+self._size-1)%len(self._data)]
    def _resize(self,cap):
        old=self._data
        self._data=[None]*cap
        walk=self._front
        for k in range(self._size):
            self._data[k]=old[walk]
            walk=(1+walk)%len(old)
        self._front=0
    def print_deque(self):
        print(self._data)
def order(D,Q):#重新排序的方法
    while D.is_empty()!=True:
        (D.delete_first())
    D.add_last(())
    D.add_last(())
    D.add_last(())
    D.add_first(())
    D.add_last(())
    D.add_last(D.delete_first())
    D.add_last(())
    D.add_last(())
    D.add_last(())
D=DeQueue()
Q=ArrayQueue()
D.add_last(1)
D.add_last(2)
D.add_last(3)
D.add_last(4)
D.add_last(5)
D.add_last(6)
D.add_last(7)
D.add_last(8)
order(D,Q)
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())

R-6.14 使用双端队列D和一个初始化为空的栈S重复做上一问题

class Empty(Exception):
    pass #占位语句
class DeQueue:
    DEFAULT_CAPACITY=10
    def __init__(self):
        self._data=[None]*DeQueue.DEFAULT_CAPACITY
        self._size=0
        self._front=0
    def __len__(self):
        return self._size
    def is_empty(self):
        return self._size==0
    def add_first(self,e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        avail=(self._front-1)%len(self._data)
        self._data[avail]=e
        self._front = avail
        self._size+=1
    def add_last(self,e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        avail = (self._front +self._size) % len(self._data)
        self._data[avail] = e
        self._size += 1
    def delete_first(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        answer=self._data[self._front]
        self._data[self._front]=None
        self._front=(self._front+1)%len(self._data)
        self._size-=1
        return answer
    def delete_last(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        de=(self._front+self._size-1)%len(self._data)
        answer=self._data[de]
        self._data[de]=None
        self._size-=1
        return answer
    def first(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data[self._front]
    def last(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data[(self._front+self._size-1)%len(self._data)]
    def _resize(self,cap):
        old=self._data
        self._data=[None]*cap
        walk=self._front
        for k in range(self._size):
            self._data[k]=old[walk]
            walk=(1+walk)%len(old)
        self._front=0
    def print_deque(self):
        print(self._data)
class ArrayStack:
    def __init__(self):
        self._data=[]
    def __len__(self):
        return len(self._data)
    def is_empty(self):
        return len(self._data)==0
    def push(self,e):
        self._data.append(e)
    def top(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data[-1]
    def pop(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data.pop()
def order(D,S):
    while D.is_empty()!=True:
        (D.delete_last)
    D.add_last(())
    D.add_last(())
    D.add_last(())
    D.add_first(())
    D.add_last(())
    D.add_last(D.delete_first())
    D.add_last(())
    D.add_last(())
    D.add_last(())
D=DeQueue()
S=ArrayStack()
D.add_last(1)
D.add_last(2)
D.add_last(3)
D.add_last(4)
D.add_last(5)
D.add_last(6)
D.add_last(7)
D.add_last(8)
order(D,S)
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())
print(D.delete_first())

C-6.19 在代码段6-5中，假设html的开始标签结束标签具有与

• 的形式。更普遍的是,html允许可选的属性作为开始标签的一部分。所用的一般格式是<name attribute=“value1”,attribute=“value2”>.修改代码段6-5，使得即使在一个开始标签中包含一个或多个这样的属性时，也可以正确匹配标记

• class Empty(Exception):
      pass #占位语句
  class ArrayStack:
      def __init__(self):
          self._data=[]
      def __len__(self):
          return len(self._data)
      def is_empty(self):
          return len(self._data)==0
      def push(self,e):
          self._data.append(e)
      def top(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data[-1]
      def pop(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data.pop()
      def print_Stack(self):
         print(self._data)
  def is_matched(raw):
      S=ArrayStack()
      j=('<')
      while j!=-1:
          k=('>',j+1)
          if k==-1:
              return False
          tag=raw[j+1:k]
          if not ('/'):
              (tag)
          else:
              if S.is_empty()==True:
                  return False
              e=()
              if tag[1:]!=e[:len(tag)-1]:
                  return False
          j = ('<', k + 1)
      return S.is_empty()
  print(is_matched('<name attribute="seda"</name>'))
  
  

  C-6.20 通过一个栈实现一个非递归算法来枚举{1，2，…,n}所有排列数结果

  C-6.21演示如何使用栈S和队列Q非递归地生成一个含有n个元素的集合所有可能的子集集合

  C-6.22 用非递归方式实现中缀表达式转换为后缀表达式

  C-6.23 假设有三个非空栈R,S,T.请通过一系列操作，将S中的元素以原始的顺序存储到T中原有元素后面，最终R中元素的顺序不变。例如，R=[1,2,3],S=[4,5],T=[6,7,8,9],则最终的结果应为R=[1,2,3],S=[6,7,8,9,4,5].

  先将S中所有元素放到R中 R变为[1,2,3,5,4],再将 T中元素放入R中 R变为 [1,2,3,5,4,9,8,7,6]
  再将R中后6个元素放入S中，完成

  C-6.24 描述如何用一个简单的队列作为实例变量实现堆栈ADT，在方法体中,只有常量占用本地内存。在你设计的方法中,push(),pop(),top()的运行时间分别是多少?

  class Empty(Exception):
      pass #占位语句
  class ArrayQueue:
      DEFAULT_CAPACITY=10
      def __init__(self):
          self._data=[None]*ArrayQueue.DEFAULT_CAPACITY
          self._size=0
          self._front=0
      def __len__(self):
          return self._size
      def is_empty(self):
          return self._size==0
      def first(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          return self._data[self._front]
      def dequeue(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          answer=self._data[self._front]
          self._data[self._front]=None
          self._front=(self._front+1)%len(self._data)
          self._size=self._size-1
          return answer
      def enqueue(self,e):
          if self._size==len(self._data):
              self._resize(2*len(self._data))
          avail=(self._front+self._size)%len(self._data)
          self._data[avail]=e
          self._size+=1
      def _resize(self,cap):
          old=self._data
          self._data=[None]*cap
          walk=self._front
          for k in range(self._size):
              self._data[k]=old[walk]
              walk=(1+walk)%len(old)
          self._front=0
  class QStack:
      def __init__(self):
          self._data=ArrayQueue()
      def __len__(self):
          return self._data.__len__()
      def is_empty(self):
          return self._data.is_empty()
      def push(self,e):
          self._data.enqueue(e)
      def top(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          len = self._data.__len__()
          for i in range(1, len):
              e = self._data.dequeue()
              self._data.enqueue(e)
          e = self._data.dequeue()
          self._data.enqueue(e)
          return e
      def pop(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          len=self._data.__len__()
          for i in range(1,len):
              e=self._data.dequeue()
              self._data.enqueue(e)
          return self._data.dequeue()
  
  

  C-6.25 如何使用两个栈作为实例变量实现队列ADT

  class Empty(Exception):
      pass #占位语句
  class ArrayStack:
      def __init__(self):
          self._data=[]
      def __len__(self):
          return len(self._data)
      def is_empty(self):
          return len(self._data)==0
      def push(self,e):
          self._data.append(e)
      def top(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data[-1]
      def pop(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data.pop()
  class SQueue:
      def __init__(self):
          self._data1=ArrayStack()
          self._data2=ArrayStack()
          self._size=0
      def __len__(self):
          return self._data1.__len__()
      def is_empty(self):
          return self._data1.is_empty()
      def first(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          while self.is_empty()!=True:
              self._data2.push(self._data1.pop())
          e=self._data2.top()
          while self._data2.is_empty()!=True:
              self._data1.push(self._data2.pop())
          return e
      def dequeue(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          while self.is_empty() != True:
              self._data2.push(self._data1.pop())
          e = self._data2.pop()
          while self._data2.is_empty() != True:
              self._data1.push(self._data2.pop())
          return e
      def enqueue(self,e):
         self._data1.push(e)
  Q=SQueue()
  (1)
  (2)
  (3)
  (4)
  (5)
  print(())
  print(())
  print(())
  print(())
  print(())
  print(())
  print(())
  print(())
  print(())
  print(())
  
  

  C-6.26 描述如何使用一个双端队列作为实例变量实现队列ADT

  
  class Empty(Exception):
      pass #占位语句
  class DeQueue:
      DEFAULT_CAPACITY=10
      def __init__(self):
          self._data=[None]*DeQueue.DEFAULT_CAPACITY
          self._size=0
          self._front=0
      def __len__(self):
          return self._size
      def is_empty(self):
          return self._size==0
      def add_first(self,e):
          if self._size == len(self._data):
              self._resize(2 * len(self._data))
          avail=(self._front-1)%len(self._data)
          self._data[avail]=e
          self._front = avail
          self._size+=1
      def add_last(self,e):
          if self._size == len(self._data):
              self._resize(2 * len(self._data))
          avail = (self._front +self._size) % len(self._data)
          self._data[avail] = e
          self._size += 1
      def delete_first(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          answer=self._data[self._front]
          self._data[self._front]=None
          self._front=(self._front+1)%len(self._data)
          self._size-=1
          return answer
      def delete_last(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          de=(self._front+self._size-1)%len(self._data)
          answer=self._data[de]
          self._data[de]=None
          self._size-=1
          return answer
      def first(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data[self._front]
      def last(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data[(self._front+self._size-1)%len(self._data)]
      def _resize(self,cap):
          old=self._data
          self._data=[None]*cap
          walk=self._front
          for k in range(self._size):
              self._data[k]=old[walk]
              walk=(1+walk)%len(old)
          self._front=0
      def print_deque(self):
          print(self._data)
  class JDeQueue:
      def __init__(self):
          self._data=DeQueue()
      def __len__(self):
          return self._data.__len__()
      def is_empty(self):
          return self._data.is_empty()
      def first(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          return self._data.first()
      def dequeue(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          answer=self._data.delete_first()
          return answer
      def enqueue(self,e):
          self._data.add_last(e)
  Q=JDeQueue()
  (1)
  (2)
  (3)
  print(())
  print(())
  print(())
  

  C-6.27 假设有一个包含n个元素的栈S和一个初始为空的队列Q，描述如何用Q扫描S来查看其中是否包含某一特定元素x，算法必须返回到元素在S中原来的位置。算法中只能使用S,Q和固定数量的变量

  class Empty(Exception):
      pass #占位语句
  class ArrayStack:
      def __init__(self):
          self._data=[]
      def __len__(self):
          return len(self._data)
      def is_empty(self):
          return len(self._data)==0
      def push(self,e):
          self._data.append(e)
      def top(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data[-1]
      def pop(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data.pop()
  class ArrayQueue:
      DEFAULT_CAPACITY=10
      def __init__(self):
          self._data=[None]*ArrayQueue.DEFAULT_CAPACITY
          self._size=0
          self._front=0
      def __len__(self):
          return self._size
      def is_empty(self):
          return self._size==0
      def first(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          return self._data[self._front]
      def dequeue(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          answer=self._data[self._front]
          self._data[self._front]=None
          self._front=(self._front+1)%len(self._data)
          self._size=self._size-1
          return answer
      def enqueue(self,e):
          if self._size==len(self._data):
              self._resize(2*len(self._data))
          avail=(self._front+self._size)%len(self._data)
          self._data[avail]=e
          self._size+=1
      def _resize(self,cap):
          old=self._data
          self._data=[None]*cap
          walk=self._front
          for k in range(self._size):
              self._data[k]=old[walk]
              walk=(1+walk)%len(old)
          self._front=0
  def find_num(S,Q,x):
      len=S.__len__()
      i=len
      flag=1
      while S.is_empty()!=True:
          e=()
          (e)
          if e==x:
              flag=0
          if flag==1:
              i-=1
      return i
  S= ArrayStack()
  Q= ArrayQueue()
  (6)
  (7)
  (8)
  (9)
  (10)
  i=find_num(S,Q,9)
  print(i)
  
  

  C-6.28 修改ArrayQueue实现方法,使队列的容量由maxlen限制,其中该最大长度对于构造函数(默认为none)来说是一个可选参数.如果在队列满时调用enqueue操作,则触发一个队列满异常

  class Empty(Exception):
      pass #占位语句
  class MaxLen(Exception):
      pass
  class ArrayQueue:
      MAX=20
      def __init__(self,len=MAX):
          self._data=[None]*len
          self._size=0
          self._front=0
      def __len__(self):
          return self._size
      def is_empty(self):
          return self._size==0
      def first(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          return self._data[self._front]
      def dequeue(self):
          if self.is_empty():
              raise Empty('Queue is empty')
          answer=self._data[self._front]
          self._data[self._front]=None
          self._front=(self._front+1)%len(self._data)
          self._size=self._size-1
          return answer
      def enqueue(self,e):
          if self._size>=20:
              raise MaxLen('Queue is full')
          else:
              self._resize(20)
          avail=(self._front+self._size)%len(self._data)
          self._data[avail]=e
          self._size+=1
      def _resize(self,cap):
          old=self._data
          self._data=[None]*cap
          walk=self._front
          for k in range(self._size):
              self._data[k]=old[walk]
              walk=(1+walk)%len(old)
          self._front=0
      def print_queue(self):
          print(self._data)
  Q=ArrayQueue(10)
  (3)
  (4)
  

  P-6.32 给出一个完整的基于数组的双端队列ADT的队列实现方法

  
  class Empty(Exception):
      pass #占位语句
  class DeQueue:
      DEFAULT_CAPACITY=10
      def __init__(self):
          self._data=[None]*DeQueue.DEFAULT_CAPACITY
          self._size=0
          self._front=0
      def __len__(self):
          return self._size
      def is_empty(self):
          return self._size==0
      def add_first(self,e):
          if self._size == len(self._data):
              self._resize(2 * len(self._data))
          avail=(self._front-1)%len(self._data)
          self._data[avail]=e
          self._front = avail
          self._size+=1
      def add_last(self,e):
          if self._size == len(self._data):
              self._resize(2 * len(self._data))
          avail = (self._front +self._size) % len(self._data)
          self._data[avail] = e
          self._size += 1
      def delete_first(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          answer=self._data[self._front]
          self._data[self._front]=None
          self._front=(self._front+1)%len(self._data)
          self._size-=1
          return answer
      def delete_last(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          de=(self._front+self._size-1)%len(self._data)
          answer=self._data[de]
          self._data[de]=None
          self._size-=1
          return answer
      def first(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data[self._front]
      def last(self):
          if self.is_empty():
              raise Empty("Stack is empty")
          return self._data[(self._front+self._size-1)%len(self._data)]
      def _resize(self,cap):
          old=self._data
          self._data=[None]*cap
          walk=self._front
          for k in range(self._size):
              self._data[k]=old[walk]
              walk=(1+walk)%len(old)
          self._front=0
      def print_deque(self):
          print(self._data)
  Q=DeQueue()
  Q.add_first(1)
  Q.print_deque()
  Q.add_first(2)
  Q.print_deque()