В чем разница между этими двумя различными реализациями функции 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 ответа:
Можно использовать любой из них. Главное отличие-это количество сделанных копий.
В первом случае результирующее значение записывается непосредственно в целевую переменную через разыменование указателя. Во втором случае значение (в большинстве реализаций) помещается в стек, а затем копируется в переменную, получающую возвращаемое значение, предполагая, что возвращаемое значение присвоено.
Для случая возвращаемого значения, учитывая, что возвращается структура, компилятор, вероятно, не копирует возвращает значение в стек, но в другое место и помещает указатель на это место в стеке. Однако это полностью зависит от реализации. В любом случае данные структуры копируются дважды. Если структура относительно мала, то не должно быть измеримой разницы, хотя она может стать значительной, если структура имеет размер в несколько мегабайт.
Обе функции не имеют хорошего дизайна. Проблема обеих функций заключается в том, что стек может быть пустым. В этом случае функции имеют неопределенное поведение, и трудно определить, так ли это.
В 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]; }