Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore,
in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks
should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks. push() and SetOfStacks. pop() should behave 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 <vector>
#include <stack>
using namespace std;
#define STACK_CAP 5
vector<stack<int>*> vec;
int index = 0;
bool initialized = false;
void init_stacks()
{
stack<int> *s = new stack<int>;
vec.push_back(s);
}
void stack_push(int v)
{
if(initialized == false){
initialized = true;
// init_stacks();
}
stack<int> *s = vec.at(index);
if(s->size() == 5){
s = new stack<int>;
vec.push_back(s);
index ++ ;
}
s->push(v);
}
void stack_pop()
{
stack<int> *s = vec.at(index);
if(index > 0){
if(s->size() == 0){
delete s;
index --;
s = vec.at(index);
}
s->pop();
}
else{
if(s->size() == 0){
;//cout << " no more elements in stack !" << endl;
}
else{
s->pop();
}
}
}
bool stack_top(int &v)
{
//int v = 0;
stack<int> *s = vec.at(index);
if(s->size() == 0 && index == 0){
return false;
}
if(s->size() == 0){
delete s;
index --;
s = vec.at(index);
}
v = s->top();
return true;
}
void deinit_stacks()
{
stack<int> *s;
for(int i = 0; i <= index; i++){
s = vec.at(i);
delete s;
}
}
int main(int argc, char* argv[])
{
init_stacks();
for(int i = 0; i < 30; i++){
stack_push(i);
cout << "Push: Stack index " << index << " -- " << i << endl;
}
for(int i = 0; i < 40; i++){
int v;
int b = stack_top(v);
stack_pop();
if(b){
cout << "Stack index " << index << " -- " << v << endl;
}
else{
cout << "No more elements in stack !" << endl;
}
}
for(int i = 0; i < 10; i++){
stack_push(i);
cout << "Push: Stack index " << index << " -- " << i << endl;
}
for(int i = 0; i < 15; i++){
int v;
int b = stack_top(v);
stack_pop();
if(b){
cout << "Stack index " << index << " -- " << v << endl;
}
else{
cout << "No more elements in stack !" << endl;
}
}
deinit_stacks();
return 0;
}
Output
Push: Stack index 0 -- 0
Push: Stack index 0 -- 1
Push: Stack index 0 -- 2
Push: Stack index 0 -- 3
Push: Stack index 0 -- 4
Push: Stack index 1 -- 5
Push: Stack index 1 -- 6
Push: Stack index 1 -- 7
Push: Stack index 1 -- 8
Push: Stack index 1 -- 9
Push: Stack index 2 -- 10
Push: Stack index 2 -- 11
Push: Stack index 2 -- 12
Push: Stack index 2 -- 13
Push: Stack index 2 -- 14
Push: Stack index 3 -- 15
Push: Stack index 3 -- 16
Push: Stack index 3 -- 17
Push: Stack index 3 -- 18
Push: Stack index 3 -- 19
Push: Stack index 4 -- 20
Push: Stack index 4 -- 21
Push: Stack index 4 -- 22
Push: Stack index 4 -- 23
Push: Stack index 4 -- 24
Push: Stack index 5 -- 25
Push: Stack index 5 -- 26
Push: Stack index 5 -- 27
Push: Stack index 5 -- 28
Push: Stack index 5 -- 29
Stack index 5 -- 29
Stack index 5 -- 28
Stack index 5 -- 27
Stack index 5 -- 26
Stack index 5 -- 25
Stack index 4 -- 24
Stack index 4 -- 23
Stack index 4 -- 22
Stack index 4 -- 21
Stack index 4 -- 20
Stack index 3 -- 19
Stack index 3 -- 18
Stack index 3 -- 17
Stack index 3 -- 16
Stack index 3 -- 15
Stack index 2 -- 14
Stack index 2 -- 13
Stack index 2 -- 12
Stack index 2 -- 11
Stack index 2 -- 10
Stack index 1 -- 9
Stack index 1 -- 8
Stack index 1 -- 7
Stack index 1 -- 6
Stack index 1 -- 5
Stack index 0 -- 4
Stack index 0 -- 3
Stack index 0 -- 2
Stack index 0 -- 1
Stack index 0 -- 0
No more elements in stack !
No more elements in stack !
No more elements in stack !
No more elements in stack !
No more elements in stack !
No more elements in stack !
No more elements in stack !
No more elements in stack !
No more elements in stack !
No more elements in stack !
Push: Stack index 0 -- 0
Push: Stack index 0 -- 1
Push: Stack index 0 -- 2
Push: Stack index 0 -- 3
Push: Stack index 0 -- 4
Push: Stack index 1 -- 5
Push: Stack index 1 -- 6
Push: Stack index 1 -- 7
Push: Stack index 1 -- 8
Push: Stack index 1 -- 9
Stack index 1 -- 9
Stack index 1 -- 8
Stack index 1 -- 7
Stack index 1 -- 6
Stack index 1 -- 5
Stack index 0 -- 4
Stack index 0 -- 3
Stack index 0 -- 2
Stack index 0 -- 1
Stack index 0 -- 0
No more elements in stack !
No more elements in stack !
No more elements in stack !
No more elements in stack !
No more elements in stack !
请按任意键继续. . .