2013年全国硕士研究生入学统一考试题2.一个栈的入栈序列为1,2,3，,n，其出栈序列是示例P1sP2P3Pn。若p2=3，则p,可能取值的个数是（）D.无法确定A.n-3B.n-2C.n-11进，1出，2进，3进，3出，2出，.4n栈P1P2P31进，2进，2出，3进，3出，1出，或者1P1P2P3或者1进，2进，2出，3进，3出，4进，4出，…，1出P1P2P3P3除了3外都可能！...11/101
示例 2.一个栈的入栈序列为1,2,3, .,n ，其出栈序列是 p1,p2,p3,.,pn。若p2=3，则p3可能取值的个数是（ ）。 A.n-3 B.n-2 C.n-1 D.无法确定 . 栈 1 p1 3 p2 2 p3 n, .,4 1进，1出，2进，3进，3出，2出， . 2 p1 3 p2 1 p3 或者 1进，2进，2出，3进，3出，1出， . 2 p1 3 p2 4 p3 或者 1进，2进，2出，3进，3出，4进，4出， . ，1出 p3除了3外都可能！ 11/101
栈的顺序存储结构及其基本运算算法实现3.1.2栈的实现方式逻辑结构U栈线性表映射链表顺序栈链栈顺序表存储结构12/101
栈的实现方式 线性表 顺序表 链表 栈 顺序栈 链栈 逻辑结构 存储结构 映射 ∩ 12/101
顺序栈top-→dUCtop→btopaa9Pe2-1.1-1-1top→>（a）空栈（b）元素a进栈(c）元素b、、d进栈（d）元素d出栈初始时置栈顶指针top=-1，顺序栈的四要素如下：栈空的条件为top==-1。栈满（栈上溢出）的条件为top==capacity-1，这里采用动态扩展容量的方式，即满时将data数组的容量扩大两倍。元素e进栈操作是先将栈顶指针top增1，然后将元素e放在栈顶指针处。出栈操作是先将栈顶指针top处的元素取出，然后将栈顶指针减1。13/101
4 3 2 1 0 （a）空栈 top -1 a （b）元素a进栈 4 3 2 1 0 -1 top d c b a （c）元素b、c、d进栈 4 3 2 1 0 -1 top c b a （d）元素d出栈 4 3 2 1 0 -1 top 初始时置栈顶指针top=-1，顺序栈的四要素如下： 栈空的条件为top==-1。 栈满（栈上溢出）的条件为top==capacity-1，这里采用动态扩展容 量的方式，即满时将data数组的容量扩大两倍。 元素e进栈操作是先将栈顶指针top增1，然后将元素e放在栈顶指针处。 出栈操作是先将栈顶指针top处的元素取出，然后将栈顶指针减1。 顺序栈 13/101
顺序栈泛型类Sgstackclass<E>//顺序栈泛型类publicclassSqstackclass<E>1/顺序栈的初始容量（常量）f final int initcapacity=io;//存放顺序栈的容量private int capacity;/存放顺序栈中元素private E[] data;1/存放栈顶指针private int top;//构造方法，实现data和size的初始化publicSqstackclass()//强制转换为E类型数组data = (E[])new object[initcapacity];capacity=initcapacity;top=-1;1/改变栈容量private void updatecapacity(int newcapacity){E[] newdata =(E[])newobject[newcapacity];//复制原来的元素for (int i=o;i<top;i++)newdata[i]=data[i];//设置新容量capacity=newcapacity;//仍由data标识数组data=newdata;子1/栈的基本运算算法宁14/101
public class SqStackClass<E> //顺序栈泛型类 { final int initcapacity=10; //顺序栈的初始容量(常量) private int capacity; //存放顺序栈的容量 private E[] data; //存放顺序栈中元素 private int top; //存放栈顶指针 public SqStackClass() //构造方法，实现data和size的初始化 { data = (E[])new Object[initcapacity]; //强制转换为E类型数组 capacity=initcapacity; top=-1; } private void updatecapacity(int newcapacity) //改变栈容量 { E[] newdata = (E[])new Object[newcapacity]; for (int i=0;i<top;i++) //复制原来的元素 newdata[i]=data[i]; capacity=newcapacity; //设置新容量 data=newdata; //仍由data标识数组 } //栈的基本运算算法 } 顺序栈泛型类SqStackClass<E> 14/101
顺序栈的基本运算算法（1）判断栈是否为空empty（）//判断栈是否为空public booleanempty()return top==-1;14Ytop-15/101
顺序栈的基本运算算法 public boolean empty() //判断栈是否为空 { return top==-1; } 4 3 2 1 0 top -1 15/101