CS 32, WINTER 2015, PRACTICE MIDTERM II.

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 32, WINTER 2015, PRACTICE MIDTERM II.


Problem #1: Stack is a LIFO (Last In First Out) container while Queue is a FIFO     (First In First Out) container. If you were given 2 sequence of numbers in which the first sequence of numbers are the numbers entering a mystery container, and the      second sequence of numbers are the numbers leaving a container, are you able to     determine whether that mystery container is a Stack, Queue, Might Be Either One,

or Neither?

For example, if you were given these two sequences:

1    2    3    // 1 entered the container first, then 2, and finally 3.

3    2    1    // 3 left the container first, then 2, and finally 1.

then that mystery container must be a Stack.

Implement the functions on the next page (which are called by the main routine on the page after that) so that this input:

the number of values in test case #1 the values entered into the containerfor test #1 the values leaving the containerfor test #1 the number of values in test case #2

etc.

1 2 3 4 5

7

1 2 3 4 3 2 1

1 2 3 4 3 2 1

4

1 3 4 2

1 4 2 3

produces this output:

This is a Stack!

This is a Queue!

Either a Stack or a Queue!

Neither a Stack nor a Queue!


#include

#include

usingnamespacestd;


boolisQueue(const vector& seq1, const vector& seq2)

{


}



boolisStack(const vector& seq1, const vector& seq2)

{


}


intmain()

{

intnumberOfValues;

while(cin>>numberOfValues) //leaveloopifthereisnonexttestcase {

vectorv1,v2;

for(inti=0;i<numberOfValues;i++){

intvalue;

cin>>value;

v1.push_back(value);

}

for(inti=0;i<numberOfValues;i++){

intvalue;

cin>>value;

v2.push_back(value);

}

bools=isStack(v1,v2);

boolq=isQueue(v1,v2);

if(s){

if(q)

cout<<"EitheraStackoraQueue!"<<endl;

else

cout<<"ThisisaStack!"<<endl;

}else{

if(q)

cout<<"ThisisaQueue!"<<endl;

else

cout<<"NeitheraStacknoraQueue!"<<endl;

}

}


Problem #2: Below is an implementation of a singly linked list with no dummy node.


#include

usingnamespacestd;

classLinkedList

{

public:

LinkedList():head(nullptr){}


~LinkedList();                       voidappend(intvalue);     voidprint()const;               voidprintReverse()const; voidreverse();

intsum()const;

private:

structNode


//appendvaluetothelist                                          //showtheitemsinthelist                                       // showtheitemsinthelistintheoppositeorder //changelistsoitemsareintheoppositeorder   //returnthesumofthevaluesinthelist


{

intnum;

Node*next;

};

Node*head; // thisistheonlydatamember;donotaddanyothers

voidprintReverseHelper(constNode*p)const;

Node*reverseHelper(Node*current,Node*previous);

IntsumHelper(constNode*p)const;

voidremoveNodes(Node*p);

};

intmain()

{

LinkedListlist;

cout<<list.sum()<<endl;                //writes0

intvalues[4]={30,10,40,20};

for(inti=1;i<=4;i++)

list.addToList(values[i]);


list.print();

cout<<list.sum()<<endl; list.printReverse();

list.print();

list.reverse();

list.print();

}


//writes //writes //writes //writes

30104020

100

20401030 30104020(listwasn’tchanged)

//thischangesthelist

//writes 20401030



voidLinkedList::append(intvalue)

{

Node*current=newNode;

current->num=value;

current->next=nullptr;

if(head==nullptr)

head=current;

else{

Node*ptr=head;

while(ptr->next!=nullptr)

ptr=ptr->next;

ptr->next=current;

}

}


voidLinkedList::print()const

{

for(constNode*ptr








2022-02-23