You need find the correct order of the series b using Series.map. Finally replace using Series.replace:
df['b']=df['a'].map(pd.Series(df.index,df['b'].values)).replace(df['b'])
print(df)
a b
0 A A
1 B NaN
2 D D
3 C C
if you want to order following the dictionary you need to order first based on the column a using DataFrame.sort_values:
df=df.sort_values('a')
df['b']=df['a'].map(pd.Series(df.index,df['b'].values)).replace(df['b'])
print(df)
a b
0 A A
1 B NaN
3 C C
2 D D
Also you can use DataFrame.merge with sort = False:
new_df=df['a'].to_frame().merge(df['b'].to_frame(),left_on='a',right_on='b',how='outer',indicator=True,sort=False).query('_merge!="right_only"').drop('_merge',axis=1)
print(new_df)
a b
0 A A
1 B NaN
2 D D
3 C C
or with sort = True
new_df=df['a'].to_frame().merge(df['b'].to_frame(),left_on='a',right_on='b',how='outer',indicator=True).query('_merge!="right_only"').drop('_merge',axis=1)
print(new_df)
-----------------------
a b
0 A A
1 B NaN
2 C C
3 D D