【アルゴリズム】min関数を含むスタックを設計し,時間複雑度はいずれもO(1)である.

min関数を含むスタックを設計します.スタックのデータ構造を定義し、スタックの最小要素を得るためにmin関数を追加する必要があります.要求関数min,pushおよびpopの時間複雑度はいずれもO(1)である.
以下のプログラムはシーケンスチェーンテーブルを採用して実現し、実現時に関連ブログを参考にし、漏れがある場合は、指摘を歓迎します.
考え方:空間で時間を変える方法

#include
#define MAXSIZE 256

typedef struct minStackElement
{
	int value;
	int min;
}MinStackElement;

typedef struct minStack
{
	MinStackElement data[MAXSIZE];//          ，        ，    min
	int top;
}MinStack;

int Init(MinStack *p)
{
	int i;
	for(i=0; idata[i].value=0;
		p->data[i].min=0;
	}

	p->top = 0;
	return 0;
}


int Push(MinStack *p, int d)
{
	if(p->top == MAXSIZE)
	{
		printf("stack full");
		return -1;
	}
	p->data[p->top].value = d;
	p->data[p->top].min = (p->top == 0 ? d : p->data[p->top-1].min);
	if(p->data[p->top].min > d)
		p->data[p->top].min = d;
	p->top++;
	return 0;
}

int Pop(MinStack *p)
{
	if(p->top == 0)
	{
		printf("empty");
		return -1;
	}
	return p->data[p->top--].value;
}

int getMin(MinStack *p)
{
	if(p->top == 0)
	{
		printf("empty");
		return -1;
	}
	return p->data[p->top-1].min;
}

int main()
{
	int min;
	MinStack ms;
	MinStack *p = &ms;
	Init(p);
	Push(p,11);
	Push(p,2);
	Push(p,35);
	Push(p,46);
	Push(p,77);
	Push(p,56);
	Push(p,175);
	Push(p,1);
	min = getMin(p);
	printf("min=%d
",min);
	
}