СДлб4
.docxМинистерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем (БИС)
СТЕКИ И ОЧЕРЕДИ
Отчет по практической работе №4 по дисциплине «Структуры данных»
Студент гр. 731-2
А.С. Батаев
Принял:
преподаватель КИБЭВС
Д.Р. Уразаев
Томск 2022
СОДЕРЖАНИЕ
Y
1 Введение 3
2 Ход работы 4
Заключение 10
1 Введение
Данная работа посвящена реализации стека и очереди с использованием динамических структур. Во время работы будет реализован односвязный список на языке программирования c# Задание: Требуется реализовать стек и очередь и создать методы для добавления и удаления элементов, а также проверки длинны этих структур и проверки первого элемента структуры.
2 Ход работы
Весь код программы представлен в приложении А.
По заданию был реализован класс Node, который отвечает за инициализацию и переопределение стека (Рисунок 2.1).
Рисунок 2.1-Класс Node
Далее по заданию был реализован публичный класс Stack.
Была объявлена переменная head, эта переменная отвечает за хранение элемента начала стека. Так же была объявлена публичная переменная count, переменная count служит для хранения размера стека. Переменные head и count представлены на рисунке 2.2.
Рисунок 2.2-Переменные head и count
Для возвращения размера стека был реализован метод Len. Метод Len представлен на рисунке 2.3.
Рисунок 2.3-Метод Len
Для удаления первого элемента стека был реализован метод Pop. Если размер стека равен 0, то возвращается значение 0 и в консоль выводится сообщение, что стек не содержит элементов. После проверки на наличие элементов в переменную point присваивается значение начала списка, после этого указатель на начало списка смещается. Метод возвращает удалённый элемент. Метод Pop представлен на рисунке 2.4.
Рисунок 2.4-Метод Pop
Метод Push нужен для добавления элемента в начало стека. Для этого метод принимает целочисленное значение. Далее это значение встаёт в начало стека, размер стека увеличивается на единицу. Метод Push представлен на рисунке 2.5.
Рисунок 2.5-Метод Push
Метод Check возвращает элемент, который находится сверху стека. Метод Check представлен на рисунке 2.6.
Рисунок 2.6-Метод Check
Для возвращения размера очереди был реализован метод Len представленный на рисунке 2.7.
Рисунок 2.7-Метод Len
Для удаления первого элемента стека был реализован метод Delete. Если размер стека равен 0, то возвращается значение 0 и в консоль выводится сообщение, что очередь не содержит элементов. После проверки на наличие элементов в переменную point присваивается значение начала списка, после этого указатель на начало списка смещается. Метод возвращает удалённый элемент. На рисунке 2.8 представлен метод Delete.
Рисунок 2.8-Метод Delete
Метод Add нужен для добавления элемента в конец очереди. Для этого метод принимает целочисленное значение. Далее это значение встаёт в конец очереди, размер очереди увеличивается на единицу, последний добавленный элемент принимает значение tail. На рисунке 2.9 представлен метод Add.
Рисунок 2.9-Метод Add
Метод Check возвращает элемент, который находится в начале очереди. На рисунке 2.10 представлен метод Check.
Рисунок 2.10-Метод Check
Метод Main находится в классе Program. Метод Main можно увидеть на рисунке 2.11-12.
Рисунок 2.11-Метод Main
Рисунок 2.12-Метод Main
Заключение
Во время лабораторной работы была проведена реализация стек и очереди. Были реализованы четыре метода. Очередь и стек были реализованы с помощью односвязных списков. Были получены навыки работы с динамическими списками на базе языка программирования c#.
Приложение А (обязательное)
using System;
using System.Collections.Generic;
using System.Collections;
using System.Xml.Serialization;
using static sdlab4.Program;
namespace sdlab4
{
class Program
{
public class Node<T>
{
public int Element;
public Node<int> Next;
public Node(int element)
{
Element = element;
}
}
public class Stack<T>
{
public Node<int> head; public int count;
public int Len()
{
return count;
}
public int Pop()
{
Check();
Node<int> point = head;
head = head.Next;
count--;
return point.Element;
}
public void Push(int element)
{
Node<int> point = new Node<int>(element);
point.Next = head;
head = point;
count++;
}
public int Check()
{
if (count == 0)
{
Console.WriteLine("Stack has no elements, return value 0");
return 0;
}
return head.Element;
}
}
public class Queue<T>
{
public Node<int> head;
public Node<int> tail;
public int count;
public int Len()
{
return count;
}
public int Delete()
{
Check();
Node<int> point = head;
head = head.Next;
count--;
return point.Element;
}
public void Add(int element)
{
Node<int> point = new Node<int>(element);
Node<int> temp = tail; tail = point; if (count == 0)
{
head = tail;
}
else
{
temp.Next = tail;
}
count++;
}
public int Check()
{
if (count == 0)
{
Console.WriteLine("Queue has no elements, returned value 0");
return 0;
}
return head.Element;
}
}
static void Main(string[] args)
{
int header;
int count;
OneMore:
Console.WriteLine("1 - Stack, 2 - Queue");
switch (int.Parse(Console.ReadLine()))
{
case 1:
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(22);
stack.Push(333);
stack.Push(44);
stack.Push(5);
stack.Push(66);
stack.Push(777);
stack.Push(88);
stack.Push(9);
header = stack.Check();
Console.WriteLine($"Top element of the stack : {header}");
count = stack.Len();
Console.WriteLine("The stack size is {0}", count);
header = stack.Check();
Console.WriteLine($"Top element of the stack : {header}");
header = stack.Pop();
Console.WriteLine("Removed element {0}", header);
header = stack.Check();
Console.WriteLine($"The stack size is: {header}");
count = stack.Len();
Console.WriteLine("The stack size is {0}", count);
break;
case 2:
Queue<int> line = new Queue<int>();
line.Add(111);
line.Add(22);
line.Add(3);
line.Add(44);
line.Add(555);
line.Add(66);
line.Add(7);
line.Add(88);
line.Add(999);
header = line.Check();
Console.WriteLine(" Queue start element : {0}", header);
header = line.Check();
Console.WriteLine("Queue start element: {0}", header);
count = line.Len();
Console.WriteLine("Queue length {0}", count);
header = line.Delete();
Console.WriteLine("The removed element of the queue is {0}", header);
header = line.Check();
Console.WriteLine("Queue start element: {0}", header);
count = line.Len();
Console.WriteLine("Queue length: {0}", count);
break;
}
goto OneMore;
}
}
}