Difference between revisions of "Q1 A linked list question"

From CDOT Wiki
Jump to: navigation, search
(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:
<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.
+
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>
  
<p>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.
+
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>
  
<p>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)
+
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>
  
<p>When a Stack is first instantiated, it is empty.
+
When a Stack is first instantiated, it is empty.<br>
  
<p>A Stack has the following public member functions:
+
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