May 2013 – Programming Tutorials

Dynamic Queue Implementation – C#

A dynamic queue is a queue that is implemented with nodes. Nodes consist of two things: value and link to another node.

The following image illustrates the implementation:

dynamic-queue

The most left node is the front of the queue, and the most right one is the back of the queue. Every node is connected to the one right of it. The back of the queue points to null.

You can see the implementation of the queue here.
Lets jump to the explanation.

First lets see how the Node is implemented.

private class Node
{
	public T Item { get; set; }
	public Node Next { get; set; }

	public Node(T item)
	{
		this.Item = item;
		this.Next = null;
	}

	public Node(T item, Node previous)
	{
		this.Item = item;
		this.Next = null;
		previous.Next = this;
	}
}

We have an Item which represents the value of the node. The link is a simple reference to a node and is called Next. We also have two constructors. One that creates a node with some item and has a pointer to null. The other one creates the same node, but the difference is that a previous node is linked to the one that was just created. The Node class is a private class in the Queue class which I called CustomQueue.

Now lets jump to the CustomQueue.
Lets see what fields, constructors and properties we have.

private Node front;
private Node back;
private int count;

public CustomQueue()
{
	this.front = null;
	this.back = null;
	this.count = 0;
}

public int Count
{
	get
	{
		return this.count;
	}
}

We have references(pointers) to the front and the back of the queue. There is a count field that has a Count property with getter only (we don’t want to mess up the count from the outside). We also have only a single default constructor that makes an empty queue by initializing the front and the back with null and count with 0.

Now lets see the basic methods.

public void Enqueue(T item)
{
	if (this.front == null)
	{
		// We have empty queue
		this.front = new Node(item);
		this.back = this.front;
	}
	else
	{
		Node newNode = new Node(item, this.back);
		this.back = newNode;
	}

	this.count++;
}

The “Enqueue” method adds a new element to the front of the queue. First we check if the queue is empty (if so we make a queue with only one node that points to null). If the queue is not empty, we create a new node and tell the back of the queue to start pointing at the node we’ve just created. This is accomplished with the second constructor. We have to tell that the new back of the queue is the new node. Last we increment the count.

Consider the following code:

CustomQueue<int> queue = new CustomQueue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

In the memory that looks much like this:

enqueue

public T Dequeue()
{
	if (this.count == 0)
	{
		// We have empty queue
		throw new InvalidOperationException("The queue is empty");
	}

	T result = this.front.Item;
	this.front = this.front.Next;
	this.count--;

	return result;
}

The “Dequeue” method removes the front of the queue and returns the value of it. We first make a check if the queue is empty (if so we throw an InvalidOperationExceltion). If the queue is not empty, then we remove the front. It’s simple, we just initialize the front with it’s link. The garbage collector will take care of the node that is discarded from the queue. We also have to decrement the count and return the result (the value of the removed element).

Consider the following code:

CustomQueue<int> queue = new CustomQueue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

queue.Dequeue();
queue.Dequeue();
queue.Dequeue();

The dequeue process should look something like this:

dequeue

public T Peek()
{
	if (this.count == 0)
	{
		// We have empty queue
		throw new InvalidOperationException("The queue is empty");
	}

	return this.front.Item;
}

The “Peek” method gets the value of the front of the queue. Again there is a check for empty queue and an exception throw if it’s empty.

public void Clear()
{
	this.front = null;
	this.back = null;
	this.count = 0;
}

The “Clear” method clears the queue (makes it empty). It’s just like the constructor. We initialize the front and the back with null and the count with 0.

CustomQueue implements the ICloneable interface. It’s useful to clone the queue sometimes.

public object Clone()
{
	CustomQueue<T> clone = new CustomQueue<T>();

	Node currentNode = this.front;
	while (currentNode != null)
	{
		// We have non-empty queue
		clone.Enqueue(currentNode.Item);
		currentNode = currentNode.Next;
	}

	return clone;
}

