Какова временная эффективность операций push(), pop(), isEmpty() и peek() стеков?

Стек — это линейная структура данных, которая следует порядку LIFO (последний пришел — первый ушел), т. е. данные вводятся с одного конца, и пока они удаляются, они будут удаляться с того же конца.

The few most performed operations in a stack are:

1. push()
2. pop()
3. isEmpty()
4. peek()

Теперь проверим эффективность операций по времени:

1. нажать():

Эта функция вызывается для вставки нового элемента в стек.

Синтаксис:

stack.push(value)

Временная сложность: O(1)

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

2. тянуть()

Эта функция вызывается для удаления самого верхнего элемента стека.

Синтаксис:

stack.pop() 

Временная сложность: O(1)

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

3. пусто():

Эта функция вызывается, чтобы проверить, пуст стек или нет.

Синтаксис:

stack.isEmpty() 

Временная сложность: O(1)

4. заглянуть():

Эта функция вызывается для получения значения самого верхнего элемента стека.

Синтаксис:

stack.peek()

Временная сложность: O(1)

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

Для получения более подробной информации см.:
Проектирование и анализ алгоритмов.