Задача
Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
- push_front Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
- push_back Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
- pop_front Извлечь из дека первый элемент. Программа должна вывести его значение.
- pop_back Извлечь из дека последний элемент. Программа должна вывести его значение.
- front Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
- back Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
- size Вывести количество элементов в деке.
- clear Очистить дек (удалить из него все элементы) и вывести ok.
- exit Программа должна вывести bye и завершить работу.
Гарантируется, что количество элементов в деке в любой момент не превосходит [latex]100[/latex]. Все операции:
pop_front,
pop_back,
front,
back
всегда корректны.
Входные данные
Описаны в условии. См. также пример входных данных.
Выходные данные
Описаны в условии. См. также пример входных данных.
Тесты
| Входные данные | Выходные данные |
| push_back 3 push_front 14 size clear push_front 1 back push_back 2 front pop_back size pop_front size exit |
ok ok 2 ok ok 1 ok 1 2 1 1 0 bye |
Код программы на 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 |
#include <iostream> #include <string> using namespace std; struct deque{ #define Size 200000 int start, end; int folder[Size]; deque(){ start = end = Size/2; } void push_front(int var){ folder[--start] = var; cout << "ok" << endl; } void push_back(int var){ folder[end++] = var; cout << "ok" << endl; } void pop_front(){ cout << folder[start++] << endl; } void pop_back(){ cout << folder[--end] << endl; } void front(){ cout << folder[start] << endl; } void back(){ cout << folder[end-1] << endl; } void size(){ cout << end-start << endl; } void clear(){ start = end = Size/2; cout << "ok" << endl; } }; int main() { string s; deque deq; int n; while (cin >> s){ if (s == "push_front"){ cin >> n; deq.push_front(n); } else if (s == "push_back"){ cin >> n; deq.push_back(n); } else if (s == "pop_front") deq.pop_front(); else if (s == "pop_back") deq.pop_back(); else if (s == "front") deq.front(); else if (s == "back") deq.back(); else if (s == "size") deq.size(); else if (s == "clear") deq.clear(); else if (s == "exit"){ cout << "bye"; return 0; } } } |
Код программы на Java
|
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 |
import java.util.*; class deque{ private static final int Size = 200000; int start, end; int [] folder = new int[Size] ; deque(){ start = end = Size/2; } void push_front(int var){ folder[--start] = var; System.out.println("ok"); } void push_back(int var){ folder[end++] = var; System.out.println("ok"); } void pop_front(){ System.out.println(folder[start++]); } void pop_back(){ System.out.println(folder[--end]); } void front(){ System.out.println(folder[start]); } void back(){ System.out.println(folder[end-1]); } void size(){ System.out.println(end-start); } void clear(){ start = end = Size/2; System.out.println("ok"); } }; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner scan = new Scanner(System.in); deque deq = new deque(); String S; while (scan.hasNext()){ S = scan.next(); if (S.equals("push_front")) deq.push_front(scan.nextInt()); else if (S.equals("push_back")) deq.push_back(scan.nextInt()); else if (S.equals("pop_front")) deq.pop_front(); else if (S.equals("pop_back")) deq.pop_back(); else if (S.equals("front")) deq.front(); else if (S.equals("back")) deq.back(); else if (S.equals("size")) deq.size(); else if (S.equals("clear")) deq.clear(); else if (S.equals("exit")){ System.out.println("bye"); System.exit(0); } } } } |
Решение
Создадим массив [latex]folder[/latex] и целочисленные переменные [latex]start[/latex] и [latex]end[/latex] в качестве указателей на начало и конец нашего дека.
- push_front — сдвигаем указатель [latex]start[/latex] на [latex]1[/latex] назад, кладем значение в наш дек и выводим ok;
- push_back — кладем значение в наш дек, сдвигаем указатель [latex]end[/latex] на [latex]1[/latex] вперед и выводим ok;
- pop_front — выводим значение начала дека и перемещаем [latex]start[/latex] вперед на [latex]1[/latex];
- pop_back — перемещаем [latex]end[/latex] назад на [latex]1[/latex] и выводим значение конца дека;
- front — выводим значение начала дека;
- back — выводим значение перед [latex]end[/latex];
- size — отнимем от переменной [latex]end[/latex] переменную [latex]start[/latex];
- clear — приводим [latex]start[/latex] и [latex]end[/latex] к изначальным позициям;
- exit — выводим «bye» и заканчиваем программу.
Ссылки
Ideone C++
Ideone Java
решение e-olymp C++
решение e-olymp Java
С точки зрения e-olymp всё хорошо. Но я считаю, что задача не решена.
Я ведь вижу код и мне понятно, что задание «Реализуйте структуру данных дек» не выполнено. Нужно создать класс или структуру с нужными методами.
Надо отступы поправить.