Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
zewer
1587 / 1211 / 149
Регистрация: 07.01.2011
Сообщений: 7,759
Завершенные тесты: 1
#1

вопрос по стеках (stack) - C++

06.11.2011, 01:12. Просмотров 1491. Ответов 17
Метки нет (Все метки)

Задание:
Реализовать стек с помощью массива data [N], в котором последний элемент массива, а не отдельная переменная, используеться для хранения указателя вершины стека, а остальные элементы массива могут содержать элементы самого стека. После обработки всей заданной входной последовательности превратить полученный стек так, чтобы он не содержал одинаковых элементов, идущих подряд (т.е. вместо каждой последовательности одинаковых элементов должен остаться только один элемент, например, из стека с содержанием 22230115555 надо получить стек с содержанием 23 015).

кто может, помогите по написанию кода, я вот придумал такой алгоритм, но в причине отсуствие синтаксисчних навиков, мне тяжело его реализировать:
например наш стек содержит такие елементи 22230115555, помня что в стеку елементи идут с права на лево, тоесть так:
5
5
5
5
1
..
ми будем перемещать елементи в другой стек, при умове, что если встретиться елемент, которий равний предидущему, то его ми перекидивать не будем, так ми получим стек с такими елементами
5
1
0
3
2
дальше ми опять перекинем назад, чтоб получился стек с елементами:
2
3
0
1
5
вот и все, ето мой алгоритм, кто хорошо знает синтаксис, наберите плс, буду благодарен, в доказ того что я не тупой, дам то что набрал сам, тоесть проверял роботу стека:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stack>
#include <iostream>
using namespace std;
int main()
{
setlocale (LC_ALL, "");
int i = 0;
int value;
const int x_size = 11;
stack< int > intStack;
intStack.empty();
int x[x_size]={4, 4, 4, 4, 5, 5, 2, 2, 2, 1, 1}; // заповнення стеку
for ( ; i < x_size; ++i )
    intStack.push( i[ x ] );
 
intStack.pop();
value = intStack.size();
 
 
cout << "результат " << value << endl;
}
Наперед спасибо, я понимаю что очень многа текста

Добавлено через 1 час 49 минут
неужели никто не знает стек??????
не могу в такое поверить...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2011, 01:12
Я подобрал для вас темы с готовыми решениями и ответами на вопрос вопрос по стеках (stack) (C++):

Есть ли связь между STL-stack и stack - высокопроизводительная память?
Куча источников, как всегда много отсебятины, в общем я запутался...

Указатели в стеках
Есть структура стека есть две функции - добавления элемента в стек и удаления...

Подсчитать общее число элементов в стеках
Здравствуйте. Пожалуйста, как можно проще, не используя классы, помогите решить...

Ошибка: "Unhandled exception: Stack cookie instrumentation code detected a stack-based buffer overrun"
Не могу понять почему значение ChoiceOfPlayer меняется и почему NumberOfRow и...

Как проинициализировать std::stack<const int> obj ( std::stack<int>{} );
добрый день. вопрос в коде: http://rextester.com/VCVVML6656 #include...

Очередь, теория. Очередь на шести стеках
Здравствуйте, пытаюсь побольше найти информации про очереди и их применение в...

17
soon
2545 / 1310 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.11.2011, 01:18 #2

Не по теме:

Хм. Мне стало скучно, и я реализовал свой стек с блекджек... Ну вы поняли.


Алгоритм в самом конце, в функции main. Вроде должен работать. Перемещать из второго стека в главный не стал, если надо - допилите, напильник прилагается.
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <iomanip>
 
const int STEP = 10;
 
template <typename T>
class Stack
{
public:
    Stack();
    Stack(int); 
    ~Stack();
    void push(T);
    T pop();
    int getSize();
    
private:
    T *stack;
    int size;
    int count;
};
 
template <typename T>
Stack<T>::Stack() : size(STEP), count(0)
{
    stack = new T [size];
}
 
template <typename T>
Stack<T>::Stack(int n) : size(n), count(0)
{
    stack = new T [size];
}
 
template <typename T>
Stack<T>::~Stack()
{
    delete[] stack;
}
 
template <typename T>
void Stack<T>::push(T num)
{
    if(++count != size)
        stack[count - 1] = num;
    else
    {
        T *buf = new T [size + STEP];
        for(int i = 0; i < size; ++i)
            buf[i] = stack[i];
        delete[] stack;
        stack = new T [size + STEP];
        for(int i = 0; i < size; ++i)
            stack[i] = buf[i];
        delete[] buf;
        size += STEP;
        stack[count - 1] = num;
    }
}
 
