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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
zewer
1092 / 783 / 77
Регистрация: 07.01.2011
Сообщений: 5,770
#1

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

06.11.2011, 01:12. Просмотров 1409. Ответов 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 минут
неужели никто не знает стек??????
не могу в такое поверить...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2011, 01:12     вопрос по стеках (stack)
Посмотрите здесь:

C++ STL stack
C++ stack, потоки
stack C++
C++ Указатели в стеках
C++ Есть ли связь между STL-stack и stack - высокопроизводительная память?
Stack overflow C++
C++ Класс stack
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
2537 / 1302 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.11.2011, 01:18     вопрос по стеках (stack) #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;
}
}
zewer
1092 / 783 / 77
Регистрация: 07.01.2011
Сообщений: 5,770
06.11.2011, 01:38  [ТС]     вопрос по стеках (stack) #3
спасибо, щас посмотрю...
но я забил написать коечто, мммммм, не нужно использовать размер (size), тоесть я должен сделать, не используя его
soon
2537 / 1302 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.11.2011, 01:46     вопрос по стеках (stack) #4
Получится немного корявее, но нет ничего невозможного. Хотя, укусить себя за лоб будет сложновато... Но речь не о том.
Либо нужно попросить пользователя ввести количество чисел, либо отслеживать количество введенных чисел непосредственно при вводе. Затем, везде где будет использоваться push увеличивать size на единицу, а там где pop уменьшать. Разумеется, это должны быть 2 различные переменные для stack и buf(в моем случае).
zewer
1092 / 783 / 77
Регистрация: 07.01.2011
Сообщений: 5,770
06.11.2011, 01:52  [ТС]     вопрос по стеках (stack) #5
Цитата Сообщение от soon Посмотреть сообщение
Получится немного корявее, но нет ничего невозможного. Хотя, укусить себя за лоб будет сложновато... Но речь не о том.
Либо нужно попросить пользователя ввести количество чисел, либо отслеживать количество введенных чисел непосредственно при вводе. Затем, везде где будет использоваться push увеличивать size на единицу, а там где pop уменьшать. Разумеется, это должны быть 2 различные переменные для stack и buf(в моем случае).
а если использовать так:
берем самий верхний елемент и переносим его в другой стек, и сразу проверяем, не пустой ли наш основной стек, если он не пустой, то повторяем дальше
ну типу чтото data[used];
data [used - 1];
или не поканает?
и кста, можно делать ли подобние операции со стеками без использование шаблона?
soon
2537 / 1302 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.11.2011, 11:04     вопрос по стеках (stack) #6
Цитата Сообщение от zewer Посмотреть сообщение
берем самий верхний елемент и переносим его в другой стек, и сразу проверяем, не пустой ли наш основной стек, если он не пустой, то повторяем дальше
ну типу чтото data[used];
data [used - 1];
Не догнал, если честно. Можете непосредственно на коде показать?
zewer
1092 / 783 / 77
Регистрация: 07.01.2011
Сообщений: 5,770
06.11.2011, 22:36  [ТС]     вопрос по стеках (stack) #7
можно ли сделать стек без использование шаблонов, а только на основе статического массива?????
просто в задание написано сделать на основе статического массива, дайте ответ да или нет, если без шаблона то походу сделаю норм
soon
2537 / 1302 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.11.2011, 23:09     вопрос по стеках (stack) #8
можно ли сделать стек без использование шаблонов, а только на основе статического массива?????
Разумеется, только размер стека будет ограничен.
Я не понял касательно алгоритма.
а если использовать так:
берем самий верхний елемент и переносим его в другой стек, и сразу проверяем, не пустой ли наш основной стек, если он не пустой, то повторяем дальше
ну типу чтото data[used];
data [used - 1];
или не поканает?
И алгоритм ли это вообще?
zewer
1092 / 783 / 77
Регистрация: 07.01.2011
Сообщений: 5,770
06.11.2011, 23:50  [ТС]     вопрос по стеках (stack) #9
как раз все прекрасно, спасибо
на счет data [used] , я просто нарил такую фигню - походу ето бред
а на счет алгоритма без использование size, то походу может подойти такой:
после каждого переноса елемента делать проверку на то, не пустой ли стек, если не пустой, продолжать перенос, а если пустой - то остановить перенос
как то так, вроде и реализовать не сложно
hepr
61 / 33 / 5
Регистрация: 21.10.2010
Сообщений: 539
07.11.2011, 17:22     вопрос по стеках (stack) #10
Блин, не туда скинул))
Chelioss
07.11.2011, 17:43
  #11

Не по теме:

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

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

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

Загвоздка в том, что в задании, которое дали в ВУЗе, надо сделать собственный стэк и использовать в программе свой и стандартный стэк. Со своим как раз проблемы нет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2011, 19:14     вопрос по стеках (stack)
Еще ссылки по теме:

Ошибка: "Unhandled exception: Stack cookie instrumentation code detected a stack-based buffer overrun" C++
Подсчитать общее число элементов в стеках C++
Контейнер stack C++
C++ Реализация stack
Stack.top в c++ C++

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

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

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

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

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


length to getLen как заменить думаю и так понятно
Yandex
Объявления
07.11.2011, 19:14     вопрос по стеках (stack)
Ответ Создать тему
Опции темы

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