Programming on c sharp, C# Abstract data types

Programming on c sharp in Microsoft Visual Studio. Abstract Data Types in C#

Содержание:

Theory
- Stack
- Queue
Labs and Tasks

Theory

Stack

Stack represents a simple last-in-first-out (LIFO) non-generic collection of objects.

Stack interface:

class Stack<T>
{
    public int Count { get; }
    public void Push(T item);  
    public T Pop();
    public T Peek();
}

If Count is less than the capacity of the stack, Push is an O(1) operation. If the capacity needs to be increased to accommodate the new element, Push becomes an O(n) operation, where n is Count. Pop is an O(1) operation.
Stack accepts null as a valid value and allows duplicate elements.

Examples of working with a Stack:

Push method Inserts an object at the top of the Stack

// namespace to work with a Stack class
using System.Collections; 
static void Main(string[] args)
     {
     // Creates and initializes a new Stack.
        Stack myStack = new Stack();
	myStack.Push("Hello");
	myStack.Push("World");
	myStack.Push("!");
 
	// Displays the properties and values of the Stack.
	Console.WriteLine("myStack");
	Console.WriteLine($"Count: {myStack.Count}"); // Count: 3
 
	Console.Write("Values: ");
	foreach (Object obj in myStack)
		Console.Write($"{obj} "); // Values: ! World Hello
   }

Pop method removes and returns the object at the top of the Stack

var s = new Stack<int>();
s.Push(1);
s.Push(2);
s.Push(3);
while (s.Count > 0)
	Console.WriteLine(s.Pop()); // 3 2 1
Console.WriteLine($"s count: {s.Count}"); // 0

var s = new Stack<int>();
s.Push(1);
s.Push(2);
s.Push(3);
var s1 = new Stack<int>();
while (s.Count > 0)
	s1.Push(s.Pop());
Console.WriteLine($"s1 count: {s1.Count}"); // 3
while (s1.Count > 0)
	Console.WriteLine(s1.Pop()); // 1 2 3

Peek method returns the object at the top of the Stack without removing it

Queue

Queue is a collection of data organized by the FIFO principle: First In – First Out

Queue interface:

class Queue<T>
{
  public int Count { get; }
  public void Enqueue(T item);
  public T Dequeue();
  public T Peek();
}

Examples of working with a Queue:

var q = new Queue<int>(); // Initializing of the new instance of the Queue<T> class
q.Enqueue(3); // Adds an object to the end of the Queue
q.Enqueue(2);
q.Enqueue(5); // 3 2 5
 
var q1 = new Queue<int>();
while (q.Count > 0)
  q1.Enqueue(q.Dequeue());
while (q1.Count>0)
  WriteLine(q1.Dequeue());

Labs and Tasks

Stack

Lab 1. Working with a Stack class

To do: There is a string containing three types of brackets: round (), square [], and curly {}, and any other characters. Check whether the brackets are correctly placed in it. For example, in the line ([]{})[] brackets are placed correctly, but not in the line ([]].

Note: it is better to use the next algorithm:

1. Create an empty stack.
2. Iterate over the characters of the string using a loop.
3. If the current character is an opening bracket, then push it at the top of the stack.
4. If the current character is a closing bracket, then check the top element of the stack: the corresponding opening bracket must be there.
5. In the end, the stack must become empty, otherwise, the string had incorrect brackets.

The resulting example:

The string: ([a]{b}c)[]
The brackets are placed correctly!

The string: (a[]]
The brackets are placed INcorrectly!

The string: ())
The brackets are placed INcorrectly!

[Solution and Project name: Lesson_17Lab1, file name L17Lab1.cs]

✍ How to do:

Create a new project with the name and file name as it is specified in the task.
Create a method to check the characters of the string. Only one parameter is needed — the string itself. The method will return a boolean type: true — if the brackets are placed correctly inside the string, and false — if the brackets are placed incorrectly inside the string. The signature of the method:

public static bool CheckBrackets(string s)
   {
     ...
   }

1. Create an empty stack.

After, create an instance of the Stack class to push opening brackets into it. Since we’re going to work with characters it has to be of char type. Place the declaration inside the method:

Stack<char> st = new Stack<char>();

2. Iterate over the characters of the string using a loop.

To iterate over the string characters we’re going to use foreach loop:

foreach (char c in s)
  {
    ...
  }

3. If the current character is an opening bracket, then push it at the top of the stack.

We’re going to store all opening brackets in our stack. Create an if statement to check the current string character to see if it is an opening bracket, if so, push this bracket into the stack. Place the code into the foreach loop, instead of ...:

