сегодня читала про абстрактные типы данных, если честно, ничетра не поняла, наверное потому что там основное внимание уделяется созданию стека... вот в этом главная проблема: зачем создавать стек?? я вообще не могу осознать такого понятие как "создание стека"!!!! стек - это ж типа способ хранения памяти,при котором то ,что ложится в память последним, вынимается первым.... так как же можно его создавать?? он же уже всегда есть!!!! объясните пожалуйста несмышленому ламеру...

А вот и ответ :

Цитата

стек - это ж типа способ хранения памяти,при котором то ,что ложится в память последним, вынимается первым....

Можно создать стек каких-либо объектов. Например дом - это объект. И класть их(дома) в стек. А потом доставать. Абстракция, одним словом

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

2 murzzzzz

Так... Не путай Один Стек с Дргим. )

В АТД под словом стек подразумевается тип данных в котором ЛЮБЫЕ данные (Например тетрадки на столе учительницы) работают по принципу FILO (Фест инпут Ласт Аутпут)... А то как что в памяти комп хранит сюда не относиться, хотя работает по этому же принципу. )

так а зачем нам этот стек тогда надо создавать?

murzzzzz, для решения задачь определенного типа...
Также как тебе ингда нужны масивы.. коненчо без них можно обойтись, но с ними прозе... Так и стеки, очереди, деревья и прочие структуры нужны чтобы облегчить жизнь )

Представь себе трубку в которую ты засовываешь шарики и они вываливаются с другого конца
Это и есть стёк..


Это сообщение отредактировал(а) chipset - 16.2.2005, 01:47

chipset
это не стёк - это очередь скорее

2 chipset, Стек это скорей трубочка с запаяным концом... И если вкинуть несколько шариков и понадобиться вытащить первый... ТО сперва прийдется вытрусить все )
Добавлено @ 12:38
2 murzzzzz, а АТД потому и абстрактные, что мы о них говорим как о домиках, шариках и памяти ))) И заметь нам это не мешает... абстракция ;)

А приведите, пожалуйста, пример создания стека с комментариями.

Цитата(Admin @ 16.2.2005, 13:44)

приведите, пожалуйста, пример создания стека с комментариями.

Запросто. Очередной комментарий пишется на бумажку и кладется поверх стопки комментариев. Снимать и читать можно только сверху - ни в середину, и в низ пачки лазить низзя...

Цитата(Akina @ 16.2.2005, 12:47)

Запросто. Очередной комментарий пишется на бумажку и кладется поверх стопки комментариев.

- просто супер.

Пример, реализации ПРОСТОГО стека, работающего с простым типом данных int, на основе массива.

Код

static int *s; static int n; void initS(int maxNum) // инициализация стека. {    s=malloc(maxNum*sizeof(int)); // размер глубины стека    n=0; // указатель на текущую глубину стека } void pushS(int item) // вставляем новый элемент {   s[n++]=item; } int popS() // извлекаем элемент {   return s[--n]; }

Это сообщение отредактировал(а) Наставник - 16.2.2005, 15:35

Пример для Си++

Код

#include <stack> #include <iostream> int main(void) {    // стек целых чисел (по умолчанию используется контейнер deque).    std::stack<int> stack;    // кладём в стек пять чисел.    for (int i = 0; i < 5; ++i)        stack.push(i);    // теперь извлекаем из стека числа и выводим на экран.    while (!stack.empty())    {        // берём элемент из вершины стека и выводим в поток.        std::cout << stack.top() << ' ';        // удаляем элемент в верхушке стека.        stack.pop();    }    std::cout << std::endl; return 0; }

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

Или другой пример, мы интерпретируем некоторый код в постфиксной нотации, операнды кладутся на стек, затем выполняется операция, результат снова на стек и т.д.

Третий пример тоже со стеком, парсим XML файл, открытый тег кладём на стек, когда встречаем закрывающий тег, на стеке он должен лежать иначе материмся диким матом о ошибочной вложенности тегов

Пример реализации стека ввиде связанного списка, с избыточными комментариями:

Код

template <class Type>  // Type - тип данных, хранящихся в стеке. class Stack {  private :    struct Node       // Узлы списка, реализующего стек    {      Type *data;    // Данные, хранящиеся в стеке;      Node* next;   // Указатель на следующий узел списка.      Node( Type *I, Node *N ) : data(I), next(N) {};    } *Head;          // Голова списка  public :    Stack( void ) : Head(NULL) {};    virtual ~Stack( void ) { DeleteAll(); };    // При удалении стека, не забываем                                                                  // удалить все его элементы.    bool Empty ( void ) const { return Head == NULL; };      // Пустует ли наш стек?    void Push ( Type *T ) { Head = new Node(T, Head); };  // Добавить элемент в стек.    Type* Pop ( void );       // Вытолкнуть элемент из стека    void DeleteAll ( void );  // Удалить всё }; template <class Type> Type *Stack<Type>::Pop()  //  возвращает "вытолкнутый" элемент. {  if ( !node ) return NULL;    // Если стек пуст, возвращаем NULL.  Node *tmp = Head;          // Возвращаем "верхний", а верхушкой  Head = Head->next;        // стека делаем предыдущий элемент.  return tmp->data; }; template <class Type> void Stack<Type>::DeleteAll( void ) {  while ( Head )                  // Пока есть элементы :  {    Node *tmp = Head;       // приговариваем верхний элемент,    Head = Head->next;     // теперь верхним делаем предыдущий,    delete tmp;                   // "протыкаем" "приговоренный" элемент.  } };

Можно, конечно, удалять элементы по-другому, заставляя каждый узел списка удалять следующий. Но по моему для примера так нагляднее.

Это сообщение отредактировал(а) Chaos A.D. - 17.2.2005, 00:49