【正确答案】(1)必要性：用反证法证明。
   假如存在i，j，k，使i＜j＜k与p_j＜p_k＜p_i同时成立，则有：
   ①由于i＜j＜k，三元素出栈的相对次序应为p_i，p_j，p_k。
   ②因为p_j＜p_k＜p_i，所以入栈的相对次序为p_j，p_k，p_i
   根据②，当P_i入栈时，如果p_j和p_k都在栈中，p_j必在p_k之下。所以出栈的相对次序只能为p_i，p_k，p_j。故与①矛盾。
   (2)充分性
   设序列p₁，p₂，…，p_n符合条件，则我们可以用下述方法逐个地使p_i(j=1，2，…，n)加入该序列。
   情况1：若p_j在输入序列的剩余部分(假设1，2，…，i-1已经输入)i，i+1，…，n中，则把p_j之前的元素及p_j进栈，然后把p_j从栈中取出送入序列。
   情况2：若p_j已经在栈中，则它必然在栈顶(这是因为栈中元素在任何时刻显然都是从顶向下递减的，而刚离栈的p_j-1大于栈中的所有元素。假如p_j不在栈顶，设栈顶元素是p_k，我们有j-1＜j＜k，而p_j-1＞p_k＞p_i。与已知条件矛盾。)把栈顶元素取出送入序列。
   重复上述步骤，可得到所要求的序列。充分性得证。