# Part1:回顾

## 2.堆栈(Stack)

``````# -*- coding: utf-8 -*-
"""
Created on Sat Mar 24 11:11:38 2018

"""

#实现栈
class Stack():
def __init__(self,size):
self.size=size
self.stack=[]
self.top=-1

def isfull(self):
return self.size==(self.top+1)

def push(self,x):
if self.isfull():
return 'stack is full'
else:
self.stack.append(x)
self.top+=1

def isempty(self):
return self.top==(-1)

def pop(self):
if self.isempty():
return 'stack is empty'
else:
self.top-=1
b=self.stack.pop()
return b

def show(self):
return self.stack

a=Stack(5)
print a.isfull()
print a.isempty()

a.push(4)
print a.show()

b=a.pop()
print a.show(),b``````

## 3.队列(Queue)

``````# -*- coding: utf-8 -*-
"""
Created on Sat Mar 24 12:15:02 2018

"""

class Queue():
def __init__(self,size):
self.size=size
self.queue=[]
self.front=0
self.rear=0

def isfull(self):
return self.size==(self.rear-self.front+1)

if self.isfull():
return 'queue is full'
else:
self.queue.append(x)
self.rear+=1

def isempty(self):
return self.front==self.rear

def deleteq(self):
if self.isempty():
return 'queue is empty'
else:
self.front+=1
b=self.queue.pop(0)
return b

def show(self):
return self.queue

q=Queue(10)
for i in range(5):
print q.show(),q.front,q.rear
for i in range(5):
print q.deleteq()
print q.show(),q.front,q.rear``````

# Part2:作业

• 作业1
• 一元多项式的乘法与加法运算

4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

``````# -*- coding: utf-8 -*-
"""
Created on Thu Mar 22 20:47:01 2018

"""

a=raw_input()
b=raw_input()

a=a.split(' ')
b=b.split(' ')

poly_1=[]
poly_2=[]

for i in a:
if i!=' ' and i!='':
poly_1.append(i)

for i in b:
if i!=' ' and i!='':
poly_2.append(i)

poly1=map(int,poly_1)
poly2=map(int,poly_2)

'''
poly1=[]
poly2=[]
'''
'''for i in poly_1:
if i!=' ':
poly1.append(i)

for i in poly_2:
if i!=' ':
poly2.append(i)'''

#读取每项对应的系数，要考虑常数项的情形
#a为次数，b为系数
if len(poly1)>1 and len(poly2)>1:
poly1_a=poly1[1::2]
poly1_b=poly1[2::2]
poly2_a=poly2[1::2]
poly2_b=poly2[2::2]
elif len(poly1)==1 and len(poly2)>1:
poly2_a=poly2[1::2]
poly2_b=poly2[2::2]
poly1_a=[0]
poly1_b=[0]
elif len(poly2)==1 and len(poly1)>1:
poly1_a=poly1[1::2]
poly1_b=poly1[2::2]
poly2_a=[0]
poly2_b=[0]
else:
poly2_a=[0]
poly2_b=[0]
poly1_a=[0]
poly1_b=[0]

def polyplus(poly1a,poly1b,poly2a,poly2b):
if poly1a[0]==0 and poly1b[0]==0:
return poly2a,poly2b
elif poly2a[0]==0 and poly2b[0]==0:
return poly1a,poly1b
else:
l1=len(poly1a)
l2=len(poly2a)

#polya表示系数，polyb表示指数
poly3a=[]
poly3b=[]

i=0
j=0
while(i<l1 and j<l2):
if poly1b[i]>poly2b[j]:
poly3b.append(poly1b[i])
poly3a.append(poly1a[i])
i+=1
elif poly1b[i]<poly2b[j]:
poly3b.append(poly2b[j])
poly3a.append(poly2a[j])
j+=1
else:
temp=poly2a[j]+poly1a[i]
if temp!=0:
poly3b.append(poly2b[j])
poly3a.append(temp)
i+=1
j+=1
if i==l1:
poly3b+=poly2b[j:]
poly3a+=poly2a[j:]
else:
poly3b+=poly1b[i:]
poly3a+=poly1a[i:]
if poly3a!=[] and poly3b!=[]:
return poly3a,poly3b
else:
return 0,0
#print poly3a,poly3b

