1. 一个列表实现两个栈
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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. 两个栈实现一个队列
有两个栈s1，s2。入队时，将元素压入s1。出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
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. 两个队列实现一个栈
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
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)
|