Лабораторна робота №4

Умова

Реалізуйте стек за допомогою лінійного зв'язаного списку L. Операції PUSH і POP мають виконуватися за час O(1).
Реалізуйте чергу за допомогою лінійного зв'язаного списку L. Операції ENQUEUE і DEQUEUE мають виконуватися за час О(1).

Аналіз

Обидві структури мають дуже схожу реалізацію через зв'язний список. Єдиним чим вони відрізняються, це тим звідки ми беремо значення. У стеку з кінця, а в черзі з початку.

Для Pop та Dequeue я буду використовувати Try- паттерн. Метод буде повертати true та встановлювати реальне значення out параметру, коли коллекція має елементи. Інакше функція повертає false та out параметр має значення за замовчуванням.

Це використовується так, наприклад:

if(stack.TryPop(out var value)) {
  Console.WriteLine("Value exist")
}

if(stack.TryPop(out var value)) {
  Console.WriteLine("Value exist")
}

Структура основних вхідних та вихідних даних

Для Push та Enqueue це значення. Для TryPop та TryDequeue це out параметр (змінна в яку буде записане значення в функції)

Текст програми

Program.cs

using Lab4;

Console.WriteLine("Stack");
var stack = new RomanStack<int>();
Track.Add("Push", stack.Push, 4);
Track.Add("Push", stack.Push, 1);
Track.Add("Push", stack.Push, 3);
Track.Remove<int>("Pop", stack.TryPop);
Track.Add("Push", stack.Push, 8);
Track.Remove<int>("Pop", stack.TryPop);

Console.WriteLine();

Console.WriteLine("Queue");
var queue = new RomanQueue<int>();
Track.Add("Enqueue", queue.Enqueue, 4);
Track.Add("Enqueue", queue.Enqueue, 1);
Track.Add("Enqueue", queue.Enqueue, 3);
Track.Remove<int>("Dequeue", queue.TryDequeue);
Track.Add("Enqueue", queue.Enqueue, 8);
Track.Remove<int>("Dequeue", queue.TryDequeue);

using Lab4;

Console.WriteLine("Stack");
var stack = new RomanStack<int>();
Track.Add("Push", stack.Push, 4);
Track.Add("Push", stack.Push, 1);
Track.Add("Push", stack.Push, 3);
Track.Remove<int>("Pop", stack.TryPop);
Track.Add("Push", stack.Push, 8);
Track.Remove<int>("Pop", stack.TryPop);

Console.WriteLine();

Console.WriteLine("Queue");
var queue = new RomanQueue<int>();
Track.Add("Enqueue", queue.Enqueue, 4);
Track.Add("Enqueue", queue.Enqueue, 1);
Track.Add("Enqueue", queue.Enqueue, 3);
Track.Remove<int>("Dequeue", queue.TryDequeue);
Track.Add("Enqueue", queue.Enqueue, 8);
Track.Remove<int>("Dequeue", queue.TryDequeue);

Track.cs

namespace Lab4;

public delegate bool RemoveDelegate<T>(out T value);

/// <summary>
/// Track addition and removing from stack/queue like methods.
/// </summary>
public static class Track
{
    public static void Add<T>(string message, Action<T> action, T value)
    {
        action(value);
        Console.ForegroundColor = ConsoleColor.Green;
        Console.WriteLine($"{message}: {value}");
        Console.ForegroundColor = ConsoleColor.White;
    }

    public static void Remove<T>(string message, RemoveDelegate<T> action)
    {
        Console.ForegroundColor = ConsoleColor.Red;
        if (action(out var value))
        {
            Console.WriteLine($"{message}: {value}");
        }
        else
        {
            Console.WriteLine($"Nothing can be {message}");
        }
        Console.ForegroundColor = ConsoleColor.White;
    }
}

namespace Lab4;

public delegate bool RemoveDelegate<T>(out T value);

/// <summary>
/// Track addition and removing from stack/queue like methods.
/// </summary>
public static class Track
{
    public static void Add<T>(string message, Action<T> action, T value)
    {
        action(value);
        Console.ForegroundColor = ConsoleColor.Green;
        Console.WriteLine($"{message}: {value}");
        Console.ForegroundColor = ConsoleColor.White;
    }

    public static void Remove<T>(string message, RemoveDelegate<T> action)
    {
        Console.ForegroundColor = ConsoleColor.Red;
        if (action(out var value))
        {
            Console.WriteLine($"{message}: {value}");
        }
        else
        {
            Console.WriteLine($"Nothing can be {message}");
        }
        Console.ForegroundColor = ConsoleColor.White;
    }
}

RomanStack.cs

using System.Diagnostics.CodeAnalysis;

namespace Lab4;

public class RomanStack<T>
{
    private readonly LinkedList<T> data = new();

    public void Push(T item)
    {
        data.AddLast(item);
    }

    public bool TryPop([NotNullWhen(true)] out T? value)
    {
        var last = data.Last;
        if (last == null || last.Value == null)
        {
            value = default;
            return false;
        }

        value = last.Value;
        data.RemoveLast();
        return true;
    }
}

using System.Diagnostics.CodeAnalysis;

namespace Lab4;

public class RomanStack<T>
{
    private readonly LinkedList<T> data = new();

    public void Push(T item)
    {
        data.AddLast(item);
    }

    public bool TryPop([NotNullWhen(true)] out T? value)
    {
        var last = data.Last;
        if (last == null || last.Value == null)
        {
            value = default;
            return false;
        }

        value = last.Value;
        data.RemoveLast();
        return true;
    }
}

RomanQueue.cs

using System.Diagnostics.CodeAnalysis;

namespace Lab4;

public class RomanQueue<T>
{
    private readonly LinkedList<T> data = new();

    public void Enqueue(T item)
    {
        data.AddLast(item);
    }

    public bool TryDequeue([NotNullWhen(true)] out T? value)
    {
        var first = data.First;
        if (first == null || first.Value == null)
        {
            value = default;
            return false;
        }

        value = first.Value;
        data.RemoveFirst();
        return true;
    }
}

using System.Diagnostics.CodeAnalysis;

namespace Lab4;

public class RomanQueue<T>
{
    private readonly LinkedList<T> data = new();

    public void Enqueue(T item)
    {
        data.AddLast(item);
    }

    public bool TryDequeue([NotNullWhen(true)] out T? value)
    {
        var first = data.First;
        if (first == null || first.Value == null)
        {
            value = default;
            return false;
        }

        value = first.Value;
        data.RemoveFirst();
        return true;
    }
}

Результат

Стек та Черга це "умовні" структури, бо найчастіше вони не змінюють шлях, як ми структуруємо данні в пам'яті. Вони лише визначають/обмежують можливі дії з данними. Теоритично ми можемо створити 1 структуру данних й обмежувати її за допомогою інтерфейсів та отримати схожий результат.

Стек та Черга є зручними в багатьох випадках, для певних задач.

Лабораторна робота №4 ​

Умова ​

Аналіз ​

Структура основних вхідних та вихідних даних ​

Текст програми ​

Program.cs ​

Track.cs ​

RomanStack.cs ​

RomanQueue.cs ​

Результат ​