def polymultiply(poly1a,poly1b,poly2a,poly2b):
if poly1a[0]==0 and poly1b[0]==0:
return 0,0
elif poly2a[0]==0 and poly2b[0]==0:
return 0,0
else:
l1=len(poly1a)
l2=len(poly2a)

poly3_a=map(lambda x:x*poly1a[0],poly2a)
poly3_b=map(lambda x:x+poly1b[0],poly2b)

i=1
while (i<l1):
tempa=map(lambda x:x*poly1a[i],poly2a)
tempb=map(lambda x:x+poly1b[i],poly2b)
poly3_a,poly3_b=polyplus(poly3_a,poly3_b,tempa,tempb)
i+=1
return poly3_a,poly3_b

p1,p2=polyplus(poly1_a,poly1_b,poly2_a,poly2_b)
m1,m2=polymultiply(poly1_a,poly1_b,poly2_a,poly2_b)
if m1==0 and m2==0:
print '0 0'
else:
leng=len(m1)
for i in range(leng):
if i<leng-1:
print m1[i],m2[i],
else:
print m1[i],m2[i]
if p1==0 and p2==0:
print '0 0'
else:
leng=len(p1)
for i in range(leng):
if i<leng-1:
print p1[i],p2[i],
else:
print p1[i],p2[i]``````

• 作业2

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10^5 ) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:
where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

``````# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 12:38:13 2018

@author: 715073608
"""

'''
00100 7 4
00000 4 99999
00100 1 12309
68237 6 -1
11111  8  44444
33218 3 00000
99999 5 68237
12309 2 33218
'''

##读取数据
a=raw_input('')
a=a.split(' ')

b=[]
for i in range(int(a[1])):
temp=raw_input('')
temp=temp.split(' ')
b.append(temp)

##按顺序重新排列
c=[]
pos=a[0]
for i in range(int(a[1])):
for j in b:
if j[0]==pos:
#c.append(i)
c.append(j[:-1])
pos=j[2]
break

##reverse数据
k=int(a[2])
m=len(c)
n=m/k

d=[]
for i in range(n):
temp=c[i*k:(i+1)*k][:]
temp.reverse()
d+=temp
d+=c[n*k:]

#输出结果
for i in range(m-1):
print d[i][0]+' '+d[i][1]+' '+d[i+1][0]
print d[-1][0]+' '+d[-1][1]+' '+'-1'``````
• 作业3
• Pop Sequence

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:
For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:
YES
NO
NO
YES
NO

``````# -*- coding: utf-8 -*-
"""
Created on Sat Mar 24 11:23:23 2018

"""

#定义栈
class Stack():
def __init__(self,size):
self.size=size
self.stack=[]
self.top=-1

def isfull(self):
return self.size==(self.top+1)

def push(self,x):
if self.isfull():
return 'stack is full'
else:
self.stack.append(x)
self.top+=1

def isempty(self):
return self.top==(-1)

def pop(self):
if self.isempty():
return 'stack is empty'
else:
self.top-=1
self.stack.pop()
#return b

def show(self):
return self.stack

#读取数据
a=raw_input()
b=map(int,a.split(' '))
c=[]

for i in range(b[2]):
temp=raw_input()
c.append(map(int,temp.split(' ')))

#思路是按照1到n输入，如果碰到栈尾的元素和给出的序列相同，则抛出这个元素，序列删除这个元素，以此循环

def isstack(x,size,num):
b=[]
a=Stack(size)
for i in range(1,num+1):
if not a.isfull():
a.push(i)
while not a.isempty() and a.show()[-1]==x[0]:
del x[0]
a.pop()
if len(a.show())==0:
print 'YES'
else:
print 'NO'

for i in c:
isstack(i,b[0],b[1])
'''
[1,2,3,4,5,6,7]
[3,2,1,7,5,6,4]
[7,6,5,4,3,2,1]
[5,6,4,3,7,2,1]
[1,7,6,5,4,3,2]
'''
'''
isstack([1,2,3,4,5,6,7],5,7)
isstack([3,2,1,7,5,6,4],5,7)
isstack([7,6,5,4,3,2,1],5,7)
isstack([5,6,4,3,7,2,1],5,7)
isstack([1,7,6,5,4,3,2],5,7)
'''
``````