Отсортировать элементы стека по возрастанию

@sdasdasda · Регистрация: 23.11.2016

Студворк — интернет-сервис помощи студентам

Здравствуйте) Помогите пожалуйста разобраться с задачей. Я недавно начала программировать(1 курс), осталось решить только 1 задачу для зачёта. Дан стек из целых числе. Используя только стеки, отсортировать элементы стека по возрастанию. На дне стека минимальный элемент, в вершине- максимальный. Решить задачу, используя класс для работы со стеком. Класс должен содержать методы добавления и удаления элементов из вершины стека. Напишите пожалуйста код программы с комментариями, чтобы я наконец разобралась. Заранее спасибо.

@Antikl · 20.05.2017, 15:58

//файл под названием stack.h

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
115
116
117
118
119
#ifndef STACK_H
#define STACK_H
 
#include <cassert> // для assert
#include <iostream>
 
#include <iomanip> // для setw
 
template <typename T>
class Stack
{
private:
    T *stackPtr;                      // указатель на стек
    const int size;                   // максимальное количество элементов в стеке
    int top;                          // номер текущего элемента стека
public:
    Stack(int = 10);                  // по умолчанию размер стека равен 10 элементам
    Stack(const Stack<T> &);          // конструктор копирования
    ~Stack();                         // деструктор
 
    inline void push(const T & );     // поместить элемент в вершину стека
    inline T pop();                   // удалить элемент из вершины стека и вернуть его
    inline void printStack();         // вывод стека на экран
    inline const T &Peek(int ) const; // n-й элемент от вершины стека
    inline int getStackSize() const;  // получить размер стека
    inline T *getPtr() const;         // получить указатель на стек
    inline int getTop() const;        // получить номер текущего элемента в стеке
};
 
// реализация методов шаблона класса STack
 
// конструктор Стека
template <typename T>
Stack<T>::Stack(int maxSize) :
    size(maxSize) // инициализация константы
{
    stackPtr = new T[size]; // выделить память под стек
    top = 0; // инициализируем текущий элемент нулем;
}
 
// конструктор копирования
template <typename T>
Stack<T>::Stack(const Stack<T> & otherStack) :
    size(otherStack.getStackSize()) // инициализация константы
{
    stackPtr = new T[size]; // выделить память под новый стек
    top = otherStack.getTop();
 
    for(int ix = 0; ix < top; ix++)
        stackPtr[ix] = otherStack.getPtr()[ix];
}
 
// функция деструктора Стека
template <typename T>
Stack<T>::~Stack()
{
    delete [] stackPtr; // удаляем стек
}
 
// функция добавления элемента в стек
template <typename T>
inline void Stack<T>::push(const T &value)
{
    // проверяем размер стека
    assert(top < size); // номер текущего элемента должен быть меньше размера стека
 
    stackPtr[top++] = value; // помещаем элемент в стек
}
 
// функция удаления элемента из стека
template <typename T>
inline T Stack<T>::pop()
{
    // проверяем размер стека
    assert(top > 0); // номер текущего элемента должен быть больше 0
 
    stackPtr[--top]; // удаляем элемент из стека
}
 
// функция возвращает n-й элемент от вершины стека
template <class T>
inline const T &Stack<T>::Peek(int nom) const
{
  //
  assert(nom <= top);
 
  return stackPtr[top - nom]; // вернуть n-й элемент стека
}
 
// вывод стека на экран
template <typename T>
inline void Stack<T>::printStack()
{
    for (int ix = top - 1; ix >= 0; ix--)
        cout << "|" << setw(4) << stackPtr[ix] << endl;
}
 
// вернуть размер стека
template <typename T>
inline int Stack<T>::getStackSize() const
{
    return size;
}
 
// вернуть указатель на стек (для конструктора копирования)
template <typename T>
inline T *Stack<T>::getPtr() const
{
    return stackPtr;
}
 
// вернуть размер стека
template <typename T>
inline int Stack<T>::getTop() const
{
    return top;
}
 
#endif // STACK_H

как использовать

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
#include <iostream>
 
using namespace std;
 
#include "stack.h"
 
int main()
{
    Stack<char> stackSymbol(5);
    int ct = 0;
    char ch;
 
    while (ct++ < 5)
    {
        cin >> ch;
        stackSymbol.push(ch); // помещаем элементы в стек
    }
 
    cout << endl;
 
    stackSymbol.printStack(); // печать стека
 
    cout << "\n\nУдалим элемент из стека\n";
    stackSymbol.pop();
 
    stackSymbol.printStack(); // печать стека
 
    Stack<char> newStack(stackSymbol);
 
    cout << "\n\nСработал конструктор копирования!\n";
    newStack.printStack();
 
    cout << "Второй в очереди элемент: "<< newStack.Peek(2) << endl;
 
    return 0;
}