if (c == '[' || c == '(' || c == '{')
    st.Push(c);

Push(Object) method inserts an object at the top of the Stack.

4. If the current character is a closing bracket, then check the top element of the stack: the corresponding opening bracket must be there.

Let’s imagine that our stack is no longer empty, and we have to check whether the opening bracket at the top of the stack (that is, it was pushed last) corresponds to the closing bracket — the value of the current character. Add the If statement to check these conditions:

if (st.Count > 0)
	if ((st.Peek() == '[' && c == ']') || (st.Peek() == '(' && c == ')') ||
		(st.Peek() == '{' && c == '}'))
	{
		...
	}

Peek() method returns the object at the top of the Stack without removing it.

At the end of the check, our stack should become empty. So we need to remove the corresponding bracket from the stack. Place the statement inside the if:

     // ...
     st.Pop();

Pop() removes and returns the object at the top of the Stack.

One more thing we have to do is to count all the brackets inside the string. If the number of the brackets is odd, so there is an extra bracket or a lack of bracket inside the string. Define the counter before the foreach loop:

int countBrackets = 0;
string brackets = "[]{}()";

Inside the loop, we need to increase the counter in the case if the current character is a bracket:

if (brackets.IndexOf(c) >= 0) countBrackets++;

5. In the end, the stack must become empty, otherwise, the string had incorrect brackets.

The method returns true if the stack is empty or the countBrackets is an even number, and false otherwise. Add the code at the end of the method code:

if (countBrackets % 2 > 0) // if the number of brackets is odd
	return false;
else
	return st.Count == 0;

Within the main function initialize a string variable. Call the CheckBrackets method to check the string. Print out the proper messages:

Write("The string: ");
string s = "([a]{b}c)[]";
WriteLine(s);
if (CheckBrackets(s))
	WriteLine("The brackets are placed correctly!");
else
	WriteLine("The brackets are placed INcorrectly!");

Run the application again and check the output.
Add some more values of the string and check them too.

Write("The string: ");
s = "(a[]]";
WriteLine(s);
if (CheckBrackets(s))
	WriteLine("The brackets are placed correctly!");
else
	WriteLine("The brackets are placed INcorrectly!");

Run the application again and check the output.
Save and upload the file into the moodle system.

Queue

Lab 2. Working with a Queue

To do: Output the first n natural numbers in ascending order, whose Prime factorization includes only the numbers 2, 3, 5. For example, for n = 11 the result must be 1 2 3 4 5 6 8 9 10 12 15. Because there are no multiples of 7, 11 and 13; for 14 — the multiples are 2 and 7, and 7 can’t be used.

Note: it is better to use the next algorithm:

1. Use three queues that store numbers that are 2 (3, 5) times larger than those already printed, but they are not printed.
2. Each time the smallest value located at the top of one of the queues is selected and printed, and corresponding multiples of it are added to the tails of the queues.
3. The process starts with printing the number 1.

The resulting example:

Please, enter n:
20
The result is:
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

[Solution and Project name: Lesson_17Lab2, file name L17Lab2.cs]

✍ How to do:

Create a new project with the name and file name as it is specified in the task.
Ask user to input n and read the inputted number, storing it in the n variable:

Console.WriteLine("Please, enter n:");
int n = int.Parse(Console.ReadLine());

Don’t forget to check to see if the entered number is larger than 0:

System.Diagnostics.Debug.Assert(n > 0);

1. Use three queues that store numbers that are 2 (3, 5) times larger than those already printed, but they are not printed.

Initialize three empty instances of the Queue class. Give them the names (e.g. Two, Three, Five):

Queue<int> Two = new Queue<int>();
Queue<int> Three = new Queue<int>();
Queue<int> Five = new Queue<int>();

It is said in the task that «the process starts with printing the number 1«. Let’s print the 1:

int min = 1;
Console.Write(min);
Console.Write(" ");

2. Each time the smallest value located at the top of one of the queues is selected and printed, and corresponding multiples of it are added to the tails of the queues.

After, you have to add to Two queue the number that is 2 times larger than that already printed (than min = 1), to add to Tree queue the number that is 3 times larger than that already printed, and to Five queue the number that is 5 times larger than that already printed:

Two.Enqueue(min * 2);
Three.Enqueue(min * 3);
Five.Enqueue(min * 5);

Enqueue(object obj) adds an object to the end of the Queue.

To print out the next value, it should be 2, you have to find the minimum number among the top numbers of the queues and print it out to the console window. This process will be repeated n times, so you’ll need a for loop:

