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

Стек! - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 48, средняя оценка - 4.77
murod
 Аватар для murod
-2 / 7 / 2
Регистрация: 04.11.2010
Сообщений: 163
02.08.2011, 11:32     Стек! #1
Реализуйте структуру данных "стек". Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.

Размер стека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.

Я не понял как использовать здесь динамическое выделение памяти , еще и размер, может кто поможет
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
02.08.2011, 11:42     Стек! #2
murod, это баян, имейте совесть, пользуйтесь поиском
murod
 Аватар для murod
-2 / 7 / 2
Регистрация: 04.11.2010
Сообщений: 163
02.08.2011, 11:43  [ТС]     Стек! #3
так трудно да ответить тут ,?
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
02.08.2011, 11:44     Стек! #4
Цитата Сообщение от murod Посмотреть сообщение
Я не понял как использовать здесь динамическое выделение памяти , еще и размер, может кто поможет
а сдесь что непонятно, мы ж не знаеим сколько элементов пользователь захочет запихнуть в стек, потому память нужно выделять динамически

Цитата Сообщение от murod Посмотреть сообщение
так трудно да ответить тут ,?
трудно, ибо на форуме даже тема была, в которой выложены стеки, деки, очереди от самых элементарных реализаций до реализаций с аллокатором и итератором
LosAngeles
Заблокирован
02.08.2011, 11:44     Стек! #5
это кроме того его баян. Ничего не напоминает?
CТЕК !

я и вполне рабочий стек там набросал? не проверял конечно. Но там воистину сложно ошибиться
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <deque>
#include <string>
#include <stdexcept>
 
 
template <typename T, typename C = std::deque<T> >
        class stack
{   
    C c;
public:
    void    pop();
    void    push(T const&);
    T       top() const;
    size_t  size() const;
    void    clear();
 
};
 
 
 
template <typename T, typename C>
        inline void stack<T, C>::push(T const& rhs)
{
    c.push_back(rhs);
}
 
 
 
template <typename T, typename C>
        inline void stack<T, C>::pop()
{
    if (!c.size()) throw (std::underflow_error("}I{0na"));
    c.pop_back();
}
 
 
 
template <typename T, typename C>
        inline T stack<T, C>::top() const
{
    return c.back();
}
 
 
template <typename T, typename C>
        inline size_t stack<T, C>::size() const
{
    return c.size();
}
 
 
template <typename T, typename C>
        inline void stack<T, C>::clear()
{
    c.clear();
}
murod
 Аватар для murod
-2 / 7 / 2
Регистрация: 04.11.2010
Сообщений: 163
02.08.2011, 11:46  [ТС]     Стек! #6
вы мне этот динамический память как описать напишите а там как нибудь справлюсь
LosAngeles
Заблокирован
02.08.2011, 11:49     Стек! #7
если ты с циклами и iostream умеешь работать, то написание проги с этим стеком не должно вызвать серьёзных затруднений

Добавлено через 1 минуту
new\delete или std::allocator если ты хочешь с нуля писать
murod
 Аватар для murod
-2 / 7 / 2
Регистрация: 04.11.2010
Сообщений: 163
02.08.2011, 11:50  [ТС]     Стек! #8
Мда я забыл сказать что я ток вчера понял что такое СТЕК ?
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
02.08.2011, 11:56     Стек! #9
murod, а способ реализации не задается? На массиве или на списке?
А то можно и стандартный стек использовать...
murod
 Аватар для murod
-2 / 7 / 2
Регистрация: 04.11.2010
Сообщений: 163
02.08.2011, 11:57  [ТС]     Стек! #10
ValeryLaptev, на массиве
LosAngeles
Заблокирован
02.08.2011, 11:58     Стек! #11
deleted
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
02.08.2011, 12:01     Стек! #12
Цитата Сообщение от murod Посмотреть сообщение
Мда я забыл сказать что я ток вчера понял что такое СТЕК ?
Не... Ты это всегда знал, только не знал, что это именно таким страшным словом называется... Магазин патронов у автомата или пистолета - это стек...
murod
 Аватар для murod
-2 / 7 / 2
Регистрация: 04.11.2010
Сообщений: 163
02.08.2011, 12:03  [ТС]     Стек! #13
так я получу ответ на свой главный вопрос ? т. е о задаче ?
LosAngeles
Заблокирован
02.08.2011, 12:06     Стек! #14
в виде списка стеков полно и на этом форуме, а в виде массива только если фиксированного размера найдёшь примеры
murod
 Аватар для murod
-2 / 7 / 2
Регистрация: 04.11.2010
Сообщений: 163
02.08.2011, 12:09  [ТС]     Стек! #15
почему у меня репутация отрицательная ??

Добавлено через 14 секунд
за что меня так ?
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
02.08.2011, 12:10     Стек! #16
Списки, стеки, очереди
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
02.08.2011, 12:35     Стек! #17
Цитата Сообщение от murod Посмотреть сообщение
так я получу ответ на свой главный вопрос ? т. е о задаче ?
Вот тебе про реализацию динамического массива. Тут много дополнительного, ченго тебе не нужно. Ну так ломать - не строить, выкинешь.