template <typename T>
T Stack<T>::pop()
{
    return stack[--count];
}
 
template <typename T>
int Stack<T>::getSize()
{
    return count;
}
 
int main()
{
    Stack<float> stack;
    float tmp;
    while(std::cin >> tmp)
        stack.push(tmp);
    if(stack.getSize() == 0)
        return 0;
    
    Stack<float> buf;
    float a, b;
    while(stack.getSize() > 0)
    {
        if(stack.getSize() == 1)
        {
            buf.push(stack.pop());
            break;
        }
        
        a = stack.pop();
        do
            b = stack.pop();
        while((stack.getSize() > 0) && (a == b));
        
        buf.push(a);
        if(a != b)
            stack.push(b);
    }
 
    //Begin of напильник. Заменить им вывод стека.
    //while(buf.getSize() > 0)
    //    stack.push(buf.pop());
    //while(stack.getSize() > 0)
    //    std::cout << stack.pop() << std::setw(6);
    //End of напильник
    
    while(buf.getSize() > 0)
        std::cout << buf.pop() << std::setw(6);
    
    return 0;
}
}
0
zewer
1587 / 1211 / 149
Регистрация: 07.01.2011
Сообщений: 7,759
Завершенные тесты: 1
06.11.2011, 01:38  [ТС] #3
спасибо, щас посмотрю...
но я забил написать коечто, мммммм, не нужно использовать размер (size), тоесть я должен сделать, не используя его
0
soon
2545 / 1310 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.11.2011, 01:46 #4
Получится немного корявее, но нет ничего невозможного. Хотя, укусить себя за лоб будет сложновато... Но речь не о том.
Либо нужно попросить пользователя ввести количество чисел, либо отслеживать количество введенных чисел непосредственно при вводе. Затем, везде где будет использоваться push увеличивать size на единицу, а там где pop уменьшать. Разумеется, это должны быть 2 различные переменные для stack и buf(в моем случае).
0
zewer
1587 / 1211 / 149
Регистрация: 07.01.2011
Сообщений: 7,759
Завершенные тесты: 1
06.11.2011, 01:52  [ТС] #5
Цитата Сообщение от soon Посмотреть сообщение
Получится немного корявее, но нет ничего невозможного. Хотя, укусить себя за лоб будет сложновато... Но речь не о том.
Либо нужно попросить пользователя ввести количество чисел, либо отслеживать количество введенных чисел непосредственно при вводе. Затем, везде где будет использоваться push увеличивать size на единицу, а там где pop уменьшать. Разумеется, это должны быть 2 различные переменные для stack и buf(в моем случае).
а если использовать так:
берем самий верхний елемент и переносим его в другой стек, и сразу проверяем, не пустой ли наш основной стек, если он не пустой, то повторяем дальше
ну типу чтото data[used];
data [used - 1];
или не поканает?
и кста, можно делать ли подобние операции со стеками без использование шаблона?
0
soon
2545 / 1310 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.11.2011, 11:04 #6
Цитата Сообщение от zewer Посмотреть сообщение
берем самий верхний елемент и переносим его в другой стек, и сразу проверяем, не пустой ли наш основной стек, если он не пустой, то повторяем дальше
ну типу чтото data[used];
data [used - 1];
Не догнал, если честно. Можете непосредственно на коде показать?
0
zewer
1587 / 1211 / 149
Регистрация: 07.01.2011
Сообщений: 7,759
Завершенные тесты: 1
06.11.2011, 22:36  [ТС] #7
можно ли сделать стек без использование шаблонов, а только на основе статического массива?????
просто в задание написано сделать на основе статического массива, дайте ответ да или нет, если без шаблона то походу сделаю норм
0
soon
2545 / 1310 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.11.2011, 23:09 #8
можно ли сделать стек без использование шаблонов, а только на основе статического массива?????
Разумеется, только размер стека будет ограничен.
Я не понял касательно алгоритма.
а если использовать так:
берем самий верхний елемент и переносим его в другой стек, и сразу проверяем, не пустой ли наш основной стек, если он не пустой, то повторяем дальше
ну типу чтото data[used];
data [used - 1];
или не поканает?
И алгоритм ли это вообще?
0
zewer
1587 / 1211 / 149
Регистрация: 07.01.2011
Сообщений: 7,759
Завершенные тесты: 1
06.11.2011, 23:50  [ТС] #9
как раз все прекрасно, спасибо
на счет data [used] , я просто нарил такую фигню - походу ето бред
а на счет алгоритма без использование size, то походу может подойти такой:
после каждого переноса елемента делать проверку на то, не пустой ли стек, если не пустой, продолжать перенос, а если пустой - то остановить перенос
как то так, вроде и реализовать не сложно
0
hepr
61 / 33 / 13
Регистрация: 21.10.2010
Сообщений: 538
07.11.2011, 17:22 #10
Блин, не туда скинул))
0
Chelioss
07.11.2011, 17:43
  #11

