简明现代魔法 -> 数据结构 -> 获取栈中的最小元素

获取栈中的最小元素

2011-03-06

定义栈的数据结构,要求添加一个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\n", 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!\n", min, data);
        else
            result = FAILED;
    }
 
    /* 释放栈 */
    delete_stack(&stack);
 
    assert(!stack);
 
    return result;
}
随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们