Реализовать структуру данных "очередь"

@lerka1996 · Регистрация: 04.03.2015

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

Написать программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n
Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из очереди первый элемент. Программа должна вывести его значение.
front
Программа должна вывести значение первого элемента, не удаляя его из очереди.
size
Программа должна вывести количество элементов в очереди.
clear
Программа должна очистить очередь и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

Входные данные
Вводятся команды управления очередью, по одной на строке

Выходные данные
Требуется вывести протокол работы с очередью, по одному сообщению на строке

Примеры
входные данные
size
push 1
size
push 2
size
push 3
size
exit
выходные данные
0
ok
1
ok
2
ok
3
bye

@zss · 16.11.2015, 14:17

структура данных "Очередь"

@ture · 17.11.2015, 11:52

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
#include <iostream>
#include <string>
 
template<typename T>class Queue {
private:
    //вложенный тип (односвязный список)
    class Node {
    public:
        T val;
        Node * next = nullptr;
        Node(const T & val):val(val) {}
        ~Node() { delete next; }
    };
    
    int len;
    Node * first, * last;
    //запрещаем копирование и писваивание (чтоб не морочиться)
    Queue(const Queue & other);
    Queue & operator=(const Queue & other);
public:
    //конструктор без параметров
    Queue(): len(0), first(nullptr), last(nullptr) {}
 
    //добавляет в конец очереди
    void push(const T & val) {
        Node * n = new Node(val);
        if(last == nullptr)
            first = last = n;
        else {
            last->next = n;
            last = last->next;
        }
        ++len;
    }
    //удаляет первый из очереди 
    void pop() {
        if(first!=nullptr) {
            Node * temp = first;
            first = first->next;
            temp->next = nullptr;
            delete temp;
            --len;
            if(!len)
                last = nullptr;         
        } 
    }
    //очищает очередь
    void clear() { delete first; first = last = nullptr; len = 0; }
    //получает первые из очереди
    T front() const { 
        return first->val; //если очередь пуста, то вывалит ошибку
    }
    //выдаем размер
    int size() const { return len; }
    //деструктор
    ~Queue() { delete first; first = last = nullptr; }
};
 
int main() {
    Queue<int> q;
    std::string str;
    while(std::cin >> str) {
        if(str == "push") {
            int n;
            std::cin >> n;
            q.push(n);
            std::cout << "ok\n";
        } else if(str == "pop") {
            std::cout << q.front() << std::endl;
            q.pop();            
        } else if(str == "front")
            std::cout << q.front() << std::endl;
        else if(str=="size")
            std::cout << q.size() << std::endl;
        else if(str == "clear") {
            q.clear();
            std::cout << "ok\n";
        } else if(str == "exit")
            break;
    }
        
    std::cout << "bye\n";
    system("pause");
    return 0;
}

это я навоял из головы, т.е. проверки на Вашей стороне

@irthgr · 09.08.2021, 18:54

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
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
 
struct queue{
    int storage[100000];
    int start;
    int finish;
    queue(){
        start = 0;
        finish = 0;
    }
 
    void push(int n){
        storage[finish] = n;
        finish++;
    }
 
    int pop(){
        int a = storage[start];
        start++;
        return a;
    }
 
    int front(){
        return storage[start];
    }
 
    int size(){
        return finish - start;
    }
 
    string clear(){
        finish = 0;
        start = 0;
        return "ok";
    }
 
    string exit(){
        return "bye";
    }
};
 
int main() {
    string a;
    string n;
    queue x;
    string i = "";
    while(cin >> a){
        if(a == "push"){
            int n;
            cin >> n;
            x.push(n);
            i += "ok\n";
        }
        else if(a == "pop" && x.size()!=0){
            n = to_string(x.front());
            x.pop();
            i += n + "\n";
        }
        else if(a == "pop" && x.size()==0){
            i += "error\n";
        }
        if(a == "front" && x.size()!=0){
            n = to_string(x.front());
            i += n + "\n";
        }else if(a == "front" && x.size()==0){
            i += "error\n";
        }
        if(a == "size"){
            n = to_string(x.size());
            i += n + "\n";
        }
        else if(a == "clear"){
            x.clear();
            i += "ok\n";
        }
        else if(a == "exit"){
            i += "bye\n";
            break;
        }
 
    }
    cout << i;
    return 0;
}

Моё решение, это изменённое чужое

@Folian · 09.08.2021, 19:19

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

int storage[100000];

@Kolbastero · 05.11.2021, 01:52

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
#include <iostream>
#include <string>
 
using namespace std;
 
const int MAX_SIZE = 10000;
 
 
struct queue {
    int m_size = 0;            // Количество элементов в очереди
    int m_start = 0;
    int m_elems[MAX_SIZE]; // Массив для хранения элементов
 