Динамический массив

Чтобы разобраться в этом вопросе, давайте снова реализуем динамический массив, но с переменным количеством элементов. Нумерация элементов, как обычно, должна начинаться с 0, а добавление элементов осуществляется только в конец массива. Нам нужно рассмотреть несколько вопросов:
1. Какой объем памяти выделять первоначально, если размер контейнера не указан.
2. Если при добавлении элемента выясняется, что места в контейнере нет, то какой объем выделять дополнительно.

Кроме того, нужно подумать и об эффективности реализации. Дело в том, что если при добавлении нового элемента требуется изменение размера динамического массива, то это потребует перезаписи всех существующих элементов. Операция добавления элемента в этом случае должна выделить новый динамический массив нужного размера, переписать в него содержимое старого динамического массива и уничтожить старый массив. Очевидно, делать это нужно как можно реже.

Ответ на первый вопрос достаточно прост: сколько хотите, столько и выделяйте — никакого «специального» количества не существует. Можно выделить даже 0 элементов, так как это разрешено стандартом. Но обычно выделяют некоторое минимальное количество памяти, например, для 10 или 100 элементов.

Ответа на второй вопрос только три:
 выделять столько памяти, чтобы размер динамического массива всегда точно соответствовал количеству элементов в нем. При таком подходе память расходуется очень эффективно — никакого лишнего расхода. Однако это означает, что при каждом добавлении элемента требуется перезапись n элементов массива.
 увеличивать размер динамического массива с некоторым фиксированным шагом (количеством элементов) m, например 10 или 32. Очевидно, память расходуется достаточно эффективно — пустым остается небольшой объем. И перезаписи требуются реже — один раз на каждые m добавлений элементов.
 увеличивать размер динамического массива экспоненциально, выделяя каждый раз не меньше памяти, чем текущий размер массива. Например, в массиве 100 элементов, тогда новый динамический массив должен вмещать не менее 200 элементов. При следующем увеличении выделяется новая память для 400 элементов. Если принять текущий размер за 1, то коэффициент увеличения тоже равен 1, а размер нового массива равен sizeof(старый массив)*(1+1). При таком подходе память в значительной мере пустует. Однако, как пишет Герб Саттер [21, задача 7.2], такая стратегия существенно снижает необходимость перезаписи элементов — настолько существенно, что он рекомендует пренебречь дополнительным расходом памяти. Со ссылкой на Эндрю Кенига Саттер сообщает, что наилучший коэффициент увеличения массива должен быть близок к 1.5. Таким образом,
размер нового массива = sizeof(старый массив)*(1+1.5)
Поверим Гербу Саттеру и перепишем класс SimpleArray (см. листинг 7.4) как шаблон TArray, реализовав последнюю стратегию выделения памяти. Добавим также последовательный доступ с помощью итераторов. Таким образом, класс-шаблон нашего массива может выглядеть так (листинг 9.1).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
Листинг 9.1. Интерфейс динамического массива с изменяемым размером
template<typename T> 
class TArray {
public:
  // типы
  typedef T                                     value_type;            
  typedef T*                                    iterator;              
  typedef const T*                              const_iterator;        
  typedef T&                                    reference;             
  typedef const T&                              const_reference;       
  typedef std::size_t                           size_type;             
  // конструкторы/копирование/деструктор
  TArray(const size_type& n = minsize);
  TArray(const TArray<T>& array);
  template <class Iterator> TArray(Iterator first, Iterator last);
  ~TArray() { delete [] elems; elems = 0; }
  Tarray<T>& operator=(const TArray<T>&);
  template<typename U> TArray& operator=(const TArray<U>&);
// итераторы
  iterator begin() { return elems; }
  const_iterator begin() const { return elems; }
  iterator end() { return elems+Count; }
  const_iterator end() const { return elems+Count; }
// размеры
  size_type size() const                // длина массива
  { return Count; }
  bool empty() const                    // есть ли элементы
  { return (Count == 0); }
  size_type capacity() const            // потенциальный размер
  { return Size; }
  void resize(size_type newsize);       // изменить размер
// доступ к элементам
  reference operator[](size_type)
  { rangecheck(i);                      // проверка индекса
    return elems[i]; 
  }
  const_reference operator[](size_type) const 
  { rangecheck(i);                      // проверка индекса
    return elems[i]; 
  }
  reference front() { return elems[0]; }
  const_reference front() const { return elems[0]; }
  reference back() { return elems[size()-1]; }
  const_reference back() const { return elems[size()-1]; }  
// методы-модификаторы
  void push_back(const T& v);
  void pop_back()                        // удалить последний элемент
  { if (!empty()) --Count; 
    else throw std::domain_error("array<>: empty array!");
  }
  void clear() { Count = 0; }           // очистить массив
  void swap(TArray<T>& other)           // обменять с другим массивом
  {  std::swap(elems, v.elems);         // стандартная функция обмена
     std::swap(Size, v.Size);
     std::swap(Count, v.Count);
  }
  void assign(const T& v)               // заполнить массив
  { if (!empty()) 
      for(size_type i = 0; i < Count; ++i) 
          elems[i] = v;
  } 
private:
  static const size_type minsize = 10;  // минимальный размер массива
  size_type Size;                       // выделено элементов в памяти
  size_type Count;                      // количество элементов
  value_type * elems;                   // указатель на данные
// проверка индекса
    void rangecheck (size_type i) 
    { if (i >= size()) 
        throw std::range_error("array<>: index out of range");
    }
};
// обмен – внешняя функция
template<typename T> void swap(TArray<T>&, TArray<T>&)
inline void swap(TArray<T>& x, TArray<T>& y)
{ x.swap(y); }
// сравнения
template<typename T> 
bool operator==(const TArray<T>& x, const TArray<T>& y)
{ if (x.size() == y.size())
  { for(size_type i = 0; i < x.size(); ++i) 
        if (x[i]!=y[i]) return false;
    return true;
  }
  else return false;
}
template<typename T> 
bool operator!=(const TArray<T>& x, const TArray<T>& y)
{ return !(x==y); }
Такой массив называется растущим, так как элементы добавляются только к его концу: массив «растет». В начале класса-шаблона, как обычно, заданы определения типов. Заменив double на любой другой встроенный числовой тип, получим реализацию динамического массива для другого типа. Реализацию методов при этом переписывать не требуется, поскольку они реализованы в терминах объявленных типов.

