stackLL.hpp

#ifndef STACKLL_HPP #define STACKLL_HPP

class StackLL { private: struct Node { char key; Node *next; };

// pocharer to item to be popped next Node* stackHead;

public: StackLL(); ~StackLL(); bool isEmpty(); void push(char key); void pop(); char peek(); };

#endif -----------------------------------------

stackLL.cpp

#include #include "StackLL.hpp"

using namespace std;

StackLL::StackLL() { stackHead = nullptr; }

StackLL::~StackLL() { while(!isEmpty()) pop(); }

bool StackLL::isEmpty() { return (stackHead == nullptr); }

void StackLL::push(char key) { Node* nn = new Node; nn->key = key; nn->next = nullptr; nn->next = stackHead; stackHead = nn; }

void StackLL::pop() { if(!isEmpty()) { Node* temp = stackHead; stackHead = stackHead->next; delete temp; } else { cout

char StackLL::peek() { if(!isEmpty()) return stackHead->key; else{ cout

QueueLL.hpp

#ifndef QUEUELL_HPP #define QUEUELL_HPP

#include

class QueueLL { private: struct Node { int key; Node *next; };

// item in list to be dequeued next Node* queueFront; // item in list that was most recently enqueued Node* queueEnd;

public: QueueLL(); ~QueueLL(); bool isEmpty(); void enqueue(int key); void dequeue(); int peek(); };

#endif

-------------------------------------------------

QueueLL.cpp

#include #include "QueueLL.hpp"

using namespace std;

QueueLL::QueueLL() { queueFront = nullptr; queueEnd = nullptr; }

QueueLL::~QueueLL() { while( !isEmpty() ) dequeue(); }

bool QueueLL::isEmpty() { /*if(queueFront == nullptr || queueEnd == nullptr) return true; return false;*/ return (!queueFront || !queueEnd); }

// TODO void QueueLL::enqueue(int key) { Node *nn = new Node; nn->key = key; nn->next = nullptr;

// TODO Complete this function, handle the case when you're enqueuing in an empty queue }

//TODO void QueueLL::dequeue() { if(!isEmpty()) { // TODO Complete this function, handle the case when your queue becomes empty after dequeuing } else{ cout

int QueueLL::peek() { if( !isEmpty() ) return queueFront->key; else { cout

DriverStack.cpp

#include #include "StackLL.hpp"

using namespace std;

// TODO GOLD - Complete the TODOs in this function bool isValid(string input) { StackLL stack; char x;

// Traversing the input for (int i=0; i

// If it is not an opening bracket, then the stack shouldn't be empty if (stack.isEmpty()) return false;

//Switch cases for the closing brackets switch (input[i]) { case ')':

// TODO first peek and then pop from stack // if the popped character is the matching starting bracket then fine else parenthesis are not balanced

break;

case '}':

// TODO Complete this section (similar to the case above) break;

case ']':

// TODO Complete this section (similar to the case above) break; }

} // If stack is not empty, there are unmatched brackets return (stack.isEmpty());

} int main() { int choice; while(1) { cout

cout > choice; cout

cout > input; if (isValid(input)) cout

}

----------------------------------------------------

DriverQueue.cpp

#include #include "QueueLL.hpp" using namespace std;

int main() { // test queues QueueLL queue;

// TC1: queue empty after created? cout

// TC2: Push items // TODO SILVER - Complete your enqueue function cout

// TC3: Queue not empty after pushing items cout

// TC4: peek cout

// TC5: pop items // TODO SILVER - Complete your dequeue function cout

return 0; }

Download the Lab6 zipped file from moodle. This file consists of header files and function implementations of both Stacks and Queues. Your task is to complete the following function/functions: 1. Complete the enqueue and dequeue operations of a queue. After completing these functions in QueueLL.cpp, run the DriverQueue.cpp to check if they are working correctly (Silver problem - Mandatory ) 2. Check if parentheses is balanced in an input string in DriverStack.cpp (Gold problem)