    ~queue()
    {
        for (int i = m_size - 1; i > -1; i--)
        {
            m_elems[i] = 0;
        }
        m_size = 0;
        m_start = 0;
    };   // Деструктор
    void push(int d)
    {
        if (m_size == MAX_SIZE) m_size = 0;
        m_elems[m_size] = d;
        m_size++;
        std::cout << "ok" << endl;
    };      // Добавить в очередь новый элемент
    int pop() {
        if (m_size - m_start == 0) throw - 1;
        m_start++;
        if (m_start == MAX_SIZE)
        {
            m_start = 0;
            return m_elems[MAX_SIZE - 1];
        }
        return m_elems[m_start - 1];
 
    };             // Удалить из стека первый элемент
                           // и вернуть его значение
    int front() 
    {
        if (m_size == 0) throw - 1;
        return m_elems[m_start];
    };              // Вернуть значение первого элемента
    int size() {
        if (m_size >= m_start) return m_size;
        else
        {
            return m_size + MAX_SIZE - m_start;
        }
    };              // Вернуть количество элементов в очереди
    void clear() {
        m_size = 0;
        m_start = 0;
        std::cout << "ok" << endl;
    };          // Очистить очередь
};
 
int main()
{
    int n;
    string b;
    queue biba;
    while (true)
    {
        cin >> b;
        if (b == "push")
        {
            std::cin >> n;
            biba.push(n);
        }
        if (b == "back")
        {
            try
            {
                std::cout << biba.front() << endl;
            }
            catch (int)
            {
                cout << "error" << endl;
            }
        }
        if (b == "pop")
        {
            try
            {
                std::cout << biba.pop() << endl;
            }
            catch (int)
            {
                cout << "error" << endl;
            }
        }
        if (b == "size")
        {
            std::cout << biba.size() << endl;
        }
        if (b == "clear")
        {
            biba.clear();
        }
        if (b == "exit")
        {
            std::cout << "bye" << endl;
            return 0;
        }
    }
    return 0;
}

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

@lemegeton · 05.11.2021, 12:01

Моя вариация на тему. )

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
#include <iostream>
#include <stdexcept>
 
struct NodeBase {
    NodeBase *prev;
    NodeBase *next;
    NodeBase(): prev{this}, next{this} {}
    explicit NodeBase(NodeBase *after): prev{after}, next{after->next} {
        prev->next = next->prev = this;
    }
    virtual ~NodeBase() {
        prev->next = next;
        next->prev = prev;
    }
};
 
template<typename T>
struct Node: public NodeBase {
    T value;
    Node(const T &value, NodeBase *after): NodeBase{after}, value{value} {}
};
 
template<typename T>
class Queue {
public:
    Queue(): base{}, nodeCount{0} {}
    Queue(const Queue<T> &) = delete;
    Queue &operator=(const Queue<T> &) = delete;
 
    void push_back(const T &value) {
        new Node<T>(value, base.prev);
        ++nodeCount;
    }
 
    const T &front() const {
        if (empty()) {
            throw std::underflow_error("queue is empty");
        }
        return static_cast<Node<T>*>(base.next)->value;
    }
 
    void pop_front() {
        if (empty()) {
            throw std::underflow_error("queue is empty");
        }
        delete base.next;
        --nodeCount;
    }
 
    std::size_t size() const {
        return nodeCount;
    }
    bool empty() const {
        return base.next == &base;
    }
    void clear() {
        while (!empty()) {
            delete base.next;
        }
        nodeCount = 0;
    }
    virtual ~Queue() {
        clear();
    }
private:
    NodeBase base;
    std::size_t nodeCount;
};
 
int main() {
 
    Queue<int> queue{};
    auto &in = std::cin;
 
    while (in.good()) {
        std::string command;
        std::cin >> command;
        if (command == "exit") {
            std::cout << "bye" << std::endl;
            break;
        } else if (command == "push") {
            int x;
            in >> x;
            queue.push_back(x);
            std::cout << "ok" << std::endl;
        } else if (command == "pop") {
            std::cout << queue.front() << std::endl;
            queue.pop_front();
        } else if (command == "front") {
            std::cout << queue.front() << std::endl;
        } else if (command == "size") {
            std::cout << queue.size() << std::endl;
        } else if (command == "clear") {
            queue.clear();
            std::cout << "ok" << std::endl;
        }
    }
 
    return 0;
}

@Kolbastero · 08.11.2021, 07:50

Не бей тапками, но это же стек а не очередь)) @irthgr

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

@lerka1996 2 / 2 / 0 Регистрация: 04.03.2015 Сообщений: 76

	Реализовать структуру данных "очередь" 16.11.2015, 13:54. Показов 15985. Ответов 7 Метки нет (Все метки) Написать программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы: push n Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok. pop Удалить из очереди первый элемент. Программа должна вывести его значение. front Программа должна вывести значение первого элемента, не удаляя его из очереди. size Программа должна вывести количество элементов в очереди. clear Программа должна очистить очередь и вывести ok. exit Программа должна вывести bye и завершить работу. Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент. Входные данные Вводятся команды управления очередью, по одной на строке Выходные данные Требуется вывести протокол работы с очередью, по одному сообщению на строке Примеры входные данные size push 1 size push 2 size push 3 size exit выходные данные 0 ok 1 ok 2 ok 3 bye 0

@zss Модератор 13771 / 10964 / 6491 Регистрация: 18.12.2011 Сообщений: 29,241
	16.11.2015, 14:17
	структура данных "Очередь" 0

@Kolbastero 0 / 0 / 0 Регистрация: 05.11.2021 Сообщений: 3
	08.11.2021, 07:50
	Не бей тапками, но это же стек а не очередь)) @irthgr 0

Реализовать структуру данных "очередь"

Решение