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

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

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

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

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

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

C++ Стек и очередь
стек и очередь C++
C++ Стек и очередь
C++ Список, стек и очередь.
Контейнерные классы: стек и очередь C++
стек и очередь C++
Очередь, стек, дерево? (реализация) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
7037 / 5214 / 259
Регистрация: 10.12.2010
Сообщений: 22,904
Записей в блоге: 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
7037 / 5214 / 259
Регистрация: 10.12.2010
Сообщений: 22,904
Записей в блоге: 17
26.05.2012, 23:55     Зачем нужен стек и очередь #4
О чем ты programina?
gray_fox
What a waste!
 Аватар для gray_fox
1250 / 1133 / 54
Регистрация: 21.04.2012
Сообщений: 2,357
Завершенные тесты: 3
26.05.2012, 23:59     Зачем нужен стек и очередь #5
programina О_о интересно...

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

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

Добавлено через 1 минуту
Цитата Сообщение от Avazart Посмотреть сообщение
О чем ты programina?
Она путает понятия "стек как алгортимический инструмент" и "стек как аппаратный механизм для обеспечения процедурных вызовов"
Avazart
 Аватар для Avazart
7037 / 5214 / 259
Регистрация: 10.12.2010
Сообщений: 22,904
Записей в блоге: 17
27.05.2012, 00:30     Зачем нужен стек и очередь #7
Ну вообще можно сказать что эти вещи -хранилища элементов, но в отличии от массивов,векторов итп очень ограниченые по доступу к элементам.
diagon
Higher
 Аватар для diagon
1921 / 1187 / 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,893
Записей в блоге: 1
27.05.2012, 08:08  [ТС]     Зачем нужен стек и очередь #9
Правильно ли я понимаю, что стек нужен решение алгоритмом ?
Catstail
Модератор
 Аватар для Catstail
21780 / 10504 / 1705
Регистрация: 12.02.2012
Сообщений: 17,507
27.05.2012, 08:45     Зачем нужен стек и очередь #10
Стек - важнейшая структура данных. Используется при обходе графов (вообще любых структур, задаваемых рекурсивно - файловой системы, например). Еще одно применение - вычисление (или трансляция) алгебраических выражений.
ValeryS
Модератор
6449 / 4915 / 451
Регистрация: 14.02.2011
Сообщений: 16,298
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
 Аватар для Evg
17179 / 5433 / 336
Регистрация: 30.03.2009
Сообщений: 14,720
Записей в блоге: 26
27.05.2012, 13:37     Зачем нужен стек и очередь #12
Цитата Сообщение от diagon Посмотреть сообщение
Как раз в поиске в ширину используется очередь
Угу... вечером голова совсем не варила...

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

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