@sdasdasda · 05.06.2017, 22:03 **[ТС]**

Antikl, и что по вашему делает эта программа? вы просто скопировали с этой ссылки код
http://cppstudio.com/post/5155/

@Antikl · 06.06.2017, 09:59

Сообщение от sdasdasda

и что по вашему делает эта программа

это класс для работы со стеком притом что он шаблоный можно любой тип использовать

Добавлено через 2 минуты
+ используйте функцию sort() для сортировки

@Геомеханик · 06.06.2017, 12:20

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <string>
#include <cstdlib>
 
template<typename T>
class tstack {
    struct node {
        node* next;
        T     val;
    };
private:
    node*  st;
    size_t cnt;
public:
    tstack(void) noexcept :st(nullptr), cnt(0) {}
    explicit tstack(const T* _f, const T* _l):st(nullptr), cnt(0){
        while(_f != _l)
            push(*_f++);
    }
 
    tstack(const tstack& s):st(nullptr), cnt(0){
        *this = s;
    }
 
    tstack(tstack&& s) noexcept : st(nullptr), cnt(0) {
        *this = std::forward<decltype(s)>(s);
    }
 
    ~tstack() noexcept { clear(); }
public:
    //добавить
    void push(const T& val){
        node* p = new node();
        p->val  = std::forward<decltype(val)>(val);
        p->next = st;
        st = p;
        ++cnt;
    }
 
    //удалить
    void pop(void) noexcept {
        if(cnt > 0){
            --cnt;
            node* t = st;
            st = st->next;
            delete t;
        }
    }
 
    //сортировка вставками по возрастанию
    void sort(void) noexcept {
        node* a, *b, *p, *h = nullptr;
        for(node* i = st; i != nullptr; ) {
            a = i;
            i = i->next;
            b = h;
            for(p = nullptr; (b != nullptr) && (b->val < a->val); ) {
                p = b;
                b = b->next;
            }
 
            if(p == nullptr){
                a->next = h;
                h       = a;
            } else {
                a->next = b;
                p->next = a;
            }
        }
 
        if(h != nullptr) 
            st = h;
    }
 
    //удаление всех
    void clear(void) noexcept {
        node* t;
        while(st != nullptr){
            t  = st;
            st = st->next;
            delete t;
        }
        cnt = 0;
    }
 
    T& top(void) noexcept { return st->val; }
    const T& top(void) const noexcept { return st->val; }
 
    size_t size(void) const  noexcept { return cnt; }
    bool   empty(void) const noexcept { return (st == nullptr); }
 
    tstack& operator = (tstack&& s) noexcept {
        if(this != &s){
            clear();
            st    = s.st;
            cnt   = s.cnt;
            s.st  = nullptr;
            s.cnt = 0;
        }
        return *this;
    }
    
    tstack& operator = (const tstack& s){
        if(this != &s){
            clear();
            //копируем
            for(const node* p = s.st; p != nullptr; p = p->next)
                push(p->val);
 
            //реверсируем
            node* t, *p = st, *h = nullptr;
            while(p != nullptr){
                t = p;
                p = p->next;
                
                t->next = h;
                h = t;
            }
            
            if(h != nullptr)
                st = h;
        }
        return *this;
    }
};
 
 
int main(void){
    tstack<int> s1;
    for(int i = 0; i < 16; ++i)
        s1.push(rand() % 10);
 
    std::cout << "count: " << s1.size() << std::endl;
    s1.sort();
    while(!s1.empty()){
        std::cout << s1.top() << ' ';
        s1.pop();
    }
    std::cout << std::endl;
 
    //...
 
    tstack<std::string> s2;
    s2.push("BBB");
    s2.push("AAA");
    s2.push("WWW");
    s2.push("CCC");
    s2.push("ZZZ");
    s2.sort();
    while(!s2.empty()){
        std::cout << s2.top() << std::endl;
        s2.pop();
    }
    std::cin.get();
    return 0;
}

MrGluck · 06.06.2017, 12:23

Из разряда "не надо так". Хотя задача сортировать стек сама по себе бредовая.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <algorithm>
#include <iostream>
#include <stack>
 
int main()
{
    std::stack<int> st {{1, 5, 3, 4, 2}};
    using cnt = decltype(st)::container_type;
    std::sort(reinterpret_cast<cnt*>(&st)->begin(), reinterpret_cast<cnt*>(&st)->end());
    while (!st.empty())
    {
        std::cout << st.top() << " ";
        st.pop();
    }
}

@zss · 06.06.2017, 12:47

Для класса stack нет функции sort.
Еее надо написать:

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
#include <iostream>
#include <stack>
using namespace std;
 
