Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 37, средняя оценка - 4.95
Sylar9
-20 / 55 / 2
Регистрация: 04.09.2011
Сообщений: 1,910
Записей в блоге: 1
#1

Зачем нужен стек и очередь - C++

26.05.2012, 23:08. Просмотров 4810. Ответов 11
Метки нет (Все метки)

Не как не могу понять примение стека и очереди. Может кто то объясните зачем они нужны? я знаю как они работают, как простотой код для стека написать, а примение не могу понять
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2012, 23:08     Зачем нужен стек и очередь
Посмотрите здесь:

C++ Стек и очередь
стек и очередь C++
C++ Стек и очередь
C++ Список, стек и очередь.
Контейнерные классы: стек и очередь C++
стек и очередь C++
Очередь, стек, дерево? (реализация) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
7063 / 5240 / 262
Регистрация: 10.12.2010
Сообщений: 23,052
Записей в блоге: 17
26.05.2012, 23:50     Зачем нужен стек и очередь #2
http://ru.wikipedia.org/wiki/FIFO_(информатика)
http://ru.wikipedia.org/wiki/LIFO_(информатика)
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
26.05.2012, 23:52     Зачем нужен стек и очередь #3
В очереди можно создать много однотипных данных:
C++
1
char* c = new char[100000500000];
В стеке приведет к ошибке:
C++
1
char c[100000500000];
Avazart
7063 / 5240 / 262
Регистрация: 10.12.2010
Сообщений: 23,052
Записей в блоге: 17
26.05.2012, 23:55     Зачем нужен стек и очередь #4
О чем ты programina?
gray_fox
What a waste!
1256 / 1139 / 55
Регистрация: 21.04.2012
Сообщений: 2,361
Завершенные тесты: 3
26.05.2012, 23:59     Зачем нужен стек и очередь #5
programina О_о интересно...

Добавлено через 1 минуту
С выделением памяти (стек\куча) перепутали?
Evg
Эксперт CАвтор FAQ
17392 / 5630 / 352
Регистрация: 30.03.2009
Сообщений: 15,416
Записей в блоге: 26
27.05.2012, 00:04     Зачем нужен стек и очередь #6
Цитата Сообщение от Sylar9 Посмотреть сообщение
Может кто то объясните зачем они нужны?
Почитай алгоритмы типа "поиск в глубину" и "поиск в ширину" - в них используется стек. В некоторых алгоритмах используется очередь (навскидку не вспомню, но что-то вертится около "полный перебор"). Т.е. стек и очередь - это инструменты при решении алгоритмических (и не только) задач

Добавлено через 1 минуту
На форуме несколько раз мелькала задача о проверке правильности расстановок скобок. В основе решения точно так же используется стек. Это хорошо проявляется в случае неоднородных скобок (т.е. когда присутствуют круглые, квадратные, фигурные скобки)

Добавлено через 1 минуту
Цитата Сообщение от Avazart Посмотреть сообщение
О чем ты programina?
Она путает понятия "стек как алгортимический инструмент" и "стек как аппаратный механизм для обеспечения процедурных вызовов"
Avazart
7063 / 5240 / 262
Регистрация: 10.12.2010
Сообщений: 23,052
Записей в блоге: 17
27.05.2012, 00:30     Зачем нужен стек и очередь #7
Ну вообще можно сказать что эти вещи -хранилища элементов, но в отличии от массивов,векторов итп очень ограниченые по доступу к элементам.
diagon
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.05.2012, 06:07     Зачем нужен стек и очередь #8
Цитата Сообщение от Evg Посмотреть сообщение
"поиск в ширину" - в них используется стек
Как раз в поиске в ширину используется очередь.
Одно из практических применений для очереди(для стека применений очень много, лень их все описывать):
Допустим, у вас есть задача - получить с консоли некую последовательность чисел, и затем вывести эту последовательность с удвоенными элементами в консоль.
Классический подход - сначала сохранить все считываемые данные в массиве, и затем вывести этот массив.
Т.е.
примерно такой код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>
 
int main()
{
    std::vector< int > arr;
    
    int x;
    while (std::cin >> x && x != 0) //0 - конец ввода
        arr.push_back(x);
 
    for (size_t i = 0; i < arr.size(); ++i)
        std::cout << arr[i] * 2 << std::endl;
}

Альтернативный подход - использовать очередь.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <queue>
 
int main()
{
    std::queue< int > qu;
    
    int x;
    while (std::cin >> x && x != 0) //0 - конец ввода
        qu.push(x * 2);
    
    for (; !qu.empty(); qu.pop() )
        std::cout << qu.front() << std::endl;
}
В данном случае задача надумана и очень проста, но даже здесь мне решение с очередью кажется более красивым. В более сложных задачах, где нужно накапливать ответ, сложно найти достойную замену очереди.
Sylar9
-20 / 55 / 2
Регистрация: 04.09.2011
Сообщений: 1,910
Записей в блоге: 1
27.05.2012, 08:08  [ТС]     Зачем нужен стек и очередь #9
Правильно ли я понимаю, что стек нужен решение алгоритмом ?
Catstail
Модератор
22309 / 10714 / 1742
Регистрация: 12.02.2012
Сообщений: 17,786
27.05.2012, 08:45     Зачем нужен стек и очередь #10
Стек - важнейшая структура данных. Используется при обходе графов (вообще любых структур, задаваемых рекурсивно - файловой системы, например). Еще одно применение - вычисление (или трансляция) алгебраических выражений.
ValeryS
Модератор
6511 / 4977 / 460
Регистрация: 14.02.2011
Сообщений: 16,484
27.05.2012, 11:13     Зачем нужен стек и очередь #11
Цитата Сообщение от diagon Посмотреть сообщение
Допустим, у вас есть задача - получить с консоли некую последовательность чисел, и затем вывести эту последовательность с удвоенными элементами в консоль.
используем очередь
А если нужно вывести задом наперед (сначала последнее потом первое)
то используем стек

Добавлено через 4 минуты
Цитата Сообщение от programina Посмотреть сообщение
В стеке приведет к ошибке
C++
1
char c[100000500000];
во время исполнения (рухнет стек)
Но!
стек для хранения локальных переменных это одно
стек как организация данных это совершенно другое
есть еще много таких разночтений(в русском языке это называется Омо́нимы)
например "класс окна" в виндосе и "класс с++" абсолютно разные вещи
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.05.2012, 13:37     Зачем нужен стек и очередь
Еще ссылки по теме:

Очередь(а выходит стек) C++
C++ Стек и очередь
C++ Очередь и стек
Стек, очередь (линейные списки) C++
стек и очередь C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Evg
Эксперт CАвтор FAQ
17392 / 5630 / 352
Регистрация: 30.03.2009
Сообщений: 15,416
Записей в блоге: 26
27.05.2012, 13:37     Зачем нужен стек и очередь #12
Цитата Сообщение от diagon Посмотреть сообщение
Как раз в поиске в ширину используется очередь
Угу... вечером голова совсем не варила...

Цитата Сообщение от Sylar9 Посмотреть сообщение
Правильно ли я понимаю, что стек нужен решение алгоритмом ?
Именно так. Считай, что стек и очередь (а так же дэк, список, дерево, граф и пр.) для программиста - это как интеграл и логарифм для математика. Сами по себе вещи не нужные, а нужны лишь в качестве инструмента для решения других задач
Yandex
Объявления
27.05.2012, 13:37     Зачем нужен стек и очередь
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru