Практические задания по теме «Методы»

Задачи для обязательного выполнения

Задача 1. Простой стек

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

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

Задача 2. Реализуйте структуру данных "очередь"

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

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

Задача 3. Проверка расстановки скобок в арифметическом выражении

Дан текст. Проверить, правильно ли в нем расставлены круглые скобки (т. е. находится ли справа от каждой открывающей скобки соответствующая ей закрывающая скобка, а слева от каждой закрывающей — соответствующая ей закрывающая). Предполагается, что внутри каждой пары скобок нет других скобок.

• Ответом должны служить слова да или нет.
• В случае неправильности расстановки скобок:
  • если имеются лишние правые (закрывающие) скобки, то выдать сообщение с указанием позиции первой такой скобки;
  • если имеются лишние левые (открывающие) скобки, то выдать сообщение с указанием количества таких скобок.

Если скобки расставлены правильно, то сообщить об этом.

Задача 4. Реализация структуры хранения двухсторонняя очередь.

Дек (deque) представляет двустороннюю очередь, в которой элементы можно добавлять как в начало, так и в конец. Удаление также может идти как с начала, так и с конца. Поскольку реализовать добавление и удаление нужно с двух сторон, то за основу реализации нужно взять организацию двусвязного списка. Так, каждый элемент в деке будет представлен следующим классом:

public class DoublyNode<T>
{
  public DoublyNode(T data)
  {
    Data = data;
  }
  public T Data { get; set; }
  public DoublyNode<T> Previous { get; set; }
  public DoublyNode<T> Next { get; set; }
}

Реализовать методы для работы с данной структурой

• Поиск заданного элемента в двухсторонней очереди. Результат – номера позиций очереди, где был найден искомый элемент
• добавление элемента в очередь с начала
• добавление элемента в очередь с конца
• удаление искомого элемента из очереди
• удаление элемента из начала очереди
• удаление элемента с конца очереди
• печать элементов очереди