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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 37, средняя оценка - 4.95
Sylar9
-20 / 55 / 2
Регистрация: 04.09.2011
Сообщений: 1,888
Записей в блоге: 1
26.05.2012, 23:08     Зачем нужен стек и очередь #1
Не как не могу понять примение стека и очереди. Может кто то объясните зачем они нужны? я знаю как они работают, как простотой код для стека написать, а примение не могу понять
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2012, 23:08     Зачем нужен стек и очередь
Посмотрите здесь:

C++ СТЕК,ОЧЕРЕДЬ
C++ Стек и очередь
стек и очередь C++
C++ Стек и очередь
C++ Стек и очередь
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
26.05.2012, 23:50     Зачем нужен стек и очередь #2
http://ru.wikipedia.org/wiki/FIFO_(информатика)
http://ru.wikipedia.org/wiki/LIFO_(информатика)
programina
 Аватар для programina
1912 / 597 / 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
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
26.05.2012, 23:55     Зачем нужен стек и очередь #4
О чем ты programina?
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
26.05.2012, 23:59     Зачем нужен стек и очередь #5
programina О_о интересно...

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

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

Добавлено через 1 минуту
Цитата Сообщение от Avazart Посмотреть сообщение
О чем ты programina?
Она путает понятия "стек как алгортимический инструмент" и "стек как аппаратный механизм для обеспечения процедурных вызовов"
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
27.05.2012, 00:30     Зачем нужен стек и очередь #7
Ну вообще можно сказать что эти вещи -хранилища элементов, но в отличии от массивов,векторов итп очень ограниченые по доступу к элементам.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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,888
Записей в блоге: 1
27.05.2012, 08:08  [ТС]     Зачем нужен стек и очередь #9
Правильно ли я понимаю, что стек нужен решение алгоритмом ?
Catstail
Модератор
 Аватар для Catstail
21435 / 10220 / 1666
Регистрация: 12.02.2012
Сообщений: 17,095
27.05.2012, 08:45     Зачем нужен стек и очередь #10
Стек - важнейшая структура данных. Используется при обходе графов (вообще любых структур, задаваемых рекурсивно - файловой системы, например). Еще одно применение - вычисление (или трансляция) алгебраических выражений.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
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++ Очередь и стек

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

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

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

Текущее время: 09:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru