Homework 11 -- Stacks & Queues

template <typename T>class Stack {  private:    class Node {      public:        T value;        Node* next;        Node(T v, Node* n = nullptr) : value(v), next(n) {}    };       Node* head;    public:    class EmptyException {};    Stack(): head(nullptr) {}    void push(T v);    T pop();    bool isEmpty();};

In this and the subsequent questions you will be asked to implement the various functions declared above. You will need to to write function templates that suitably implement these functions. For this assignment, you have to implement isEmpty. This is an easy question, you don’t have to write much. The template syntax is also provided for you. In the subsequent questions you will need to provide your own.

🔗

#include <sstream>

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

template <typename T>
class Stack {
  private:
    class Node {
      public:
        T value;
        Node* next;
        Node(T v, Node* n = nullptr) : value(v), next(n) {}
    };
   
    Node* head;  
  public:
    class EmptyException {};
    Stack(): head(nullptr) {}
    void push(T v);
    T pop();
    bool isEmpty();
};

template<typename T>
void Stack<T>::push(T v) {
    head = new Node(v, head);
}

template<typename T>
T Stack<T>::pop() {
    if (head == nullptr) throw EmptyException();
    T v = head->value;
    Node* oldHead = head;
    head = head->next;
    delete oldHead;
    return v;
}

^^^^
// Return value is true if and only if the stack is empty
template<typename T>
bool Stack<T>::isEmpty() { 
    
}

====
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

TEST_CASE( "test1" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("cat");
    mystack.push("dog");
    mystack.push("marmot");
    if (mystack.isEmpty())
        cout << "true";
    else
        cout << "false";
    
    ;
    std::string answer = "false";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test2" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    if (mystack.isEmpty())
        cout << "true";
    else
        cout << "false";
    
    ;
    std::string answer = "true";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test3" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("mouse");
    if (mystack.isEmpty())
        cout << "true";
    else
        cout << "false";
    
    ;
    std::string answer = "false";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test4" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("xerea");
    mystack.push("mr.gray");
    if (mystack.isEmpty())
        cout << "gotcha";
    else
        cout << "good job";
    
    ;
    std::string answer = "good job";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test5" ) {
    std::stringstream cout;
    Stack<int> mystack;
    if (mystack.isEmpty())
        cout << "yeppers";
    else
        cout << "false";
    
    ;
    std::string answer = "yeppers";
    CHECK( cout.str() == answer );
}

🔗

9.

A stack class template is provided for you, with the following definition:

🔗

template <typename T>class Stack {  private:    class Node {      public:        T value;        Node* next;        Node(T v, Node* n = nullptr) : value(v), next(n) {}    };       Node* head;    public:    class EmptyException {};    Stack(): head(nullptr) {}    void push(const T& v);    T pop();    bool isEmpty() const;};

For this question, you have to implement push.

🔗

#include <sstream>

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

template<typename T>
class Stack; // forward declare to make function declaration possible
 
template<typename T> // declaration
std::ostream& operator<<(std::ostream&, const Stack<T>&);

template <typename T>
class Stack {
  private:
    class Node {
      public:
        T value;
        Node* next;
        Node(const T& v, Node* n = nullptr) : value(v), next(n) {}
    };
   
    Node* head;  
  public:
    class EmptyException {};
    Stack(): head(nullptr) {}
    void push(const T& v);
    T pop();
    bool isEmpty() const;
    friend std::ostream& operator<< <>(std::ostream& out, const Stack<T>& stack);
};

template<typename T>
T Stack<T>::pop() {
    if (head == nullptr) throw EmptyException();
    T v = head->value;
    Node* oldHead = head;
    head = head->next;
    delete oldHead;
    return v;
}

template<typename T>
bool Stack<T>::isEmpty() const { return head == nullptr; }

template<typename T>
std::ostream& operator<<(std::ostream& out, const Stack<T>& st) {
    typename Stack<T>::Node * curr = st.head;
    while (curr != nullptr) {
        out << curr->value;
        curr = curr->next;
        if (curr == nullptr) break;
        else out << "  ,  ";
    }
    return out;
}

^^^^
// push
// Postcondition: A new copy of entry has been pushed onto the stack.

====
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

TEST_CASE( "test1" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("mouse");
    cout << mystack;
    
    ;
    std::string answer = "mouse";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test2" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("platypus");
    mystack.push("emu");
    cout << mystack;
    
    
    ;
    std::string answer = "emu  ,  platypus\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test3" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("cat");
    mystack.push("dog");
    mystack.push("marmot");
    cout << mystack;
    
    ;
    std::string answer = "marmot  ,  dog  ,  cat\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test4" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("cat");
    mystack.push("dog");
    mystack.push("marmot");
    mystack.push("bunny rabbit");
    cout << mystack;
    
    ;
    std::string answer = "bunny rabbit  ,  marmot  ,  dog  ,  cat\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test5" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("monkey");
    cout << mystack;
    
    ;
    std::string answer = "monkey";
    CHECK( cout.str() == answer );
}

🔗

10.

A stack class template is provided for you, with the following definition:

🔗

template <typename T>class Stack {  private:    class Node {      public:        T value;        Node* next;        Node(T v, Node* n = nullptr) : value(v), next(n) {}    };       Node* head;    public:    class EmptyException {};    Stack(): head(nullptr) {}    void push(const T& v);    T pop();    bool isEmpty() const;};

For this question, you have to implement pop.

🔗

#include <sstream>

#include <iostream>
#include <string>
#include <sstream>

template<typename T>
class Stack; // forward declare to make function declaration possible
 
template<typename T> // declaration
std::ostream& operator<<(std::ostream&, const Stack<T>&);

template <typename T>
class Stack {
  private:
    class Node {
      public:
        T value;
        Node* next;
        Node(const T& v, Node* n = nullptr) : value(v), next(n) {}
    };
   
    Node* head;  
  public:
    class EmptyException {};
    Stack(): head(nullptr) {}
    void push(const T& v);
    T pop();
    bool isEmpty() const;
    friend std::ostream& operator<< <>(std::ostream& out, const Stack<T>& stack);
};

template<typename T>
void Stack<T>::push(const T& v) {
    head = new Node(v, head);
}

template<typename T>
bool Stack<T>::isEmpty() const { return head == nullptr; }

template<typename T>
std::ostream& operator<<(std::ostream& out, const Stack<T>& st) {
    typename Stack<T>::Node * curr = st.head;
    while (curr != nullptr) {
        out << curr->value;
        curr = curr->next;
        if (curr == nullptr) break;
        else out << "  ,  ";
    }
    return out;
}

^^^^
// pop
// Postcondition: If the stack was non-empty, the top item of the stack has been removed
// Postcondition: If the stack was empty an exception has been thrown.

====
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

TEST_CASE( "test1" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("mouse");
    std::cout << "Before: " << mystack << std::endl;
    mystack.pop();
    std::cout << "After: " << mystack << std::endl;
    if (! mystack.isEmpty()) std::cout << "pop error";
    
    
    ;
    std::string answer = "Before: mouse\nAfter:\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test2" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("platypus");
    mystack.push("emu");
    std::cout << "Before: " << mystack << std::endl;
    mystack.pop();
    std::cout << "After: " << mystack << std::endl;
    mystack.pop();
    if (! mystack.isEmpty()) std::cout << "pop error";
    
    
    ;
    std::string answer = "Before: emu  ,  platypus\nAfter: platypus\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test3" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("cat");
    mystack.push("dog");
    mystack.push("marmot");
    std::cout << "Before: " << mystack << std::endl;
    mystack.pop();
    std::cout << "After: " << mystack << std::endl;
    mystack.pop();
    std::cout << "After: " << mystack << std::endl;
    mystack.pop();
    if (! mystack.isEmpty()) std::cout << "pop error";
    
    
    ;
    std::string answer = "Before: marmot  ,  dog  ,  cat\nAfter: dog  ,  cat\nAfter: cat\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test4" ) {
    std::stringstream cout;
    Stack<std::string> mystack;
    mystack.push("elephant");
    mystack.push("zebra");
    std::cout << "Before: " << mystack << std::endl;
    mystack.pop();
    std::cout << "After: " << mystack << std::endl;
    mystack.pop();
    if (! mystack.isEmpty()) std::cout << "pop error";
    
    
    ;
    std::string answer = "Before: zebra  ,  elephant\nAfter: elephant\n";
    CHECK( cout.str() == answer );
}

🔗

11.

A queue class template is provided for you, with the following definition:

🔗

};