The “Clone” method creates a deep copy of the queue. How do we do that? We create an empty queue named “clone”. If the original queue is empty we just return the empty clone queue. If it is not empty however, we have to make the deep copy. It’s very simple. We have a reference(node) called “currentNode” that first points to the front of the original queue. This node helps us to walk through the original queue from the front to the back. We say this: “while currentNode != null (we haven’t reached the end of the queue) – enqueue the value of the current node we’ve reached into the clone queue and go to the next node of the original queue”. Then we return the clone.

It looks like this:

queue-clone-process

I’ve also added some extension methods in the CustomQueue class. They are helpful, plus helped me for the unit tests.

public override string ToString()
{
	StringBuilder result = new StringBuilder();

	Node currentNode = this.front;
	while (currentNode != null)
	{
		result.Append(currentNode.Item);
		currentNode = currentNode.Next;
	}

	return result.ToString();
}

public T[] ToArray()
{
	T[] result = new T[this.count];

	Node currentNode = this.front;
	for (int i = 0; i < result.Length; i++)
	{
		result[i] = currentNode.Item;
		currentNode = currentNode.Next;
	}

	return result;
}

“ToString” and “ToArray” are much like the clone method. We are walking through the original queue and the value of the current node we’ve reached is appended in a StringBuilder in the first case, and put in an array in the second case.

The CustomQueue also implements the IEnumerable<T> interface so that the queue can be walked with a foreach loop.

public IEnumerator<T> GetEnumerator()
{
	Node currentNode = this.front;
	while (currentNode != null)
	{
		T result = currentNode.Item;
		currentNode = currentNode.Next;

		yield return result;
	}
}

IEnumerator IEnumerable.GetEnumerator()
{
	return this.GetEnumerator();
}

The IEnumerable and IEnumerator interfaces are hard to explain and this post does not concern them, so I will stop here. Maybe I will make a post on how to implement these interfaces the hard way and the easy way (here I’ve used the easy way). That’s all. Hope it was useful.

Snake Game with JavaScript

I will show you how to make a snake game very easy with pure JavaScript and Canvas. Here’s the demo and the full source

I will explain about the score system last. Lets first see how the snake is implemented. First of all it’s good to place the full JavaScript code into a clojure. That way all the variables are not global.

It should look something like that:

(function () {
    // The full source here
}());

Ok now. Lets start. What do we need for a snake game? We need a queue (for the snake body). I’ve made a simple queue implementation that looks like this:

function Queue() {
	var that = this;
	that.arr = [];
}

Queue.prototype = {
	constructor: Queue,

	enqueue: function (elem) {
		this.arr.push(elem);
	},

	dequeue: function () {
		var retValue = this.arr[0];
		var newArr = new Array(this.arr.length - 1);
		for (var i = 0; i < newArr.length; i++) {
			newArr[i] = this.arr[i + 1];
		}

		this.arr = newArr;
		return retValue;
	},

	getFirstElem: function () {
	    return this.arr[0];
	},

	getLastElem: function () {
	    return this.arr[this.arr.length - 1];
	},

	elementAt: function (index) {
	    return this.arr[index];
	},

	length: function () {
		return this.arr.length;
	}
}

As you can see it’s not a basic queue implementation. We have functions to get elements at any index, to get the first and last elements. I don’t think there is something special about it. Just a queue.

We also need coordinates. You can consider the playfield as a coordinate system. You can think of the “Coords” class as a “Vector” class.

function Coords(x, y) {
	var that = this;
	that.x = x * 10;
	that.y = y * 10;
}

Ok now. You may ask why the “x” and “y” are multiplied by 10?
It’s simple. The coordinates are actually pixels on the screen. If the step of the snake is only 1 pixel it will be almost impossible to tell that the snake even moved. That’s why I made the step 10 pixels. When the snake head moves from coordinates (10, 20) to (20, 20) you will definitely see it moving. This is a bad approach, because the constructor is modifying the values, we just gave him. I am making this for simplicity. Just note that internally the values are multiplied by 10.

Ok. We can’t make a snake game without a snake can we?

function Snake(x, y, bodyLength) {
	var that = this;
	that.snakeBody = new Queue();
	for (var i = 0; i < bodyLength; i++) {
		that.snakeBody.enqueue(new Coords(x + i, y));
	}

	that.currentDirection = new Coords(1, 0);
	that.head = that.snakeBody.getLastElem();
}

