Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Структуры данных и хэширование / Введение в абстрактные структуры /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


8  Статическая реализация стека на основе массива
8  Динамическая реализация стека на основе списка
8  Реализация стека на основе ранее рассмотренного кольцевого списка
8  Использование стека: развертка рекурсии
Cтек - Программирование от RIN.RU
Cтек

Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришел - первым исключается"). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.


Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop - выскакивать).


Полезными могут быть также вспомогательные операции:


  • определение текущего числа элементов в стеке;

  • очистка стека;

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


x:=pop(stack); push(stack,x);




Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.


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


  • а). пустого;

  • б-г). после последовательного включения в него элементов с именами 'A', 'B', 'C';

  • д, е). после последовательного удаления из стека элементов 'C' и 'B';

  • ж). после включения в стек элемента 'D'.






Включение и исключение элементов из стека

Рис. 4: Включение и исключение элементов из стека




Как видно из рис. 4, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D... Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.






SpeedSIP значительно снижает расходы на телефонную связь и сервисы:
  • бесплатные звонки внутри сети,
  • выгодные международные и междугородные звонки,
  • СМС по всему миру,
  • покупка прямого номер любой страны,
  • видеосвязь и видеоконференции.


  • В этом разделе :

    8  Статическая реализация стека на основе массива
    При представлении стека в статической памяти для стека выделяется память, как для вектора.

    8  Динамическая реализация стека на основе списка
    Стек представляется как линейный список, в котором включение элементов всегда производятся в начала списка, а исключение - также из начала.

    8  Реализация стека на основе ранее рассмотренного кольцевого списка
    Реализация опирается на класс кольцевого списка. Шаблон класса Stack содержит собственный элемент данных s, который указывает на объект List, представляющий собой стек.

    8  Использование стека: развертка рекурсии
    Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур.

    8  Статическая реализация стека на основе массива
    8  Динамическая реализация стека на основе списка
    8  Реализация стека на основе ранее рассмотренного кольцевого списка
    8  Использование стека: развертка рекурсии

     
      
      
        Copyright ©  RIN 2003 - 2004      * Обратная связь