template<class T> 
void sort(stack<T>& s)
{
    stack<T> t1,t2;
    do
    {
        t1.push(s.top());
        s.pop();
        while(!s.empty())
        {
 
            if(s.top() > t1.top())
                t1.push(s.top());
            else
                t2.push(s.top());
            s.pop();
        }   
        while(!t1.empty()){
            s.push(t1.top());
            t1.pop();
        }       
        if(t2.empty())
            break;
        while(!t2.empty())
        {
            s.push(t2.top());
            t2.pop();
        }
 
    }while ( true );
}
int main(void)
{
    stack<int> s1;
    for(int i = 0; i < 16; ++i)
        s1.push(rand() % 100);
 
    std::cout << "count: " << s1.size() << std::endl;
    sort(s1);
    while(!s1.empty()){
        std::cout << s1.top() << ' ';
        s1.pop();
    }
    std::cout << std::endl;
 
    system("pause");
    return 0;
}

@ForEveR · 06.06.2017, 13:09

zss, Сортировать стек как уже сказано выше это такое себе.
Вместо ручной функции сортировки можно перенести стек в контейнер, отсортировать контейнер, вернуть элементы обратно в стек (еще конечно можно сделать класс sorted_stack наследник стека, тогда можно будет обойтись без копии, а сортировать контейнер в котором по факту хранятся данные).

Добавлено через 16 минут

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
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>
 
// first example
 
template<typename Stack>
Stack sort_stack(const Stack& st)
{
   Stack result = st;
   std::vector<typename Stack::value_type> cnt;
   while (!result.empty())
   {
      cnt.push_back(result.top());
      result.pop();
   }
   std::sort(cnt.rbegin(), cnt.rend());
   for (const auto& v : cnt)
   {
      result.push(v);
   }
   return result;
}
 
// second example
 
template<typename T>
class sorted_stack : public std::stack<T>
{
public:
   sorted_stack(const std::stack<T>& values) : std::stack<T>(values)
   {
      std::sort(this->c.rbegin(), this->c.rend());
   }
};
 
template<typename Stack>
Stack sort_stack2(const Stack& st)
{
   sorted_stack<typename Stack::value_type> stack(st);
   return stack;
}
 
int main()
{
   std::stack<int> values;
   values.push(5);
   values.push(1);
   values.push(2);
   values.push(0);
   values.push(10);
   values.push(7);
   std::stack<int> result1 = sort_stack(values);
   while (!result1.empty())
   {
      std::cout << result1.top() << " ";
      result1.pop();
   }
   std::cout << std::endl;
   std::stack<int> result2 = sort_stack2(values);
   while (!result2.empty())
   {
      std::cout << result2.top() << " ";
      result2.pop();
   }
   std::cout << std::endl;
}

@Sdettws · 06.06.2017, 16:42

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename _T>class MyStack : public std::stack<_T> {
public:
 
    template<typename _S> void sort(_S cmp) {
        std::sort(this->c.begin(), this->c.end(), cmp);
    }
 
    MyStack<_T>(const std::initializer_list<_T> & list) : std::stack<_T>(list) {
    }
};
 
int main(int argc, char** argv) {
 
    MyStack<int> st{1, 5, 3, 4, 2};
    st.sort(std::less<int>());
 
    while (!st.empty()) {
        std::cout << st.top() << " ";
        st.pop();
    };
}

@zss · 06.06.2017, 17:30

ForEveR, не спорю. Но у ТС было именно такое задание - отсортировать стек с использованием только стеков.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@sdasdasda 0 / 0 / 0 Регистрация: 23.11.2016 Сообщений: 14

	Отсортировать элементы стека по возрастанию 20.05.2017, 15:32. Показов 10193. Ответов 9 Метки нет (Все метки) Здравствуйте) Помогите пожалуйста разобраться с задачей. Я недавно начала программировать(1 курс), осталось решить только 1 задачу для зачёта. Дан стек из целых числе. Используя только стеки, отсортировать элементы стека по возрастанию. На дне стека минимальный элемент, в вершине- максимальный. Решить задачу, используя класс для работы со стеком. Класс должен содержать методы добавления и удаления элементов из вершины стека. Напишите пожалуйста код программы с комментариями, чтобы я наконец разобралась. Заранее спасибо. 0

@sdasdasda 0 / 0 / 0 Регистрация: 23.11.2016 Сообщений: 14
	05.06.2017, 22:03 [ТС]
	Antikl, и что по вашему делает эта программа? вы просто скопировали с этой ссылки код http://cppstudio.com/post/5155/ 0

@zss Модератор 13766 / 10960 / 6490 Регистрация: 18.12.2011 Сообщений: 29,234
	06.06.2017, 17:30
	ForEveR, не спорю. Но у ТС было именно такое задание - отсортировать стек с использованием только стеков. 0