Snake.prototype = {
    constructor: Snake,

    getHead: function () {
        return this.head;
    },

    getNextHead: function () {
        var nextHead =
            new Coords(
                parseInt(this.head.x + this.currentDirection.x) / 10,
                parseInt(this.head.y + this.currentDirection.y) / 10
            );

        return nextHead;
    },

    move: function () {
        var nextHead = this.getNextHead();
        this.snakeBody.enqueue(nextHead);
        this.snakeBody.dequeue();

        this.head = nextHead;
    },

    turnLeft: function () {
        if (this.currentDirection.x !== 1 && this.currentDirection.y !== 0) {
            var leftDirection = new Coords(-1, 0);
            this.currentDirection = leftDirection;
        }
    },

    turnRight: function () {
        if (this.currentDirection.x !== -1 && this.currentDirection.y !== 0) {
            var rightDirection = new Coords(1, 0);
            this.currentDirection = rightDirection;
        }
    },

    turnUp: function () {
        if (this.currentDirection.x !== 0 && this.currentDirection !== 1) {
            var upDirection = new Coords(0, -1);
            this.currentDirection = upDirection;
        }
    },

    turnDown: function () {
        if (this.currentDirection.x !== 0 && this.curentDirection !== -1) {
            var downDirection = new Coords(0, 1);
            this.currentDirection = downDirection;
        }
    }
}

Lets see what we have in the constructor?
We have a snake body, which is a queue of coordinates. The snake also has a head and current direction. The current direction is also a coordinate. All of the possible directions are:

var leftDirection = new Coords(-1, 0);
var rightDirection = new Coords(1, 0);
var upDirection = new Coords(0, -1);
var downDirection = new Coords(0, 1);

It’s very simple. The left direction has x = -1 and y = 0. The coordinate system is a normal coordinate system (just how you know it from Math). If the snake head is at coordinates (5, 5) and we add the leftDirection speed vector to it, the snake head will go to coordinates (4, 5). That’s the secret of mooving objects in a coordinate system. However the snake moves differently. I will explain when the time comes.

First lets see what methods(functions) the snake has:

getHead: function () {
    return this.head;
}

There is not need to tell you what this function does.

getNextHead: function () {
    var nextHead =
        new Coords(
            parseInt(this.head.x + this.currentDirection.x) / 10,
            parseInt(this.head.y + this.currentDirection.y) / 10
        );

    return nextHead;
}

This function returnes the next head of the snake. What does that mean? At any state of the game the snake has a current direction. Lets imagine that the snake head is at coordinates (5, 5) and the currentDirection is (-1, 0). The next head of the snake will be on (5, 5) + (-1, 0) = (4, 5) coordinates. The getNextHead function is needed because we want to know if the snake will reach it’s body or one of the side wall before it actually happened. This function helps us in many ways (even for the moving of the snake). You may ask why I am dividing the the “x” and “y” coordinates of the nextHead by 10? Do you remember that the coordinates are actually multiplied by 10? If we say “var nextHead = new Coords(4, 5)” the coordinates will actually be (40, 50). We want them to be (4, 5). So we are creating the nextHead like this “var nextHead = new Coords(0.4, 0.5)”. That’s all.

move: function () {
    var nextHead = this.getNextHead();
    this.snakeBody.enqueue(nextHead);
    this.snakeBody.dequeue();

    this.head = nextHead;
}

Ok, we’ve finally reached the moving of the snake. It’s tricky here. First of all you have to understand this. The snake head is not the first element of the queue, it’s actually the last element. The tail of the snake is the first element of the queue. Let me explain. When we enqueue a new element to the queue, it is put at the end of queue. When we dequeue an element from the queue, the first element is removed from the queue. I think you are starting to figure it out. How does the snake move? First we want to get the next head of the snake. We already have a nice function for that. We now have the next head. The next thing to do is to put it in the snake’s body “this.snakeBody.enqueue(nextHead)”. Now we have moved the snake. The problem is that the snake is actually bigger now (we just added a new head). So we remove the end of the tail “this.snakeBody.dequeue()”. The next step to do is to assign the snake’s head to the new head “this.head = nextHead”. That’s how the snake moves. I hope you understood it.

