Question

Review the Stack implementation with Vector, and implement/answer the following methods.

Stack One of the principles of good programming is to reuse existing code whenever practical. If you can reuse existing code, you don't need to spend the time to rewrite it. Code used previously has also been debugged, and will likely contain fewer errors. One of the easiest ways to create a container is to leverage an existing data type to build a new abstraction. In this lesson we will illustrate this process by building a Stack that will use a Vector to store values as shown in the header: template <typename T> class miniStack public: // constructor. create an empty stack miniStack(); // push (insert) item onto the stack. // Postcondition: the stack has a new topmost element and // the stack size increases by 1 void push(const T& item); // remove the item from the top of the stack. // Precondition: the stack is not empty. // if stack empty, throws the underflowError exception void pop(); 1/ return a reference to the element on the top of the stack. // Precondition: the stack is not empty. W if stack empty, the function throws underflowError exception T& top(); 11 constant version of top ) const T& top() const; // determine whether the stack is empty (size of 0) bool empty() const; 1/ return the number of elements in the stack int size() const; private: // a vector object maintains the stack items and size vector<T> stackVectorXX; Encapsulation and information hiding are two important object-oriented programming strategies that describe the goal of software reuse. Information hiding refers to the purposeful ignoring of details, so that other features can be considered more carefully. In our Stack implementation, we will ignore many vector methods and use only the functions helpful in our implementation. Encapsulation means to conceal, or encapsulate, details within a data structure so that they not need to be considered by users of the abstraction. The vector, for example, encapsulates the problems of memory management. The user of the vector need not know that the internal array will sometimes be resized. They can simply view the vector

Answer 1

SOURCE CODE

#include <iostream>

#include <vector>

#include <stdexcept>

using namespace std;

template <typename T>

class miniStack

{

public:

//function prototypes

miniStack();

void push(const T& item);

void pop();

T& top();

const T& top() const;

bool empty() const;

int size() const;

private:

vector <T> stackVectorXX;

};

//push tem on stack by inserting it at

//rear opf vector

template <typename T>

void miniStack<T>::push(const T& item)

{

stackVectorXX.push_back(item);

}

//if(empty()) throw underflow_error("miniStack pop() : stack empty")

//pop stack by removing last itemn in vector

template <typename T>

void miniStack<T>::pop()

{

if(empty()) throw underflow_error("miniStack pop() : stack empty");

stackVectorXX.pop_back();

}

//if(empty()) throw underflow_error("miniStack pop() : stack empty")

//return the element at the rar of vector

template <typename T>

T& miniStack<T>::top()

{

if(empty()) throw underflow_error("miniStack top() : stack empty");

return stackVectorXX[stackVectorXX.size()-1];

}

//if(empty()) throw underflow_error("miniStack pop() : stack empty")

//return the element at the rar of vector

template <typename T>

const T& miniStack<T>::top() const

{

if(empty()) throw underflow_error("const miniStack top() : stack empty");

return stackVectorXX[stackVectorXX.size()-1];

}

template <typename T>

bool miniStack<T>::empty() const

{

return stackVectorXX.empty();

}

template <typename T>

int miniStack<T>::size() const

{

return stackVectorXX.size();

}

template <typename T>

miniStack<T>::miniStack()

{

}

int main()

{

miniStack<int> stk;

//testing all functions of miniStack

cout << "Stack push 1";

stk.push(1);

cout << "\nStack push 2";

stk.push(2);

cout << "\nStack pop";

stk.pop();

cout << "\nStack top " << stk.top();

cout << "\nStack size: " << stk.size();

cout << "\nStack is empty?" << (stk.empty() ? " Yes" : " No");

cout << "\nStack pop";

stk.pop();

cout << "\nStack is empty?" << (stk.empty() ? " Yes" : " No");

return 0;

}

OUTPUT

clang++-7 pthread -std=c++17 -o main main.cpp > ./main Stack push 1 Stack push 2 Stack pop Stack top 1 Stack size: 1 Stack is empty? No Stack pop Stack is empty? Yes? I

TIME COMPLEXITY OF OPERATIONS

• push(): constant amortized time, resizing of vector may happen, which is done in linear time; Best Case O(1) , Worst Case O(n)
• pop(): constant time; O(1)
• top(): constant time; O(1)
• empty(): constant time; O(1)
• size(): constant time; O(1)
• pop(): constant time