Что такое стеки и очереди? [закрыт]

#cpp #очередь #стек

        
             
                
                    
                        
                            Закрыт. Данный вопрос необходимо конкретизировать. Ответы
на него в данный момент не принимаются.
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Переформулируйте вопрос,
чтобы он был сосредоточен только на одной проблеме, отредактировав его.
                        
                        Закрыт 9 месяцев назад.
                                                                                
           
                
        
Учусь на втором курсе, программирование, C++. Расскажите, пожалуйста, о стеках. Как
пишется программа?
    

Ответы

Ответ 1

Стек - структура данных с доступом к элементам по принципу LIFO (Last In First Out
- Последний пришел - первый вышел). Данные добавляются в начало (конец, кому как удобно),
оттуда же и извлекаются. Для реализации данной структуры достаточно иметь лишь две
функции и указатель на верхушку:
push(item); //добавляет данные в стек
pop(); //извлекает последний элемент

Очередь - структура данных с доступом к элементам по принципу FIFO (First In First
Out - Первый пришел - Первый вышел). Данные добавляются в конец, а извлекаются из начала.
Для быстрого добавления и извлечения данных понадобится два указателя, один на начало,
очереди, второй на ее конец. Для работы с очередью используются функции:
enqueue(item); //добавляет новый элемент в очередь
dequeue(); //извлекает элемент из очереди

Для работы с указателями в C++ вам необходимо ознакомиться, например, с данной статьей
(одна из первых в поиске).
Затем, вам необходимо создать элемент данных вашего стека (очереди). Например:
struct data {
    int p;
    int c;
}

После этого обзавестись ячейкой стека. Например:
struct element {
 data element_data;
 element *next; //указатель на следующий элемент
}

Указатель на следующий элемент необходим дабы наши данные в стеке (очереди) имели
некоторую последовательность и были как-то связаны между собой.
После этого пишете необходимые функции, обзаводитесь указателями на начало (и конец,
при необходимости). Например для push():
//somewhere in the code
element *top; //инициализируется в NULL
//...
void push(data newData) {
 //создаем нашу структуру element и указатель на нее
 element *newElement = new element();
 //element_data = newData
 element->element_data = newData;
 //next = top - здесь мы и задаем связку между двумя элементами стека
 element->next = top;
 //top = указателю на нашу структуру
 top = newElement;
}

Все остальное по аналогии. На C++ давненько я не кодил (проверить негде), поэтому
прошу заранее прощения всех гуру, поправьте если где напортачил.


Ответ 2

Я бы описал стэк как упаковку с коллекцией монеток, уложеных в стопочку. С 1 до 10.
Что бы получить доступ к 5, нужно снять 10, потом 9, 8, 7, 6 и только потом получим
5-ю. Ну это лично моё ИМХО, когда то мне было проще запомнить так. В остальном остаются
только технические вопросы, и я не могу не согласится с Dex'ом...