List Implementation of Stacks(C#, Java, C++, C)

Here is my List implementation of stack(Sample Code).
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
C#

//StackADTList.cs
using System;
using System.Collections.Generic;

namespace StackUsingLists
{
public class StackADTList
{
    int _top = -1;
    List<int> listStack = null;

    //We can implement automatically growable Stack as well normal size restricted stack also
    //Here we will see limited and size restricted stack.
    public StackADTList(int nCapacity)
    {
        listStack = new List<int>(nCapacity);
        _top = -1;
    }

    public int Top
    {
        get{ return _top;}
    }

    public int StackSize
    {
        get{return listStack.Capacity;}
    }

    public void push(int item)
    {
        if ((_top + 1) == StackSize)
            throw new Exception("Stack Overflow");
        _top = _top + 1;
        listStack.Add(item);
    }

    public int pop()
    {
        if (_top < 0)
            throw new Exception("Stack Underflow");
        int item = listStack[_top];
        listStack.RemoveAt(_top);
        _top = _top - 1;
        return item;
    }

    public bool isFull()
    {
        if ((_top + 1) == StackSize)
            return true;
        else
            return false;
    }

    public bool isEmpty()
    {
        if (_top < 0)
            return true;
        else
            return false;
    }

    public override string ToString()
    {
        string strItems = "Stack : ";
        if (isEmpty())
        {
           strItems += "empty";
        }
        else
        {
            foreach(int item in listStack)
            {
                strItems += item + " ";
            }
        }
        return strItems;
    }
}
}

//Program.cs
using System;
namespace StackUsingLists
{
class Program
{   
        static void Main(string[] args)
    {       
         try
        {
            StackADTList objListStack = new StackADTList(10);

            objListStack.push(10);
            objListStack.push(25);
            objListStack.push(50);
            Console.WriteLine(" " + objListStack.ToString());
            objListStack.pop();
            objListStack.pop();
            objListStack.pop();
            Console.WriteLine(" " + objListStack.ToString());
            objListStack.pop();
        }
        catch (Exception exp)
        {
            Console.WriteLine("Error : " + exp.Message);
        }
        Console.Read();
    }
}
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Java

Note: Sorry for formatting, i will try to update as it is looks like in my IDE

package stacksadtlist;
import java.util.LinkedList;
class StacksADT
{
int _top;
int _size;
LinkedList objList = null;
public StacksADT(int nSize)
{
_size = nSize;
_top = -1;
objList = new LinkedList();
}
public int Size()
{
return objList.size();
}
public int TopIndex()
{
return _top;
}
public void push(int item) throws Exception
{
if((_top + 1) == _size)
{
throw new Exception("Stack Overlow");
}
_top = _top + 1;
objList.add((Integer)item);
}
public int pop() throws Exception
{
if(_top < 0)
{
throw new Exception("Stack Underflow");
}
int tmpItem = objList.remove(_top);
_top = _top - 1;
return tmpItem;
}
public boolean isFull()
{
if((_top + 1) == Size())
return true;
else
return false;
}
public boolean isEmpty()
{
if(_top < 0)
return true;
else
return false;
}

@ Override
public String toString()
{
String strItems = "Stack : ";
if (isEmpty())
{
strItems += "Empty";
} else {
for (int i = 0; i <= _top; i++) {
strItems += objList.get(i) + " ";
}
}
return strItems;
}
}

public class StacksADTList
{
public static void main(String[] args)
{
try
{
StacksADT objStack =new StacksADT(10);
objStack.push(10);
objStack.push(25);
objStack.push(50);
System.out.println(objStack.toString());

objStack.pop();
objStack.pop();
objStack.pop();
System.out.println(objStack.toString());

objStack.pop();

}
catch(Exception exp)
{
System.out.println("" + exp.getMessage());
}
try
{
System.in.read();
}
catch(Exception exp1)
{
//DOn't do anything
}
}
}


++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
C++

I will update very soon
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
C

#include <stdio.h>
#include <stdlib.h>

struct node
{
   int data;
   struct node *nextNode;
}*head, *current, *tmp;

int top;
int stacksize = 10;
int data;

void push(int);
int pop();
int isFull();
int isEmpty();
void printStack();

int main(int argc, char *argv[])
{
    int exitCondition = -1;
    int data;
    top = -1;
    //initializing Head
    head =  malloc(sizeof(struct node));
    if( head == NULL)
    {
        printf("Memory Error");
        return;
    }
    head->data = -999;
    head->nextNode = NULL;
    current = head;
    //Temporary node for traversing through the list
    tmp = malloc(sizeof(struct node));
    if( tmp == NULL)
    {
       printf("Memory Error");
       return;
    }
    tmp = head;
    
    //Stack Menu
    do
    {
        printf("\nSelect an Operation \n");
        printf("1. Push\n");     
        printf("2. Pop\n");
        printf("3. Is Stack Empty\n");
        printf("4. is Stack Full\n"); 
        printf("5. Print Stack\n"); 
        printf("6. Exit\n");  
        scanf("%d",&exitCondition); 
         
        switch(exitCondition)
        {
             case 1:
                  printf("Enter a number to push into the stack \n");
                  scanf("%d", &data);
                  push(data);
                  printStack();
                  break;
             case 2:
                  data = pop(); 
                  if(data == head->data)
                  {
                      printf("Stack :Underflow");    
                  }
                  else
                  {
                      printf(" %d reomved from the stack\n", data); 
                      printStack();
                  }
                  break;
             case 3: 
                  data = isEmpty(); 
                  if(data == 1)
                  {
                      printf(" Stack : Empty\n", data);
                  } 
                  break;
             case 4:                   
                  data = isFull(); 
                  if(data == 1)
                  {
                      printf(" Stack : Full\n", data);
                  } 
                  break;
             case 5:
                  printStack();
                  break;
             case 6:
                  break;
             default:
                  printf("Please enter a valid option. \n");
                  system("EXIT");
        }
    }
    while(exitCondition != 6);
  system("PAUSE"); 
  return 0;
}

void push(int item)
{
   //Creating the new node in the list - start
   struct node *newNode;
   newNode = malloc(sizeof(struct node));
   if( newNode == NULL)
   {
       printf("Memory Error");
       return;
   }
   newNode->data = item;    
   newNode->nextNode = NULL;
   //Creating the new node in the list - end
   
   if((top + 1) == stacksize)
      printf("Stack : Overflow \n");
   top = top + 1;
   if( current != NULL)
   {
      current->nextNode = newNode;
      current = newNode;  
   }    
}

int pop()
{
    if(top < 0)
    {
      data = head->data;    
    }
    else
    {
       top = top - 1;
       data = current->data;
       //here we need to do some extra coding for removing the lst node in the list
       tmp = head;
       while(tmp->nextNode != NULL)
       {
          if(tmp->nextNode == current)
          {
              current = tmp;
              current->nextNode = NULL;
              break;
          }
          tmp = tmp->nextNode;
       }
       tmp = head;
    }
    return data;
}
int isFull()
{
    if((top+1)  == stacksize)
        return 1;
    else
        return 0;
}
int isEmpty()
{
    if(top < 0)
        return 1;
    else
        return 0;
}
void printStack()
{ 
    printf("Stack :");
    if(top < 0 )
    {
        printf(" Empty");   
    }
    else
    {   
        tmp = head;     
        do
        {
            tmp = tmp->nextNode;
            if(tmp!=NULL)
            { 
               printf ("%d ", tmp->data); 
            } 
        }
        while(tmp->nextNode != NULL);
    }
    printf("\n");
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Array Implementation of Stacks(C#, Java, C++, C)

Here is my Array Implementation of stack(Sample Code)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
C#

//StackADT.cs
using System;
namespace Stacks
{
public class StackADT
{
//Array for storing stack elements
private int[] items = null;
//Stack size
private int _size = 0;
//Top index
private int _top = -1;
//Read only property, because to stop modifying the size of the stack during the operation
public int Size
{
get {return _size;}
}

//Standard Stack Operations - start 
//Constructor - for creating and initializing the stack
public StackADT(int nSize)
{
this._size = nSize;
items = new int[_size];
}
//Getting the index of top element
public int Top
{
get {return this._top;}
}
//For inserting elements in to Stack
public void push(int item)
{
if (_top == (_size - 1))
  throw new Exception("Stack Overflow");
items[++_top] = item;
}
//For deleting elements in to Stack
public int pop()
{
if (_top < 0)
  throw new Exception("Stack Underflow");
return items[_top--];
}
public bool isFull()
{
if (_top == (_size - 1))
  return true;
return false;
}
public bool isEmpty()
{
if (_top < 0)
  return true;
return false;
}
//Stack Operations - end

//Just for printing  the Stack
public override string ToString()
{
String strItems = "";
if (isEmpty())
{
  strItems = "Stack Empty";
}
else
{
  for (int i = 0; i <= _top; i++)
  {
      strItems += items[i] + "  ";
  }
}
Console.WriteLine("" + strItems);
return strItems;
}
}
}

//Program.cs

using System;
namespace Stacks
{
class Program
{
static void Main(string[] args)
{
StackADT objStack = new StackADT(10);
try
{
  objStack.push(10);
  objStack.push(25);
  objStack.push(50);
  objStack.ToString();
  objStack.pop();
  objStack.pop();
  objStack.ToString();
  objStack.pop();
  objStack.ToString();
  objStack.pop();
  objStack.Restring();
}
catch (Exception exp)
{
  Console.WriteLine("" + exp.Message);
}
Console.ReadLine();
}
}
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
C++

//StackADT.h
class StackADT
{
   int _top;
   int _size;
   int* Items;
public:
StackADT(int);
~StackADT(void);
   void push(int);
   int pop();
   int getTop();
   bool isFull();
   bool isEmpty();
   void DisplayStack();
};

//StackADT.cpp

#include "StackADT.h"
#include <iostream>
#include <ios> 
using namespace std;
StackADT::~StackADT(void)
{
}
StackADT::StackADT(int nSize)
{
Items =new int[nSize];
_top = -1;
_size = nSize;
}
void StackADT::push(int item)
{
   if((_top + 1) == _size)
{
cout << "Stack Overflow" << endl;
      return;
}
_top = _top + 1;
Items[_top] = item;
}
int StackADT::pop()
{
   if (_top < 0)
{
cout << "Stack Underflow" << endl;
      return -1;
}
   int item = Items[_top];
_top = _top - 1;
return item;
}
int StackADT::getTop()
{
return _top;
}
bool StackADT::isEmpty()
{
if (_top < 0)
      return true;
   return false;
}
bool StackADT::isFull()
{
   if (_top == _size)
      return true;
return false;
}
void StackADT::DisplayStack()
{
if(isEmpty())
{
cout << "Stack Empty" << endl;
}
   else
{
      for(int i=0;i<=_top;i++)
{
cout << Items[i] << "  ";
}
}
cout << endl;
}

//Stacks.cpp

#include <iostream>
#include "StackADT.h"
using namespace std;

int main()
{
StackADT objStack(10);
objStack.push(10);
objStack.push(25);
objStack.push(50);
objStack.DisplayStack();
objStack.pop();
objStack.pop();
objStack.DisplayStack();
objStack.pop();
objStack.DisplayStack();
objStack.pop();
objStack.DisplayStack();
    return 0;
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Java

//StackADT.java
package stacks;
public class StackADT
{
//Array for storing stack elements
private int[] items = null;
//Stack size
private int _size = 0;
//Top index
private int _top = -1;

//Read only property, because to stop modifying the size of the stack during the
//operation
public int getSize() {
 return _size;
}
//Standard Stack Operations - start 

//Constructor - for creating and initializing the stack
public StackADT(int nSize) {
 this._size = nSize;
 items = new int[_size];
}

//Getting the index of top element
public int getTop() {
 return this._top;
}

//For inserting elements in to Stack
public void push(int item) throws Exception {
 if (_top == (_size - 1)) {
     //System.out.println("Stack Overflow");
     throw new Exception("Stack Overflow");
 }
 items[++_top] = item;
}

//For deleting elements in to Stack
public int pop() throws Exception {
 if (_top < 0) {
     //System.out.println("Stack Underflow");
     throw new Exception("Stack Underflow");
 }
 return items[_top--];
}

public boolean isFull() {
 if (_top == _size) {
     return true;
 }
 return false;
}

public boolean isEmpty() {
 if (_top < 0) {
     return true;
 }
 return false;
}
//Stack Operations - end

//Just for printing  the Stack
@ Override
public String toString() {
 String strItems = "";

 if (isEmpty()) {
     strItems = "Stack Empty";
 } else {
     for (int i = 0; i <= _top; i++) {
         strItems += items[i] + "  ";
     }
 }
 System.out.println("" + strItems);
 return strItems;
}
}

//Stacks.java
package stacks;
public class Stacks
{
public static void main(String[] args)
{
 StackADT objStack = new StackADT(10);
 try
 {
     objStack.push(10);
     objStack.push(25);
     objStack.push(50);
     objStack.toString();

     //50 will be removed
     objStack.pop();
     objStack.pop();
     objStack.toString();  
     objStack.pop();
     objStack.toString();  
     objStack.pop();
     objStack.toString();  
     System.in.read();
 }
 catch(Exception exp)
 {
     System.out.println("" + exp.getMessage());
 }

}
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
C
I will post the code in C very soon. I am getting some issues in installing C in my laptop.

#include <stdio.h>
#include <stdlib.h>
int top = -1;
int stacksize = 10;
int stack[10];
void push(int);
int pop();
void isFull();
void isEmpty();
void printStack();
int main(int argc, char *argv[])
{    
    int exitCondition = -1;
    int data;
    do
    {
        printf("\nSelect an Operation \n");
        printf("1. Push\n");     
        printf("2. Pop\n");
        printf("3. Is Stack Empty\n");
        printf("4. is Stack Full\n"); 
        printf("5. Print Stack\n"); 
        printf("6. Exit\n");  
        scanf("%d",&exitCondition); 
         
        switch(exitCondition)
        {
             case 1:
                  printf("Enter a number to push into the stack \n");
                  scanf("%d", &data);
                  push(data);
                  printStack();
                  break;
             case 2:
                  data = pop(); 
                  printStack();
                  break;
             case 3: 
                  isEmpty();
                  break;
             case 4:                   
                  isFull(); 
                  break;
             case 5:
                  printStack();
                  break;
             case 6:
                  return 0;
             default:
                  printf("Please enter a valid option. \n");
        }
    }
    while(exitCondition != 6);
    
    system("PAUSE"); 
    return 0;
}
void push(int item)
{
    if(top == stacksize)
           printf("Stack Overflow");
    top = top + 1;
    stack[top] = item;
}
int pop()
{
    int item;
    if(top < 0 )
           printf("Stack Underflow");
    item = stack[top];
    top = top - 1 ;
    return item;
}
void isFull()
{
    if(top == stacksize)
         printf("Stack : Full"); 
}
void isEmpty()
{
    if(top < 0)
          printf("Stack : Empty"); 
}
void printStack()
{
    int i=0;    
    printf(" Stack : ");
    if(top < 0)
    {
        printf(" Empty ");
    }
    else
    {
        for( i= 0;i<=top;i++)
        {
             printf(" %d ",stack[i]);
        }
    }
    printf("\n");
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Stacks

Stack is data structure in which all the operations will be done on the top element. It is also called as LIFO(Last In, First Out) model, in which the element which is inserted last will be removed first. It's a kind of Linear Data Structure. At any point of time, Only top element is visible outside.

List of Operations allowed on a Stack
Create(S) - creates the stack S
Push(S, x) - for inserting elements in to Stack
Pop (S) - for deleting elements from stack
Top(S) - returns the top element of the stack
isEmpty(S) - used to check whether the stack is empty or not
isFull(S) - used to check whether the stack is full or not.

Note : isFull is a special method, used in array based implementations only.

We can implement Stack with Arrays as well as with Lists also. Before we look into Algorithms and implementation details, first we will see the advantages and disadvantages with Stacks.

+ Stacks are used to manage methods at run time (when a method is called, its parameters and local variables are pushed onto a stack; when the method returns, the values are popped from the stack).

+ Many parsing algorithms (used by compilers to determine whether a program is syntactically correct) involve the use of stacks.

+ stacks can be used to evaluate arithmetic expressions (e.g., by a simple calculator program)

+ Stacks also useful for some operations on graphs

+ Stacks are also used for reversing things. If you push something, say a String onto a Stack one character at a time, and then construct a String from the members popped off the Stack, then the String is reversed.

+ The advantage of an array implementation of stack is simplicity. The disadvantage is lack of expansion, i.e. the size of the stack is preset.

+ The advantage of a linked list implementation of stack is automatic expandability. The disadvantage is complexity, but the linked list is probably a better idea.

Now lets see how we can implement Stacks. As we know, there 2 ways of implementing Stacks. One is using Arrays and another one is using Lists. Both ways follows the same algorithm.

Stack Algorithms (These are my steps, what i have understood from the book)





These are 4 basic operations. Other operations are just for facilitating Stack to perform these operations. Just like CreateStack, DisplayStack etc.. methods. Whatever the implementation type the basic algorithms are same. We know that each algorithm will have Time Complexity. From the above algorithms, we can say that the time complexity of Stack is O(1).