Open main menu

CDOT Wiki β

Q1 A linked list question

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