CC150 3.3

3_3.cpp

/* CC150 3.3
 * Implement a data structure SetOfStacks that should be composed of several stacks and should create a new stack
 * once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should be have identically to
 * a single stack(that is, pop() should return the same values as it would if there were just a single stack).
 * FOLLOW UP
 * Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
 */

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

class SetOfStacks{
public:
	SetOfStacks() : STACK_SIZE_MAX(10) {}
	SetOfStacks(int n) : STACK_SIZE_MAX(n) {}
	bool empty() { return stackSet.empty(); }
	void push(int data);
	void pop();
	int top() { return stackSet.top().top(); }
	int size() { return stackNum; } // number of sub-stacks
private:
	stack<stack<int>> stackSet;
	int STACK_SIZE_MAX;
	int stackNum = 0;
};

void SetOfStacks::push(int data)
{
	if (stackSet.empty() || stackSet.top().size() == STACK_SIZE_MAX) {
		stack<int> newStack; // generates a new stack if the stack set is empty or the uppermost sub-stack is full
		newStack.push(data);
		stackSet.push(newStack);
		++stackNum;
	}
	else
		stackSet.top().push(data);
	return;
}

void SetOfStacks::pop()
{
	if (stackSet.empty()) {
		cerr << "Empty stack!" << endl;
		return;
	}
	stackSet.top().pop();
	if (stackSet.top().empty()) {
		stackSet.pop(); // deletes the uppermost sub-stack if it becomes empty
		--stackNum;
	}
	return;
}

void display(SetOfStacks s)
{
	cout << "size: " << s.size() << " Data: ";
	while (!s.empty()) {
		cout << s.top() << " ";
		s.pop();
	}
	cout << endl;
	return;
}

// FOLLOW UP
class SetOfStacksRn { // set of stacks with random access popAt()
public:
	SetOfStacksRn() : STACK_SIZE_MAX(10) {}
	SetOfStacksRn(int n) : STACK_SIZE_MAX(n) {}
	bool empty() { return stackSet.empty(); }
	void push(int data);
	void pop();
	int top() { return (*--stackSet.end()).top(); }
	int size() { return stackSet.size(); } // number of sub-stacks
	void popAt(int index); // index should range from 1 to size()
	int topAt(int index); // index should range from 1 to size()
private:
	int STACK_SIZE_MAX;
	vector<stack<int>> stackSet; // enables random access for popAt() operation
};

void SetOfStacksRn::push(int data)
{
	if (stackSet.empty() || (*--stackSet.end()).size() == STACK_SIZE_MAX) {
		stack<int> newStack;
		newStack.push(data);
		stackSet.push_back(newStack);
	}
	else
		(*--stackSet.end()).push(data);
	return;
}

void SetOfStacksRn::pop()
{
	if (stackSet.empty()) {
		cerr << "Empty stack!" << endl;
		return;
	}
	(*--stackSet.end()).pop();
	if ((*--stackSet.end()).empty())
		stackSet.erase(--stackSet.end());
	return;
}

void SetOfStacksRn::popAt(int index)
{
	if (index < 1 || index > stackSet.size()) {
		cerr << "Invalid index!" << endl;
		return;
	}
	auto begin = stackSet.begin(), end = stackSet.end();
	for (int i = 1; begin != end && i != index; ++i)
		++begin; // move begin iterator to the selected sub-stack
	begin->pop();
	if (begin->empty()) // delete the sub-stack if it becomes empty
		stackSet.erase(begin);
	return;
}

int SetOfStacksRn::topAt(int index)
{
	if (index < 1 || index > stackSet.size()) {
		cerr << "Invalid index!" << endl;
		return -1;
	}
	auto begin = stackSet.begin(), end = stackSet.end();
	for (int i = 1; begin != end && i != index; ++i)
		++begin;
	return begin->top();
}

void display(SetOfStacksRn s)
{
	cout << "size: " << s.size() << " Data: ";
	while (!s.empty()) {
		cout << s.top() << " ";
		s.pop();
	}
	cout << endl;
	return;
}

int main()
{
	//SetOfStacks ss(3);
	SetOfStacksRn ss(3);
	ss.push(1); display(ss);
	ss.push(2); display(ss);
	ss.push(3); display(ss);
	ss.push(4); display(ss);
	ss.push(5); display(ss);
	//cout << "Pop out " << ss.top() << endl;
	//ss.pop(); display(ss);
	cout << "Pop out " << ss.topAt(1) << endl;
	ss.popAt(1); display(ss);
	//cout << "Pop out " << ss.top() << endl;
	//ss.pop(); display(ss);
	cout << "Pop out " << ss.topAt(1) << endl;
	ss.popAt(1); display(ss);
	cout << "Pop out " << ss.top() << endl;
	ss.pop(); display(ss);
	return 0;
}