//Implement 3 stacks using a single list :
//
//class Stack :
// def __init__(self) :
// self.list = []
//
// def pop(self, stack_number) :
// pass
//
// def push(self, item, stack_number) :
// pass
#include <iostream>
#include <string>
#include <list>
using namespace std;
class SubStack
{
private:
int data = 0;
bool tailNode = false;
bool used = true;
public:
//SubStack* newHead, SubStack* newTail
SubStack(bool inUse, int dataVal = 0, bool tail = false)
{
tailNode = tail;
setInUse(inUse);
setData(dataVal);
}
SubStack* next;
SubStack* prev;
void setData(int newData) { data = newData; };
int getData() { return data; };
bool isTail() { return tailNode; };
bool inUse() { return used; };
void setInUse(bool inUse) { used = inUse; };
};
SubStack* getNextFreeNode(SubStack* head);
class StackList
{
private:
int item;
SubStack* head1;
SubStack* head2;
SubStack* head3;
SubStack* tail1 = nullptr;
SubStack* tail2 = nullptr;
SubStack* tail3 = nullptr;
public:
StackList()
{
head1 = new SubStack(true, 1);
head2 = new SubStack(true, 2);
head3 = new SubStack(true, 3);
tail1 = new SubStack(false, -1, true);
tail2 = new SubStack(false, -1, true);
tail3 = new SubStack(false, -1, true);
head1->next = tail1;
head2->next = tail2;
head3->next = tail3;
tail1->prev = head1;
tail2->prev = head2;
tail3->prev = head3;
// initially link the stacks together
tail1->next = head2;
tail2->next = head3;
}
void pop(int stack_number)
{
switch (stack_number)
{
case 1:
tail1->prev->setInUse(false);
break;
case 2:
tail2->prev->setInUse(false);
break;
case 3:
tail3->prev->setInUse(false);
break;
}
}
void push(int item, int stack_number)
{
SubStack* freeNode;
switch (stack_number)
{
case 1:
freeNode = getNextFreeNode(head1);
if (freeNode)
{
freeNode->setInUse(true);
freeNode->setData(item);
}
else // no open node, we need to generate one
{
// insert the newly made node
SubStack* newNode = new SubStack(true, item);
SubStack* temp;
newNode->next = tail1;
temp = tail1->prev;
tail1->prev = newNode;
temp->next = newNode;
}
break;
case 2:
freeNode = getNextFreeNode(head2);
if (freeNode)
{
freeNode->setInUse(true);
freeNode->setData(item);
}
else // no open node, we need to generate one
{
// insert the newly made node
SubStack* newNode = new SubStack(true, item);
SubStack* temp;
newNode->next = tail2;
temp = tail2->prev;
tail2->prev = newNode;
temp->next = newNode;
}
break;
case 3:
freeNode = getNextFreeNode(head3);
if (freeNode)
{
freeNode->setInUse(true);
freeNode->setData(item);
}
else // no open node, we need to generate one
{
// insert the newly made node
SubStack* newNode = new SubStack(true, item);
SubStack* temp;
newNode->next = tail3;
temp = tail3->prev;
tail3->prev = newNode;
temp->next = newNode;
}
break;
default:
cout << "Only 3 stacks, choose one..." << endl;
break;
}
}
SubStack* getHead() { return head1; };
};
SubStack* getNextFreeNode(SubStack* head)
{
SubStack* node = head;
while (node && !node->isTail())
{
if (!node->inUse())
return node;
node = node->next;
}
return nullptr;
}
int main()
{
StackList* stack = new StackList();
stack->push(2, 1);
stack->push(3, 1);
stack->push(4, 2);
//stack->push(5, 2);
//stack->push(6, 2);
stack->push(7, 3);
stack->push(8, 3);
stack->push(9, 3);
stack->pop(1);
stack->pop(2);
stack->pop(3);
stack->push(12, 2);
SubStack* temp = stack->getHead();
while (temp)
{
if(temp->inUse())
cout << temp->getData() << endl;
temp = temp->next;
}
return 0;
}
コメント