| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10997 | Queue |
|
| 11010 | List class |
|
Description
A queue is an abstract data type that serves as a collection of elements, where nodes are removed only from the head of the queue and are inserted only at the tail of the queue. Two principal operations can be used to manipulate a queue: enqueue, which inserts an element at the tail, and dequeue, which removes the element at the head of the collection.
Let’s see how the queue data structure can be realized in C++.We have an approach to implement queue: linked list. Thus, we define a class as follows:
class List_queue {
public:
List_queue();
~List_queue();
void enqueue(const int &);
void dequeue();
void print();
private:
ListNode *head;
ListNode *tail;
};
where List_queue implements the queue data structure.
REQUIREMENTS:
Implement the constructor, destructor, enqueue(), dequeue() and print() member functions of the List_queue class.
Note:
1.This problem involves three files.
- function.h: Class definitions.
- function.cpp: Member-function definitions.
- main.cpp: A driver program to test your class implementation.
You will be provided with main.cpp and function.h, and asked to implement function.cpp.
function.h
main.cpp
2.For OJ submission:
Step 1. Submit only your function.cpp into the submission block.
Step 2. Check the results and debug your program if necessary.
Input
There are three kinds of commands:
- “enqueue integerA” represents inserting an element with int value A at the tail of the queue.
- “dequeue” represents removing the element at the head of the queue.
- “print” represents showing the current content of the queue.
Each command is followed by a new line character.
Input terminated by EOF.
Output
The output should consist of the current state of the queue.
When the queue is empty, you don’t need to print anything except a new line character.
Sample Input Download
Sample Output Download
Partial Judge Code
10997.cppPartial Judge Header
10997.hTags
Discuss
Description
Let’s implement a list class.
- Task 1:
First you are asked to implement class OWList (standing for “one-way list”). You have definitions of classes ListNode and OWList as follows:
class ListNode
{
friend class OWList; //make OWList a friend
friend class TWList; //make TWList a friend
public:
ListNode( const int &info ) //constructor
: data( info ), nextPtr( NULL )
{
} //end ListNode constructor
private:
int data; //data
ListNode *nextPtr; // next node in list
}; //end class ListNode
class OWList
{
public:
//default constructor
OWList();
//destructor
~OWList();
//insert node at front of list
void insertAtFront( const int &value );
//remove node from front of list
void removeFromFront();
//is List empty?
bool isEmpty() const;
//display contents of List
void print() const;
protected:
ListNode *firstPtr; //pointer to first node
ListNode *lastPtr; //pointer to last node
}; // end class OWList
Requirement: Implement the member functions
1. “OWList::OWList();”: initializes the two pointers firstPtr and lastPtr as NULL.
2. “OWList::~OWList();”: deletes allocated dynamic memory space.
3. “void OWList::insertAtFront( const int &value );”
4. “int OWList::removeFromFront();”
5. “bool OWList::isEmpty() const;”
6. “void OWList::print() const;”
- Task 2:
Implement another class TWList (standing for “two-way list”), which is derived from class OWList:
class TWList:public OWList
{
public:
//default constructor
TWList()
:OWList()
{
/*It will still work correctly if you omit the constructor call of the base class in the above member initializer list. The compiler will invoke this default constructor of OWList implicitly.*/
}
//destructor
~TWList()
{
/*You don't need to delete the list again because the
compiler will invoke the destructor of the base class OWList to do this.*/
}
//insert node at back of list
void insertAtBack( const int &value );
//delete node from back of list
void removeFromBack();
};
Besides the functions inherited from OWList, TWList has two more functions: insert a node at the end of the list and remove a node from the end of the list.
Requirement: Implement the member functions
7. “void TWList:: insertAtBack( const int &value );”
8.“int TWList:: removeFromBack();”
Note:
1. This problem involves three files.
- function.h: Class definitions.
- function.cpp: Member-function definitions.
- main.cpp: A driver program to test your class implementation.
You will be provided with main.cpp and function.h, and asked to implement function.cpp.
#ifndef FUNCTION_H
#define FUNCTION_H
#include <iostream>
class ListNode
{
friend class OWList; //make OWList a friend
friend class TWList; //make TWList a friend
public:
ListNode( const int &info ) //constructor
: data( info ), nextPtr( NULL )
{
} //end ListNode constructor
private:
int data; //data
ListNode *nextPtr; // next node in list
}; //end class ListNode
class OWList
{
public:
//default constructor
OWList();
//destructor
~OWList();
//insert node at front of list
void insertAtFront( const int &value );
//remove node from front of list
void removeFromFront();
//is List empty?
bool isEmpty() const;
//display contents of List
void print() const;
protected:
ListNode *firstPtr; //pointer to first node
ListNode *lastPtr; //pointer to last node
}; // end class OWList
class TWList:public OWList
{
public:
//default constructor
TWList()
:OWList()
{
/*It will still work correctly if you omit the constructor call of the base
class in the above member initializer list. The compiler will invoke this
default constructor of OWList implicitly.*/
}
//destructor
~TWList()
{
/*You don't need to delete the list again because the compiler
will invoke the destructor of the base class OWList to do this.*/
}
//insert node at back of list
void insertAtBack( const int &value );
//delete node from back of list
void removeFromBack();
};
#endif
#include <iostream>
#include <string>
#include "function.h"
using namespace std;
int main()
{
TWList integerList;
int command;
int value; // store node value
while (cin >> command)
{
switch(command)
{
case 1: // insert at beginning
cin >> value;
integerList.insertAtFront(value);
break;
case 2: // insert at end
cin >> value;
integerList.insertAtBack(value);
break;
case 3: // remove from beginning
integerList.removeFromFront();
break;
case 4: // remove from end
integerList.removeFromBack();
break;
}
}
integerList.print();
cout<<endl;
}
2. For OJ submission:
Step 1. Submit only your function.cpp into the submission block.
Step 2. Check the results and debug your program if necessary.
Input
There are four types of command:
- “1 integerA” represents inserting a node with int value A at the head of the list.
- “2 integerB” represents inserting a node with int value B at the end of the list.
- “3” represents removing the node at the head of the list
- “4” represents removing the node at the end of the list
Each command is followed by a new line character.
Input terminated by EOF.
Output
The output should consist of the final state of the list.