キュー内で最大値を取る操作の問題(プログラミングの美3.7)
1403 ワード
#include "stdafx.h"
const int MAXN = 100;
class stack
{
public:
stack()
{
stackTop = -1;
maxItemIndex = -1;
}
void Push(int x)
{
stackTop ++;
if(stackTop >= MAXN)
;
else
{
items[stackTop]=x;
if(x>Max())
{
nextMaxItem[stackTop] = maxItemIndex;
maxItemIndex = stackTop;
}
else
nextMaxItem[stackTop] = -1;
}
}
int Pop()
{
int x;
if(stackTop < 0)
return -1;
else
{
x = items[stackTop];
if(stackTop == maxItemIndex)
{
maxItemIndex = nextMaxItem[stackTop];
}
stackTop--;
}
return x;
}
int Max()
{
if(maxItemIndex >= 0)
return items[maxItemIndex];
else
return -1;
}
bool empty()
{
return stackTop == -1;
}
private:
int items[MAXN];
int stackTop;
int nextMaxItem[MAXN];
int maxItemIndex;
};
class Queue
{
public:
void Enqueue(int x)
{
B.Push(x);
}
int Dequeue()
{
if(A.empty())
{
while(B.empty())
{
A.Push(B.Pop());
}
}
return A.Pop();
}
int Max()
{
if(A.Max() >= B.Max())
return A.Max();
else
return B.Max();
}
private:
stack A;
stack B;
};
int _tmain(int argc, _TCHAR* argv[])
{
Queue q;
q.Enqueue(10);
q.Enqueue(100);
q.Dequeue();
q.Enqueue(5);
printf("%d", q.Max());
return 0;
}