Difference between revisions of "Q1 A linked list question"
(Created page with '<p>In this question, you must use a linked list like structure to implement the object. If you use an array or even a dynamic array, no marks will be awarded. <p>Write a templa…') |
|||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
− | + | In this question, you must use a linked list like structure to implement the object. If you use an array or even a dynamic array, no marks will be awarded.<br> | |
− | + | Write a template class Stack<T> where T is any data type that can be constructed without any arguments and can be copied using the assignment operator. You can also pass any instance of T into a function by value.<br> | |
− | + | A stack is a data structure that is LIFO. In other words, the last thing added will be the first thing removed. (see sample main)<br> | |
− | + | When a Stack is first instantiated, it is empty.<br> | |
− | + | A Stack has the following public member functions:<br> | |
− | '''isempty''' - this function takes no arguments and returns a bool. If the stack is empty, return true, otherwise return false | + | '''isempty''' - this function takes no arguments and returns a bool. If the stack is empty, return true, otherwise return false<br> |
− | '''push '''- this function takes an instance of the unknown data type T as its only parameter and returns nothing. It will put the data onto the stack. | + | '''push '''- this function takes an instance of the unknown data type T as its only parameter and returns nothing. It will put the data onto the stack.<br> |
− | pop - this function takes no arguments and returns an instance of the unknown data type T. It will remove and return the last piece of data that was added. If the stack isempty when this function is called, the function should throw the string "empty stack" as an exception. | + | '''pop''' - this function takes no arguments and returns an instance of the unknown data type T. It will remove and return the last piece of data that was added. If the stack isempty when this function is called, the function should throw the string "empty stack" as an exception.<br> |
Sample main: | Sample main: | ||
− | + | <source lang="cpp"> | |
int main(void){ | int main(void){ | ||
Stack<int> IS; //integer stack | Stack<int> IS; //integer stack | ||
Line 34: | Line 34: | ||
catch(char* s){ cout << s << endl;} //empty stack | catch(char* s){ cout << s << endl;} //empty stack | ||
} | } | ||
+ | </source> | ||
Hint: think of push as inserting to front of linked list and pop as removing from front of linked list | Hint: think of push as inserting to front of linked list and pop as removing from front of linked list |
Latest revision as of 17:33, 4 August 2010
In this question, you must use a linked list like structure to implement the object. If you use an array or even a dynamic array, no marks will be awarded.
Write a template class Stack<T> where T is any data type that can be constructed without any arguments and can be copied using the assignment operator. You can also pass any instance of T into a function by value.
A stack is a data structure that is LIFO. In other words, the last thing added will be the first thing removed. (see sample main)
When a Stack is first instantiated, it is empty.
A Stack has the following public member functions:
isempty - this function takes no arguments and returns a bool. If the stack is empty, return true, otherwise return false
push - this function takes an instance of the unknown data type T as its only parameter and returns nothing. It will put the data onto the stack.
pop - this function takes no arguments and returns an instance of the unknown data type T. It will remove and return the last piece of data that was added. If the stack isempty when this function is called, the function should throw the string "empty stack" as an exception.
Sample main:
int main(void){
Stack<int> IS; //integer stack
IS.push(5); //stack: 5 (value on top of stack is underlined)
IS.push(10); //stack: 10, 5
IS.push(3); //stack: 3, 10, 5
cout << IS.pop() << endl; //prints: 3 --> stack is now: 10, 5
IS.push(4); //stack is: 4, 10, 5
cout << IS.pop() << endl; //prints 4 --> stack is now: 10, 5
cout << IS.pop() << endl; //prints 10 --> stack is now: 5
cout << IS.pop() << endl; //prints 5 --> stack is now empty
try{ cout << IS.pop() << endl; } //this try/catch prints:
catch(char* s){ cout << s << endl;} //empty stack
}
Hint: think of push as inserting to front of linked list and pop as removing from front of linked list