Now comes the “change direction functions”.
I will explain only the “turnLeft()” function. The others are analogous.

turnLeft: function () {
    if (this.currentDirection.x !== 1 && this.currentDirection.y !== 0) {
        // currentDirection != rightDirection
        var leftDirection = new Coords(-1, 0);
        this.currentDirection = leftDirection;
    }
}

You may ask why it is so complex? Well we can’t just say “this.currentDirection = leftDirection”. If the current direction is different from rightDirection, then it’s fine. Lets imagine that the currentDirection = rightDirection. If we change it to left the snake head will hit it’s body. That’s why we have a restriction. If the snake current direction is not right direction, then change it, else don’t do anything.

So far, so good.
We need food. The snake needs to eat.

function Food(width, height) {
    var minWidth = 10;
    var maxWidth = width - 10;
    var minHeight = 10;
    var maxHeight = height - 10;

    var x = parseInt((Math.random() * (maxWidth - minWidth) + minWidth) / 10);
    var y = parseInt((Math.random() * (maxHeight - minHeight) + minHeight) / 10);

    this.coords = new Coords(x, y);
}

As you can see the food has coordinates too. The thing is that they must be generated randomly. The food can be generate anywhere on the screen, we however want the food to be generated in the playfield. That’s why we pass as arguments the width and the height of the field. “minWidth = 10”, because the field has borders that are exactly 10 pixels wide. The other min and max widths and heights are analogous. I’ve made everything in the game 10 pixels wide. You already know why we divide the “x” and “y” coordinates by 10.

Now we have almost everything we need for a snake game. What we don’t have is a renderer. For the rendering we’ll use canvas. Canvas is a JavaScript API capable of visualizing 2D ad 3D graphics in the browsed. 3D is not fully implemented yet, but for a snake game 2D is just fine. You can learn more about canvas in Developer Mozilla.

Lets see what functions we have:

function drawField(ctx, width, height) {
    ctx.save();

    ctx.fillStyle = "#000";
    ctx.fillRect(0, 0, width, height);

    ctx.fillStyle = "#00f";
    ctx.strokeStyle = "#000";

    // Draws the upper and lower borders
    for (var i = 0; i < width; i += 10) {
        ctx.fillRect(i, 0, 10, 10);
        ctx.strokeRect(i, 0, 10, 10);

        ctx.fillRect(i, height - 10, 10, 10);
        ctx.strokeRect(i, height - 10, 10, 10);
    }

    // Draws the left and right borders
    for (var i = 0; i < height; i += 10) {
        ctx.fillRect(0, i, 10, 10);
        ctx.strokeRect(0, i, 10, 10);

        ctx.fillRect(width - 10, i, 10, 10);
        ctx.strokeRect(width - 10, i, 10, 10);
    }

    ctx.restore();
}

This function draws the playfield. It fills the background color and draws the border. The border consists of many small squares. You can learn how to use canvas in the link I gave you.

The next is the drawing of the food.

function drawFood(ctx, food) {
    ctx.save();

    ctx.fillStyle = "#0f0";
    ctx.strokeStyle = "#000";
    ctx.fillRect(food.coords.x, food.coords.y, 10, 10);
    ctx.strokeRect(food.coords.x, food.coords.y, 10, 10);

    ctx.restore();
}

We just take the food’s coordinates and fill a 10×10 pixels rectangle there.

And of course the drawing of the snake:

function drawSnake(ctx, snake) {
    ctx.save();

    ctx.fillStyle = "#f00";
    ctx.strokeStyle = "#000";

    var snakeBody = snake.snakeBody;
    for (var i = 0; i < snakeBody.length(); i++) {
        var snakeElem = snakeBody.elementAt(i);
        ctx.fillRect(snakeElem.x, snakeElem.y, 10, 10);
        ctx.strokeRect(snakeElem.x, snakeElem.y, 10, 10);
    }

    ctx.restore();
}

For each element in the snake’s body we fill a 10×10 rectangle at it’s coordinates.

Next thing we need is the logic of the game. It consists of two things: initialization and game loop.

Let us first see the initialization:

var canvas = document.getElementsByTagName("canvas")[0];
var width = canvas.width;
var height = canvas.height;
var ctx = canvas.getContext("2d");