This implementation uses a linked list with two pointers, one pointing to the head node and another pointing to the tail node. You can enqueue new values by placing them at the tail and advancing the tail pointer, and you can dequeue values by taking them out of the head and advancing the head pointer. As a result, the values in the linked list are stored effectively in opposite order, with newly inserted elements at the tail.

🔗

For this question, you have to implement the function enqueue. It must place a new node with the provided value at the tail of the list (and you can use the tail pointer to get to that location directly, then adjust the tail pointer). You must be careful for the special case where the list is empty.

🔗

#include <sstream>

#include <iostream>
#include <string>
#include <sstream>

template<typename T>
class Queue; // forward declare to make function declaration possible
 
template<typename T> // declaration
std::ostream& operator<<(std::ostream&, const Queue<T>&);

template <typename T>
class Queue {
  private:
    class Node {
      public:
        T value;
        Node* next;
        Node(const T& v, Node* n = nullptr) : value(v), next(n) {}
    };
   
  public:
    Node* head;  
    Node* tail;
    class EmptyException {};
    Queue(): head(nullptr), tail(nullptr) {}
    void enqueue(const T& v);
    T dequeue();
    bool isEmpty() const;
    friend std::ostream& operator<< <>(std::ostream& out, const Queue<T>& queue);
};

template<typename T>
T Queue<T>::dequeue() {
    if (head == nullptr) throw EmptyException();
    T v = head->value;
    Node* oldHead = head;
    head = head->next;
    delete oldHead;
    if (head == nullptr) tail = nullptr;
    return v;
}

template<typename T>
bool Queue<T>::isEmpty() const { return head == nullptr; }

template<typename T>
std::ostream& operator<<(std::ostream& out, const Queue<T>& st) {
    typename Queue<T>::Node * curr = st.head;
    while (curr != nullptr) {
        out << curr->value;
        curr = curr->next;
        if (curr == nullptr) break;
        else out << "  ,  ";
    }
    return out;
}

^^^^
template<typename T>
void Queue<T>::enqueue(const T& v) {
    
}

====
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

TEST_CASE( "test1" ) {
    std::stringstream cout;
    Queue<std::string> queue;
    queue.enqueue("mouse");
    std::cout << "List: " << queue << std::endl;
    std::cout << "Head: " << queue.head->value << std::endl;
    std::cout << "Tail: " << queue.tail->value << std::endl;
    
    
    ;
    std::string answer = "List: mouse\nHead: mouse\nTail: mouse\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test2" ) {
    std::stringstream cout;
    Queue<std::string> queue;
    queue.enqueue("mouse");
    queue.enqueue("danger");
    std::cout << "List: " << queue << std::endl;
    std::cout << "Head: " << queue.head->value << std::endl;
    std::cout << "Tail: " << queue.tail->value << std::endl;
    
    
    ;
    std::string answer = "List: mouse  ,  danger\nHead: mouse\nTail: danger\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test3" ) {
    std::stringstream cout;
    Queue<std::string> queue;
    queue.enqueue("mouse");
    queue.enqueue("danger");
    queue.enqueue("will robinson");
    std::cout << "List: " << queue << std::endl;
    std::cout << "Head: " << queue.head->value << std::endl;
    std::cout << "Tail: " << queue.tail->value << std::endl;
    
    
    ;
    std::string answer = "List: mouse  ,  danger  ,  will robinson\nHead: mouse\nTail: will robinson\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test4" ) {
    std::stringstream cout;
    Queue<int> queue;
    queue.enqueue(3);
    queue.enqueue(2);
    queue.enqueue(1);
    std::cout << "List: " << queue << std::endl;
    std::cout << "Head: " << queue.head->value << std::endl;
    std::cout << "Tail: " << queue.tail->value << std::endl;
    
    
    ;
    std::string answer = "List: 3  ,  2  ,  1\nHead: 3\nTail: 1\n";
    CHECK( cout.str() == answer );
}

🔗

12.

A queue class template is provided for you, with the following definition:

🔗

};

This implementation uses a linked list with two pointers, one pointing to the head node and another pointing to the tail node. You can enqueue new values by placing them at the tail and advancing the tail pointer, and you can dequeue values by taking them out of the head and advancing the head pointer. As a result, the values in the linked list are stored effectively in opposite order, with newly inserted elements at the tail.

🔗