for (int i = 1; i < n; ++i)
   {
     min = Math.Min(Two.Peek(), Math.Min(Three.Peek(), Five.Peek()));
     Console.Write(min);
     ...
   }

Peek() method returns the object at the beginning of the Queue without removing it.

Inside the same loop you have to add the next values which are 2, 3 or 5 times larger than that already printed (min) (in the task we have «corresponding multiples of it are added to the tails of the queues»):

 Console.Write(" ");
 Two.Enqueue(min*2);
 Three.Enqueue(min*3);
 Five.Enqueue(min*5);

At the same time you have to remove the printed value from the queue:

if (Two.Peek() == min)
    Two.Dequeue();
if (Three.Peek() == min)
    Three.Dequeue();
if (Five.Peek() == min)
    Five.Dequeue();

Dequeue() method removes and returns the object at the beginning of the Queue.

Run the program to see the output.

Lists

Lab 3. Working with a LinkedList

Linkedlists are usually used in situations where you need to perform a lot of inserts and deletions in the middle of some sequence.

To do:

1. A long list of random integers (100,000 items) must be generated.
2. Iterate through the list and remove all numbers from the list that are divisible by the first element of it.
3. The number 0 must be inserted between any two elements of the same parity
(e.g. 2 and 8 are both even, so we must output 2 0 8;
3 and 9 are both odd, so we must output 3 0 9).

The resulting example:

The beginning of the resulting output:
Before:
9  9  2  6  6  8  7  1  1  7  6  7  8  5  1  3  6  6  5  8  3  2  8  6  8  4  
4  4  7  9  4  5  9  2  6  5  4  3  8  6  5  8  1  6  4  5  7  3  9  8  4  2  
2  4  6  8  1  5  7  3  4  4  3  2  3  1  8  6  8  5  9  3  7  9  4  5  2 
After:
9  2  0  6  0  6  0  8  7  0  1  0  1  0  7  6  7  8  5  0  1  0  3  6  0  6  
5  8  3  2  0  8  0  6  0  8  0  4  0  4  0  4  7  4  5  2

[Solution and Project name: Lesson_17Lab3, file name L17Lab3.cs]

✍ How to do:

Create a new project with the name and file name as it is specified in the task.
Class LinkedList represents a doubly linked list. We’re going to create an instance of an object of that class. Let’s call it l:

LinkedList<int> l = new LinkedList<int>();

The list of 100 000 numbers must be generated randomly. So we need to use the instance of class Random object, number generator:

Random r = new Random()

To create a list of generated number with the boundaries [1;10] we’re going to use the for loop:

for (int i = 0; i < 100000; ++i)
	{
		l.AddLast(r.Next(1, 10));
	}

AddLast(T value) method adds a new node containing the specified value at the end of the LinkedList.

After, we can print the elements of the list out to the console window:

Console.WriteLine("before");
foreach (int i in l)
    {
       Console.Write($"{i}  ");
    }

Run the program to see the output.

2. Iterate through the list and remove all numbers from the list that are divisible by the first element of it.

Now, we’re going to use the variable to store the value of the first element. And after, we’ll check the elements one by one to see if they are divisible by the first element without a remainder.

var head = l.First;
int fst = l.First.Value;

The property First returns the first node of the LinkedList. The property Value is used to get value of the node.

Let’s check the rest elements (nodes) of the list to remove those of them which are devisable by fst (the value of the first element). We’re going to use the while loop:

head = head.Next;
while (head != null)
	{
		var t = head; // the current node of the list 
		head = head.Next; // the next node of the list 
		if (t.Value % fst == 0)
		{
 
			l.Remove(t); // removes the node of the list
		}
	}

3. The number 0 must be inserted between any two elements of the same parity.

Now we’re going to use the while loop to iterate through the list’s nodes to check the neighboring nodes to see if they are of the same parity. We’ll have if statement with double conditions — for odd and even cases:

head = l.First; // the current node
var headp = head.Next; // the next node
while (headp != null)
{
	if ((head.Value % 2 == 0 && headp.Value % 2 == 0) ||  // even nodes
            (head.Value % 2 != 0 && headp.Value % 2 != 0))    // odd nodes
	{
		l.AddAfter(head, 0);
	}
	head = headp; // moves to the next pair of the nodes
	headp = headp.Next;
}

The AddAfter method adds the specified new node after the specified existing node in the LinkedList.

After, we can output the resulting LinkedList:

Console.WriteLine();
Console.WriteLine("after");
foreach (int i in l)
{
	Console.Write($"{i}  ");
}

Run the program again to see the output.

Back

Content

Go on