var snake = new Snake(5, 5, 5);
var food = new Food(width, height);
var score = 0;

var scoreDiv = document.getElementById("score");
scoreDiv.style.fontWeight = "bold";
scoreDiv.innerHTML = "Score: " + score;

window.onkeydown = function (ev) {
    switch (ev.keyCode) {
        case 37:
            snake.turnLeft();
            break;
        case 38:
            snake.turnUp();
            break;
        case 39:
            snake.turnRight();
            break;
        case 40:
            snake.turnDown();
            break;
    }
}

First we take the canvas element and get it’s width, height and 2D context.

Next we initialize our snake. The tail is on coordinates (5, 5) and the length of the snake is 5.
Then we generate our food in a field large enough to fit in the canvas.
We also initialize a score. The score is displayed in a div with id=”score”.

Next thing we need is to navigate the snake. That’s accomplished by adding events to the window. The event object has a property called keyCode. When we press a key, that keyCode contains the code of the pressed key. The left, up, right and down arrows codes are 37, 38, 39 and 40.

The next import thing is the game loop.

function run(ctx, snake, width, height) {
    var nextHead = snake.getNextHead();
    var snakeBody = snake.snakeBody;

    // check for collision with itself
    for (var i = 0; i < snakeBody.length(); i++) {
        var elem = snakeBody.elementAt(i);
        if (elem.x === nextHead.x && elem.y === nextHead.y) {
            saveScore(score);
            restartGame();
        }
    }

    // check for collision with side walls
    if (nextHead.x <= 0 ||
            nextHead.x >= width - 10 ||
            nextHead.y <= 0 ||
            nextHead.y >= height - 10) {
        saveScore(score);
        restartGame();
    }

    // check for collision with food
    for (var i = 0; i < snakeBody.length() ; i++) {
        var elem = snakeBody.elementAt(i);
        if (elem.x === food.coords.x && elem.y === food.coords.y) {
            var snakeNextHead = snake.getNextHead();
            snake.snakeBody.enqueue(snakeNextHead);
            snake.head = snakeNextHead;
            food = new Food(width, height);
            score += 100;
            scoreDiv.innerHTML = "Score: " + score;
            break;
        }
    }

    snake.move();
    drawField(ctx, width, height);
    drawFood(ctx, food);
    drawSnake(ctx, snake);
}

This is the function that we want to be executed on every iteration of the game loop. We take the snake’s head and body and check for collisions (with itself, with side walls(border) and with food).
The collisions with itself are easy (if the snake’s nextHead equals some of the snake’s body coordinates, then the snake hit itself). Don’t mind the “saveScore” and “restartGame” functions, I will explain them later.
The collisions with the border are easy too (if the snake’s nextHead equals one of the side walls coordinates, then the snake hit the border).
The collisions with the food are trickier. Imagine that a food is generate on the top of the snake. The snake can’t eat it because it will eat itself too. That’s why I made it like that (if any of the coordinates of the snake’s body equals the food’s coordinates, then the food is eaten). Unfortunately sometimes you will get points just because the food was spawned on the top of the snake. Anyway, when we the snake eats a food, we increase the score by 100, generate a new food and of course we expand the snake. The expanding is just like the moving function, we just don’t remove the end of the tail.
When all of the collisions were dispatched we can finally call the snake’s move() method and draw a frame.

Now we have to put that function into an infinite loop. Infinite loops don’t work in JavaScript, but we have a very nice function for that “setInterval(func, milliseconds)”. setInterval calls “func” every N milliseconds.

function gameLoop() {
    run(ctx, snake, width, height);
}

setInterval(gameLoop, 100);

We are almost ready. If you don’t want to know how the score system is implemented you can just skip this part. But hey, what’s a game without a score system?

First let me show you the restartGame() function.

function restartGame() {
    document.location.reload(false);
}

Very simple. The page is reloaded.

And here is the saveScore(score) function

function saveScore(score) {
    var name = prompt("GAME OVER!\nEnter nickname:");
    if (localStorage[name]) {
        if (localStorage[name] < score) {
            localStorage[name] = score;
        }
    }
    else {
        localStorage[name] = score;
    }
}

