В чем разница между этими двумя различными реализациями функции StackTop?


Я изучаю курс по структурам данных, и в настоящее время я застрял с чем-то в стеках. При реализации функции StackTop (которая делает копию или "возвращает в некотором смысле " верхний элемент в стеке, не влияя на стек.) Приведенный ниже код является его реализацией, и это ясно,

void StackTop(StackEntry *pe, Stack *ps){
    *pe=ps->entry[ps->top-1];
}

Но пока мы хотим дать пользователю значение верхнего элемента в стеке, не могли бы мы сделать функцию такой ? И если да, то в чем разница между ними? эти две реализации ?

StackEntry StackTop(Stack *ps){
    return ps->entry[ps->top-1];
}

Имейте в виду, что StackEntry-это определяемый пользователем тип данных.

2 2

2 ответа:

Можно использовать любой из них. Главное отличие-это количество сделанных копий.

В первом случае результирующее значение записывается непосредственно в целевую переменную через разыменование указателя. Во втором случае значение (в большинстве реализаций) помещается в стек, а затем копируется в переменную, получающую возвращаемое значение, предполагая, что возвращаемое значение присвоено.

Для случая возвращаемого значения, учитывая, что возвращается структура, компилятор, вероятно, не копирует возвращает значение в стек, но в другое место и помещает указатель на это место в стеке. Однако это полностью зависит от реализации. В любом случае данные структуры копируются дважды. Если структура относительно мала, то не должно быть измеримой разницы, хотя она может стать значительной, если структура имеет размер в несколько мегабайт.

Обе функции не имеют хорошего дизайна. Проблема обеих функций заключается в том, что стек может быть пустым. В этом случае функции имеют неопределенное поведение, и трудно определить, так ли это.

В C лучшее определение функции может выглядеть как

int StackTop( Stack *ps, StackEntry *pe )
{
    int success = ps->top != 0;

    if ( success )
    {
        *pe = ps->entry[ps->top-1];
    }

    return success;
}

Если вы не беспокоитесь о неопределенном поведении функций, потому что есть еще одна функция, которая сообщает, пуст ли стек, то вы должны рассмотреть еще одну реализацию функции это позволит изменить значение, хранящееся в стеке. Такая функция может выглядеть как

StackEntry * StackTop(Stack *ps)
{

    return &ps->entry[ps->top-1];
}