Не по теме:

Как перебрать все элементы стэка? Итераторы ведь не поддерживаются.

0
LosAngeles
Заблокирован
07.11.2011, 17:46 #12
стек лифо - ласт инпут фёст аут, как бы не подразумевает произвольного доступа, зачем ему итератор
0
Chelioss
181 / 181 / 21
Регистрация: 08.01.2011
Сообщений: 1,139
07.11.2011, 17:56 #13
Цитата Сообщение от LosAngeles Посмотреть сообщение
стек лифо - ласт инпут фёст аут, как бы не подразумевает произвольного доступа, зачем ему итератор
Я хочу узнать как просмотреть все элементы, не удаляя их. Такое вот задание в ВУЗе дали.
0
zek921
9 / 9 / 2
Регистрация: 30.04.2011
Сообщений: 130
Записей в блоге: 1
07.11.2011, 18:03 #14
допустим,массив .От 0 до длина -1 .Итерация с помощью for,while ...if
for(int i =0;i<x_size ;i++){cout<<x[i];}

а добавлять / удалять элементы - с конца.
0
Chelioss
181 / 181 / 21
Регистрация: 08.01.2011
Сообщений: 1,139
07.11.2011, 18:42 #15
Цитата Сообщение от zek921 Посмотреть сообщение
допустим,массив .От 0 до длина -1 .Итерация с помощью for,while ...if
for(int i =0;i<x_size ;i++){cout<<x[i];}
а добавлять / удалять элементы - с конца.
А ничего, что стэк не поддерживает операцию индексации?
0
LosAngeles
Заблокирован
07.11.2011, 18:49 #16
Цитата Сообщение от Chelioss Посмотреть сообщение
А ничего, что стэк не поддерживает операцию индексации?
значит снова возвращаемся к итераторам, или пишем сишной структуркой, там инкапсуляции нет, можешь просматривать стек хоть наискосок
0
Chelioss
181 / 181 / 21
Регистрация: 08.01.2011
Сообщений: 1,139
07.11.2011, 19:00 #17
Цитата Сообщение от LosAngeles Посмотреть сообщение
значит снова возвращаемся к итераторам
Вы же сами сказали, что итераторы не поддерживаются.
Цитата Сообщение от LosAngeles Посмотреть сообщение
или пишем сишной структуркой, там инкапсуляции нет, можешь просматривать стек хоть наискосок
В смысле самому что ли стэк реализовать?

Загвоздка в том, что в задании, которое дали в ВУЗе, надо сделать собственный стэк и использовать в программе свой и стандартный стэк. Со своим как раз проблемы нет.
0
zek921
9 / 9 / 2
Регистрация: 30.04.2011
Сообщений: 130
Записей в блоге: 1
07.11.2011, 19:14 #18
ой ,та но здоровье ,вытягиваем содержимое поштучно куда - нибудь ,выполняем какие - нибудь действия ,запихиваем обратно (учитываем ,что берем с конца ,получим последовательность обратную начальной). Я понимаю ,правила и всё такое ,но в в реализации ,всё-же , возможность доступа произвольному (ReadOnly) элемента стека очень полезна .Мне помогала .Когда нужно работать с объектом как со стеком я выполняю пуш и поп ,больше от стека ,как хранилища особым образом организованного ,ничего и не требуется .Хз ,не очень выразил свою мысль ,наверное ,сорри .

Добавлено через 1 минуту
C++
1
2
int len = stack.Length;
for(int i =0;i<len;i++){cout<<stack.Pop();}

не удаляя - вытащенный элемент кидаем в другой стек .
Потом заполняем первый на основе данных нашего вспомогательного

Добавлено через 3 минуты
Натупил ,забыл что речь идет о стандартной реализации стека ,думал о стеках в общем и своем варианте реализации


length to getLen как заменить думаю и так понятно
1
07.11.2011, 19:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2011, 19:14
Привет! Вот еще темы с решениями:

stack
не могу норм прокомпилировать прогу, вот код, подскажите что не так! #include...

Stack и указатели c++
Есть следующий Стэк #ifndef _LINKED_STACK #define _LINKED_STACK #include...

Реализация stack
Задание реализовать stack, первым делом написал добавление элемента и показ...

Stack overflow
Реализовал структуру данных стек на связном списке, очистку решил возложить на...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

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