When the game is over the player is asked for a nickname and a key->value pair (name->score) is saved in the localStorage of the browser. It’s not the most elegant mechanism, but I wanted to make it as simple as possible. As fast as possible too of course :D. The tricky part is that we need to ask if the played has already signed his name and score. That way if you play and score 100, and on the second play your score is 500, there wont be two scores with a same nickname, your score will just be updated.

How do we display the rank list in the browser?
Well, that’s how!

(function loadTopFiveScores() {
    function Pair(key, value) {
        this.key = key;
        this.value = value;
    }

    var allScores = [];
    for (var prop in localStorage) {
        allScores.push(new Pair(prop, localStorage[prop]));
    }

    // sort the scores
    for (var i = 0; i < allScores.length - 1; i++) {
        var maxScoreIndex = i;
        for (var j = i + 1; j < allScores.length; j++) {
            if (parseInt(allScores[j].value) > parseInt(allScores[maxScoreIndex].value)) {
                maxScoreIndex = j;
            }
        }

        var temp = allScores[i];
        allScores[i] = allScores[maxScoreIndex];
        allScores[maxScoreIndex] = temp;
    }

    // load the top five scores
    var rankList = document.getElementById("rank-list");
    var length;
    if (allScores.length < 5) {
        length = allScores.length;
    }
    else {
        length = 5;
    }

    for (var i = 0; i < length; i++) {
        var div = document.createElement("div");
        div.innerHTML = allScores[i].key + ": " + allScores[i].value;
        rankList.appendChild(div);
    }
})();

Looks frightening, but it’s not. First we make a Pair class (a key->value pair). Then we save all of the key->value pairs in an array called allScore. We sort the scores by value (with simple selection sort algorithm). We also want to display only the top five scores. Well the scores are sorted so we need to take only the last five. For every score we make a div element and append it to the div with id=”rank-list”. If you want to optimize the appending process, you can do it with documentFragment.

I’ve also made a button for clearing the localStorage.

var storageCleanerButton = document.getElementById("storage-clear");
storageCleanerButton.addEventListener("click", clearScore, false);

function clearScore() {
    localStorage.clear();
    var rankList = document.getElementById("rank-list");
    rankList.innerHTML = "Top Five";
}

Congratulations, you’ve reached the end of this huge post 😀

Dynamic Stack Implementation – C#

A dynamic stack is a stack that is implemented not with an array but with nodes. A node consists of two things (a value and a link to another node).

The next image illustrates the stack.

dynamic-stack

You can find the full source here.

Lets see how the Node is implemented.

private class Node
{
    public T Item { get; set; }
    public Node Next { get; set; }

    public Node(T item)
    {
        this.Item = item;
        this.Next = null;
    }

    public Node(T item, Node next)
    {
        this.Item = item;
        this.Next = next;
    }
}

In my implementation the value is called Item and the link to the next node is a Node reference called Next. We also have two constructors. One that creates a node with a given item and a link that points to null, and one that creates a node with a given item and a link that points to a node different than null.

What do we have?

private Node top;
private int count;

public CustomStack()
{
    this.top = null;
    this.count = 0;
}

public int Count
{
    get
    {
        return this.count;
    }
}

We have a node that points to the top of the stack. The count is optional but it’s always better to know how many items we have in a stack. We have only a simple default constructor that initializes our stack. The top is null and the count is zero when the stack is created. We also have a property for the count with getter only.

Not lets see how the basic methods are implemented.

public void Push(T item)
{
    if (this.top == null)
    {
        // We have empty stack
        this.top = new Node(item);
    }
    else
    {
        Node newNode = new Node(item, this.top);
        this.top = newNode;
    }

    this.count++;
}

The “Push” method adds a new node to the stack. If the stack is empty, then we create a new node that points to null. This new node is the only element in the stack (the stack top). If the stack is not empty however, a new node is created. This node has to be the top of the stack so we point it’s link to the stack top. Then the top node starts to point the new node (the new node becomes the top of the stack).

Lets see it with our eyes.
Consider the following code:

CustomStack<int> stack = new CustomStack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);

In the memory it should look something like this:

