实现一个栈并获取其最小元素

设计包含min函数的栈
服务器君一共花费了220.954 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

定义栈的数据结构,要求添加一个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;
}

本文地址:http://www.nowamagic.net/librarys/veda/detail/1043,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1043

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《浪潮之巅》 吴军 (作者)

近一百多年来,总有一些公司很幸运地、有意识或无意识地站在技术革命的浪尖之上。在长达十年甚至几十年的时间里,它们代表着科技的浪潮,直到下一波浪潮的来临。从19世纪末算起,AT&T公司、IBM公司、苹果公司、英特尔公司、微软公司、思科公司、雅虎公司和Google公司都先后被幸运地推到了浪尖。虽然,它们来自不同的领域,中间有些已经衰落或正在衰落,但是它们都极度辉煌过。吴军的这本《浪潮之巅》系统地介绍了这些公司成功的本质原因及科技工业一百多年的发展。在这些公司兴衰的背后,有着它必然的规律。《浪潮之巅》不仅讲述科技工业的历史,更重在揭示它的规律性。

更多计算机宝库...