Data Structure And Algorithm - Implementing Custom Stack

Hello friends,

In the previous article, we have gone through how to choose the right data structure. If you want to refer to it, you may go to Data Structure And Algorithm - Choosing The Right Data Structure

Today we are going to implement the custom stack.

Let’s begin with defining the stack.

Stack

Stack is one of the most basic data structures that allows access only to the last element inserted. It follows Last in first out (LIFO).

Below diagram illustrates Push and Pop operations in Stack.

Following are some of the Important methods and properties used in stack.

• Insert/Push() – Inserts an element into Stack
• Remove/Pop() - Remove an element from Stack
• MakeEmpty() – Clears the stack
• Top/Peek() – Returns the last inserted element from Stack
• isEmpty() – Check if Stack is empty or not
• IsFull() - Check if Stack is full or not

Time Complexity

Stack can be implemented using Linked List and Array. The complexity is determined as follows.

Linked list with a pointer on the head

• Insert: O(1)
• Delete: O(1)

Array

• Insert: O(n), amortized time O(1)
• Delete: O(1)

To clarify, the amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm. This may include accounting for different types of input, length of the input, and other factors that affect its performance.

Algorithm

Push

begin procedure push: stack, data
   if stack is full
      return null
   endif
   top ← top + 1
   stack[top] ← data
end procedure

Pop

begin procedure pop: stack
   if stack is empty
      return null
   endif
   data ← stack[top]
   top ← top - 1
   return data
end procedure

Peek

begin procedure peek
   return stack[top]
end procedure

IsFull

begin procedure isfull
   if top equals to MAXSIZE
      return true
   else
      return false
   endif
end procedure

IsEmpty

begin procedure isempty
   if top less than 1
      return true
   else
      return false
   endif
end procedure

In the above paragraph, we’ve gone through the algorithms used in Stack. Now let’s see how can we implement them using C# 

Implementation using C#

Push

static void Push(int data) {
    if (!isFull()) {
        top = top + 1;
        stack[top] = data;
        Console.WriteLine($ "Member {data} is pushed.");
    } else {
        Console.WriteLine("Could not insert data, Stack is full.\n");
    }
}

Pop

static void Pop() {
    if (!isEmpty()) {
        data = stack[top];
        stack[top] = -1;
        top = top - 1;
        Console.WriteLine($ "Member {data} is popped.\n");
    } else {
        Console.WriteLine("Could not retrieve data, Stack is empty.\n");
    }
}

Peek

static int Peek() {
    if (top != -1) return stack[top];
    else return -1;
}

IsFull

static bool isFull() {
    if (top == MAXSIZE) return true;
    else return false;
}

IsEmpty

static bool isEmpty() {
    if (top == -1) return true;
    else return false;
}

Summary

You can refer to the working demo here.

In today’s article, we have learned about various methods and properties involved in designing stack followed by the time complexity of key stack operations. We looked into different algorithms used in the most common stack methods. Towards end, we have seen how the stack operations can be implemented using C#.

Hope this article was useful to you. You can let me know for any comment and feedback.