디자인 된 min, push 와 pop 의 시간 복잡 도 는 모두 O (1) 이다.
\brief min
， min ， 。
min、push pop O(1)。
， ， min 。
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define SUCCESS 0 ///<
#define FAILED -1 ///<
typedef struct _MinStackItem ///
{
int data; ///<
struct _MinStackItem *next; ///<
} MinStackItem;
typedef struct _MinStack ///
{
MinStackItem *top; ///<
MinStackItem *min; ///<
} MinStack;
/*!
\param pStack
\return SUCCESS； FAILED
*/
int create_stack(MinStack **pStack)
{
int retVal = FAILED;
if(pStack)
{
MinStack *newStack = malloc(sizeof(MinStack));
if(newStack)
{
newStack->top = NULL;
newStack->min = NULL;
*pStack = newStack;
retVal = SUCCESS;
}
}
return retVal;
}
/*!
stack
\param stack
\return NULL ；
*/
int stack_isEmpty(const MinStack *stack)
{
return !stack || (stack && stack->top == NULL);
}
/*!
data stack， O(1)
\param stack
\param data
\return SUCCESS； FAILED
*/
int stack_push(MinStack *stack, int data)
{
int retVal = FAILED;
if(stack)
{
MinStackItem *item = malloc(sizeof(MinStackItem)); //
MinStackItem *min = malloc(sizeof(MinStackItem)); //
if(item && min)
{
item->data = data;
min->data = data;
if(stack->top && stack->min)
{
if(data < stack->top->data)
min->data = data;
else
min->data = stack->min->data;
}
/* item stack->top */
item->next = stack->top;
stack->top = item;
/* min stack->min */
min->next = stack->min;
stack->min = min;
retVal = SUCCESS;
}
}
return retVal;
}
/*!
stack data ， O(1)
\param stack
\param data
\return SUCCESS； FAILED
*/
int stack_pop(MinStack *stack, int *data)
{
int retVal = FAILED;
if(stack && data)
{
MinStackItem *freePtr = NULL;
/* top min， NULL， NULL */
assert((stack->top && stack->min) || (!stack->top && !stack->min));
if(stack->top && stack->min)
{
*data = stack->top->data; //
freePtr = stack->top; // ->freePtr
stack->top = stack->top->next; // ，
free(freePtr); //free
freePtr = stack->min; // ->freePtr
stack->min = stack->min->next; // ，
free(freePtr); //free
retVal = SUCCESS;
}
}
return retVal;
}
/*!
stack ， min ， O(1)
\param stack
\param min
\return SUCCESS； FAILED
*/
int stack_min(const MinStack *stack, int *min)
{
int retVal = FAILED;
if(stack && min && stack->min)
{
*min = stack->min->data;
retVal = SUCCESS;
}
return retVal;
}
/*!
， NULL
\param pStack
*/
void delete_stack(MinStack **pStack)
{
if(pStack)
{
MinStack *stack = *pStack;
MinStackItem *freePtr = NULL;
if(stack)
{
/* top */
while(stack->top)
{
freePtr = stack->top;
stack->top = stack->top->next;
free(freePtr);
}
/* min */
while(stack->min)
{
freePtr = stack->min;
stack->min = stack->min->next;
free(freePtr);
}
}
*pStack = NULL;
}
}
int main()
{
int result = FAILED;
int dataSet[] = {10, 4, 2, 3, 1, 5}; //
MinStack *stack = NULL; //
/* */
result = create_stack(&stack);
/* push */
{
int i;
for(i = 0; i < sizeof(dataSet) / sizeof(int) && result == SUCCESS; ++ i)
{
result = stack_push(stack, dataSet[i]);
printf("push: %d %s
", dataSet[i], result == SUCCESS ? "success!" : "failed!");
}
}
/* pop */
while(result == SUCCESS && !stack_isEmpty(stack))
{
int data = -1, min = -1;
if(stack_min(stack, &min) == SUCCESS && stack_pop(stack, &data) == SUCCESS)
printf("current min: %d, pop: %d success!
", min, data);
else
result = FAILED;
}
/* */
delete_stack(&stack);
assert(!stack);
return result;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