Большинство методов очень просты, поэтому реализованы непосредственно в классе. Операции доступа по индексу используют для проверки индекса ту же приватную функцию rangecheck(), что и в классе SimpleArray (см. листинг 7.4).

В классе три поля: указатель на выделенную память elems, поле Size определяет количество зарезервированных элементов, а поле Count содержит количество присутствующих в массиве элементов. Очевидно, что поле Count увеличивается по мере добавления элементов в массив. Как только значение поля Count сравняется со значением поля Size, необходимо выделять новую память.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// добавление элементов
template <class T>
void TArray<T>::push_back(const value_type& v)
{ if (Count == Size)                        // места нет
    resize(Size * 2);                       // увеличили «мощность»
  elems[Count++] = v;                       // присвоили
}
template <class T>
void TArray<T>::resize(size_type newsize)
{ if (newsize > capacity())
  { T *data = new T[newsize];               // новый массив
    for(size_type i = 0; i<Count; ++i)      // копируем
       data[i] = elems[i];
    delete[] elems;                         // возвращаем память
    elems = data;                           // вступили во владение
    Size = newsize;                         // «увеличили «мощность»
  }
}
Метод resize() предназначен для увеличения размера зарезервированной памяти. Уменьшить размер выделенной памяти нельзя. Работает он просто: резервируется память для нового массива большего размера, туда копируются элементы текущего массива, после чего «старая» память возвращается.

Метод push_back(), который добавляет элемент в конец массива, совсем простой. Пока количество элементов (поле Count) меньше зарезервированного количества (поле Size), значение просто заносится в очередной зарезервированный элемент, увеличивая количество элементов массива на 1. Если при очередном добавлении окажется, что Count == Size, то вызывается метод resize() для удвоения выделенной памяти. После этого аргумент заносится в следующий элемент массива.

Метод pop_back() удаляет последний элемент массива, а метод clear() очищает весь массив. Методы работают очень быстро, так как реально никакого удаления не происходит, просто корректируется значение поля Count. Удаление, естественно, может быть выполнено только в том случае, если в массиве есть хоть один элемент, иначе генерируется исключение. Так как массив может быть пустой, для проверки этого факта реализован метод empty().

Между прочим, метод добавления элемента в массив вполне можно было бы реализовать с помощью перегрузки операции +=. Тогда приведенный выше пример выглядит короче
m+=1; m+=1; m+=2; m+=2;m+=3;

Соответственно, для удаления элемента вполне подходит операция -=. Однако имена методов push_back() и pop_back() выбраны сознательно. Как мы увидим далее, реализованный нами шаблон растущего динамического массива очень похож на последовательный контейнер vector из стандартной библиотеки STL.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.08.2011, 16:05     Стек!
Еще ссылки по теме:

C++ Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами
Структура стек (: добавить элемент в стек, удалить элемент из стека, получить значение с вершины стека, размер стека...) C++
Переменные в стеке. Где хранятся? Как обрабатываются? Есть ли программный стек или только стек процессора? C++

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

Или воспользуйтесь поиском по форуму:
Deviaphan
02.08.2011, 16:05     Стек!
  #18

Не по теме:

Цитата Сообщение от murod Посмотреть сообщение
я забыл сказать что я ток вчера понял что такое СТЕК ?
Знак вопроса просто убил.))))))))))))))

Yandex
Объявления
02.08.2011, 16:05     Стек!
Ответ Создать тему

Метки
стек
Опции темы

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