For this question, you have to implement the function dequeue. It must throw an error in the case of an empty list, and otherwise it must remove and return the next appropriate value, in a FIFO form. You must be careful for the special case where the list will be empty after the removal.

🔗

#include <sstream>

#include <iostream>
#include <string>
#include <sstream>

template<typename T>
class Queue; // forward declare to make function declaration possible
 
template<typename T> // declaration
std::ostream& operator<<(std::ostream&, const Queue<T>&);

template <typename T>
class Queue {
  private:
    class Node {
      public:
        T value;
        Node* next;
        Node(const T& v, Node* n = nullptr) : value(v), next(n) {}
    };
   
  public:
    Node* head;  
    Node* tail;
    class EmptyException {};
    Queue(): head(nullptr), tail(nullptr) {}
    void enqueue(const T& v);
    T dequeue();
    bool isEmpty() const;
    friend std::ostream& operator<< <>(std::ostream& out, const Queue<T>& queue);
};

template<typename T>
void Queue<T>::enqueue(const T& v) {
    if (tail == nullptr) {
      tail = new Node(v);
      head = tail;
    } else {
      tail->next = new Node(v);
      tail = tail->next;
    }
}

template<typename T>
bool Queue<T>::isEmpty() const { return head == nullptr; }

template<typename T>
std::ostream& operator<<(std::ostream& out, const Queue<T>& st) {
    typename Queue<T>::Node * curr = st.head;
    while (curr != nullptr) {
        out << curr->value;
        curr = curr->next;
        if (curr == nullptr) break;
        else out << "  ,  ";
    }
    return out;
}

^^^^
template<typename T>
T Queue<T>::dequeue() {

}

====
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

TEST_CASE( "test1" ) {
    std::stringstream cout;
    Queue<std::string> queue;
    queue.enqueue("mouse");
    queue.enqueue("danger");
    queue.enqueue("will robinson");
    std::cout << "Initial List: " << queue << std::endl;
    std::cout << "Dequeue result: " << queue.dequeue() << std::endl;
    std::cout << "New List: " << queue << std::endl;
    std::cout << "Head: " << queue.head->value << std::endl;
    std::cout << "Tail: " << queue.tail->value << std::endl;
    
    
    ;
    std::string answer = "Initial List: mouse  ,  danger  ,  will robinson\nDequeue result: mouse\nNew List: danger  ,  will robinson\nHead: danger\nTail: will robinson\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test2" ) {
    std::stringstream cout;
    Queue<std::string> queue;
    queue.enqueue("mouse");
    queue.enqueue("danger");
    std::cout << "Initial List: " << queue << std::endl;
    std::cout << "Dequeue result: " << queue.dequeue() << std::endl;
    std::cout << "New List: " << queue << std::endl;
    std::cout << "Head: " << queue.head->value << std::endl;
    std::cout << "Tail: " << queue.tail->value << std::endl;
    
    
    ;
    std::string answer = "Initial List: mouse  ,  danger\nDequeue result: mouse\nNew List: danger\nHead: danger\nTail: danger\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test3" ) {
    std::stringstream cout;
    Queue<std::string> queue;
    queue.enqueue("mouse");
    std::cout << "Initial List: " << queue << std::endl;
    std::cout << "Dequeue result: " << queue.dequeue() << std::endl;
    std::cout << "New List: " << queue << std::endl;
    std::cout << "Head: " << (queue.head == nullptr ? "null" : queue.head->value) << std::endl;
    std::cout << "Tail: " << (queue.tail == nullptr ? "null" : queue.tail->value) << std::endl;
    
    
    ;
    std::string answer = "Initial List: mouse\nDequeue result: mouse\nNew List:\nHead: null\nTail: null\n";
    CHECK( cout.str() == answer );
}

TEST_CASE( "test4" ) {
    std::stringstream cout;
    Queue<int> queue;
    std::cout << "Removing from empty list should throw exception: ";
    try {
       queue.dequeue();
       std::cout << "FAILED!\n";
    } catch (Queue<int>::EmptyException e) {
       std::cout << "YES!\n";
    }
    
    
    ;
    std::string answer = "Removing from empty list should throw exception: YES!\n";
    CHECK( cout.str() == answer );
}

🔗

CS223 Exercises

Section 1.11 Homework 11 -- Stacks & Queues

Exercises Exercises

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.