stack-push

public T Peek()
{
    if (this.count == 0)
    {
        // We have empty stack
        throw new InvalidOperationException("The stack is empty");
    }

    return this.top.Item;
}

The “Peek” method gets the value of the top without removing the top from the stack. If the stack is empty however, an InvalidOperationException is thrown.

public T Pop()
{
    if (this.count == 0)
    {
        // We have empty stack
        throw new InvalidOperationException("The stack is empty");
    }

    T result = this.top.Item;
    this.top = this.top.Next;
    this.count--;

    return result;
}

The “Pop” is almost the same as “Peek”. The difference is that it not only gets the value of the top but it also removes the top from the stack. The value is taken and the top is assigned to it’s link (next node). The count is decremented. Finally the value is returned.

Consider the following code:

CustomStack<int> stack = new CustomStack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);

stack.Pop();
stack.Pop();
stack.Pop();

The popping process looks like this:

stack-pop

public void Clear()
{
    this.top = null;
    this.count = 0;
}

“Clear” clears the stack. It’s just like the constructor. We initialize the top with null and the count with 0.

public object Clone()
{
    CustomStack clone = new CustomStack();

    if (this.count != 0)
    {
        // We have non-empty stack
        clone.top = new Node(this.top.Item);
        Node currentNode = this.top.Next;
        Node cloneLastNode = clone.top;

        while (currentNode != null)
        {
            Node newNode = new Node(currentNode.Item);
            cloneLastNode.Next = newNode;
            cloneLastNode = newNode;
            currentNode = currentNode.Next;
        }

        cloneLastNode.Next = null;
        clone.count = this.count;
    }

    return clone;
}

This is maybe the most complex method of all. If the stack is empty the job is easy. We just make an empty stack and returned it. If it is not, then we have to make the actual copy. This method makes a deep copy. That means that the two stacks don’t depend on each other. They are equal, but not the same (don’t share the same reference). How do we do that? First we make the clone a copy of the top. The “currentNode” is a helper node that will walk through the original stack from the top to the end. The “cloneLastNode” is the last node of the clone stack at any state of the copying progress. At first the “cloneLastNode” is the top of the clone stack. While “currentNode” is not null (we haven’t reached the original stack’s end) we make a new node exactly the same as the current node we’ve reached. Then the last node of the clone stack is linked to the new node and then is assigned to it. That way in the next iteration this can be repeated. The “currentNode” is also assigned to it’s link. Last we link the last node of the clone stack to null and copy the count of the original stack. I can say it like that: “while we haven’t reached the end of the stack, create a new node with value equal to the value of the current node we’ve reached, link the last node of the clone stack with the new node and make the last node of the clone to be the new node, then go to the next node of the original stack. Last the link of the last node of the clone stack is initialized with null”.

You just have to think it through and try to write it in a paper.
It’s very hard to be explained, maybe a picture will help:

stack-clone

The next methods are not basic for Stack implementation but are helpful sometimes. You can consider them as extensions.

public override string ToString()
{
    StringBuilder result = new StringBuilder();

    Node currentNode = this.top;
    while (currentNode != null)
    {
        result.Append(currentNode.Item.ToString());
        currentNode = currentNode.Next;
    }

    return result.ToString();
}

I’ve overrided the ToString method. It’s very simple. The stack is walked through from the top to the end and the values of the nodes are appended to a StringBuilder.

public T[] ToArray()
{
    T[] result = new T[this.count];

    Node currentNode = this.top;
    for (int i = 0; i < this.count; i++)
    {
        result[i] = currentNode.Item;
        currentNode = currentNode.Next;
    }

    return result;
}

Exactly the same as ToString. The difference is that the values of the nodes are put into an array.

public IEnumerator GetEnumerator()
{
    Node currentNode = this.top;
    while (currentNode != null)
    {
        T result = currentNode.Item;
        currentNode = currentNode.Next;

        yield return result;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return this.GetEnumerator();
}

This one is hard to be explained. My stack implements IEnumerable<T>. That way it can be walked through with a foreach loop. If you want to learn about it you can find a lot of information in MSDN or other resources. Maybe I will make a different post to explain how to implement this interface the hard way and the easy way.