Стек (структура данных)
Стек - это одна из самых важных структур данных в информатике. Чтобы понять, как работает стек, представьте себе колоду игральных карт, лежащую лицевой стороной вниз. Мы можем легко получить доступ только к той карте, которая лежит сверху. Когда мы хотим посмотреть на верхнюю карту, мы можем сделать две вещи: мы можем заглянуть в нее, но оставить ее в стопке, или мы можем снять ее. Когда мы снимаем верхний объект, мы убираем его из стопки. Если мы хотим добавить еще одну карточку на вершину стопки, мы толкаем ее.
Стопка называется коллекцией "последний в первом" (LIFO). Это означает, что последнее, что мы добавили (толкнули), является первым, что мы вытащили (вынули). Если последней картой, которую мы положили на стопку карт, был туз, то первой картой, которую мы достали сверху, будет тот же туз.
Два действия над стеком: push и pop.
История
Впервые стек был предложен в 1955 году, а затем запатентован в 1957 году немцем Фридрихом Л. Бауэром. Та же концепция была разработана независимо, примерно в то же время, австралийцем Чарльзом Леонардом Хэмблином.
Другие операции
В современных компьютерных языках стек обычно реализуется с помощью большего количества операций, чем просто "push" и "pop". В некоторых реализациях есть функция, которая возвращает текущую длину стека. Другой типичной вспомогательной операцией является "top" (также известная как "peek"), которая может вернуть текущий верхний элемент стека, не удаляя его. Еще одной распространенной операцией является "dup", которая создает копию элемента, находящегося на вершине стека.
Похожие страницы
- Штабелеукладчик
