|
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 |
有两个栈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() |
|
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) |
原文：http://www.cnblogs.com/linxiyue/p/3562030.html