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
{
}
boolisStack(const vector
{
}
intmain()
{
intnumberOfValues;
while(cin>>numberOfValues) //leaveloopifthereisnonexttestcase {
vector
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