CS111 C++ Practice Quiz #6

Stacks and Queues



  1. A is a data structure that uses the First In First Out protocol.

  2. A is a data structure that uses the Last In First Out protocol.

  3. List the five most essential member functions of the stack class.






  4. List the six most essential member functions of the queue class.






  5. Describe "prefix", "infix", and "postfix" notation. Give examples of each.





  6. What output is displayed after the following segment of code executes:
    stack <int> s;
    int a = 22, b = 44;
    s.push(2);
    s.push(a);
    s.push(a + b);
    b = s.top();
    s.pop();
    s.push(b);
    s.push(a - b);
    s.pop();
    while (!s.empty()) {
      cout << s.top() << endl;
      s.pop();
    }


  7. What output is displayed after the following segment of code executes:
    stack <int> s;
    for (int i = 1; i <= 10; i++)
      s.push(i);

    while (!s.empty())
      cout << s.top() << endl;



  8. What output is displayed after the following segment of code executes:
    stack <int> s;
    for (int i = 1; i <= 10; i++)
      s.push(i);

    while (!s.empty()){
      cout << s.top() << endl;
      s.pop();
    }


  9. The program contains a function Template void print to display the contents of a given queue. The reason for using this template is so that the data type - class T - of the queue is generic.
    What output is displayed after the program executes?
    #include <iostream>
    #include <string>
    #include <queue>
    using namespace std;

    template <class T> void print(const queue <T> &q);

    int main() {
      queue <string> q;
      print (q);
      q.push("Bobo");
      print (q);
      q.push("Billy");
      print (q);
      q.push("Suzy");
      print (q);
      q.pop();
      print (q);
      q.push("Ari");
      print (q);
      q.pop();
      print (q);
      return 0;
    }

    template <class T> void print(const queue <T> &q){
      queue <T> qq = q;
      while (!qq.empty()) {
        cout << qq.front() << endl;
        qq.pop();
      }
    }



Answers
  1. Queue

  2. Stack





  6. 66
    22
    2

  7. 10 an infinite number of times. top() simply copies the top element of the stack.
    Use push() to remove an element from the stack.

  8. 10
    9
    8
    7
    6
    5
    4
    3
    2
    1


  9. Bobo
    Bobo
    Billy
    Bobo
    Billy
    Suzy
    Billy
    Suzy
    Billy
    Suzy
    Ari
    Suzy
    Ari