a)试基于3.2.2节的列表模板类List，实现栈结构;b)按照你的实现方式，栈ADT各接口的效率如何？

编写程序，实现一个对象栈类，要求使用ArrayList类实现该栈，该栈类的UML图如图11-1所示。

阅读下列说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(Stock Top)，而另一端称为栈底(Stock Bottom)。栈的基本操作包括：创建栈(NewStack)、判断栈是否为空(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。

当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储(如下图所示)。

以下C代码采用链式存储结构实现一个整数栈操作。

【C代码】

typedef struct List {

int data； //栈数据

struct List* next； //上次入栈的数据地址

}List；

typedef struct Stack{

List* pTop； //当前栈顶指针

}Stack；

Stack* NewStack() {return (Stack*) calloc(1/sizeof(Stack))；}

int IsEmpty(Stack* S){//判断栈S是否为空栈

if((1))return 1;

return 0;

}

int Top(Stack* s){//获取栈顶数据。若栈为空，则返回机器可表示的最小整数

if(IsEmpty(S))return INT_ MIN；

return (2)；

}

void Push(Stack* S，int theData) {//将数据theData压栈

List* newNode；

newNode=(List*)calloc(1/sizeof (List))；

newNode-＞data=theData；

newNode-＞next=S-＞pTop；

S-＞pTop=(3)；

}

void Pop(Stack* S) {//弹栈

List* lastTop；

if(IsEmpty(S) ) return；

lastTop=S-＞pTop；

S-＞pTop=(4)；

free(lastTop)；

}

define MD(a) a＜＜2

int main(){

int i;

Stack* myStack；

myStack= NewStack()；

Push(myStack，MD(1))；

Push(myStack，MD(2))；

Pop(myStack)；

Push(myStack，MD(3)+1)；

while(!IsEmpty(myStack) ){

printf("%d"，Top(myStack))；

Pop(myStack)；

}

return 0；

}

以上程序运行时的输出结果为:(5)

实现先进先出的对象栈的类是()。

A．Thread类

B．Stack类

C．abstract类

D．Vector类

试题六（共 15分）

阅读以下说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明】

已知类 LinkedList 表示列表类，该类具有四个方法：addElement()、lastElement()、umberOfElement()以及removeLastElement()。四个方法的含义分别为：

void addElement(Object): 在列表尾部添加一个对象；

Object lastElement(): 返回列表尾部对象；

int numberOfElement(): 返回列表中对象个数；

void removeLastElement(): 删除列表尾部的对象。

现需要借助LinkedList来实现一个Stack栈类， Java代码1和Java代码2分别采用继承和组合的方式实现。

【Java代码1】

public class Stack extends LinkedList{

public void push(Object o){ //压栈

addElement(o);

}

public Object peek(){ //获取栈顶元素

return （1） ;

}

public boolean isEmpty(){ //判断栈是否为空

return numberOfElement() == 0;

}

public Object pop(){ //弹栈

Object o = lastElement();

（2） ;

return o;

}

}

【Java代码2】

public class Stack {

private （3） ;

public Stack(){

list = new LinkedList();

}

public void push(Object o){

list.addElement(o);

}

public Object peek(){//获取栈顶元素

return list. （4） ;

}

public boolean isEmpty(){//判断栈是否为空

return list.numberOfElement() == 0;

}

public Object pop(){ //弹栈

Object o = list.lastElement();

list.removeLastElement();

return o;

}

}

【问题】

若类LinkedList新增加了一个公有的方法removeElement(int index)，用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)？ （5） （A. 继承 B. 组合）

试题五（共 15分）

阅读以下说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明】

已知类 LinkedList 表示列表类，该类具有四个方法：addElement()、lastElement()、umberOfElement()以及removeLastElement()。四个方法的含义分别为：

void addElement(Object): 在列表尾部添加一个对象；

Object lastElement(): 返回列表尾部对象；

int numberOfElement(): 返回列表中对象个数；

void removeLastElement(): 删除列表尾部的对象。

现需要借助LinkedList来实现一个Stack栈类，C++代码1和C++代码2分别采用继承和组合的方式实现。

【C++代码 1】

class Stack :public LinkedList{

public:

void push(Object o){ addElement(o); }; //压栈

Object peek(){ return （1） ; }; //获取栈顶元素

bool isEmpty(){ //判断栈是否为空

return numberOfElement() == 0;

};

Object pop(){ //弹栈

Object o = lastElement();

（2） ;

return o;

};

};

【C++代码 2】

class Stack {

private:

（3） ;

public:

void push(Object o){ //压栈

list.addElement(o);

};

Object peek(){ //获取栈顶元素

return list. （4） ;

};

bool isEmpty(){ //判断栈是否为空

return list.numberOfElement() == 0;

};

Object pop(){//弹栈

Object o = list.lastElement();

list.removeLastElement();

return o;

};

};

【问题】

若类LinkedList新增加了一个公有的方法removeElement(int index)，用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)？ （5） （A. 继承 B. 组合）