OOP – ASSIGNMENT XV

Lab Manual Download: Write a program to implement stack or any other data structure in Java

ASSIGNMENT NO 15

Title: Demonstrate implementation of data structure in Java

Objectives: To learn implementation of data structure in Java.

Problem Statement:  Write a program to implement stack or any other data structure in Java.

Outcomes: Students will be able to learn and understand implementation of stack in Java.

Hardware requirements: Any CPU with Pentium Processor or similar, 256 MB RAM or more, 1 GB Hard Disk or more.

Software requirements:  64 bit Linux/Windows Operating System, JDK 1.4 or later

Theory:

In computer science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently. Data structures can implement one or more particular abstract data types (ADT), which specify the operations that can be performed on a data structure and the computational complexity of those operations. In comparison, a data structure is a concrete implementation of the specification provided by an ADT. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure. The efficiency of a data structure cannot be analyzed separately from those operations. Following abstract data types are available:

  1. Container
  2. List
  3. Associative array
  4. Multimap
  5. Set
  6. Bag
  7. Multiset
  8. Stack
  9. Queue
  10. Double-ended queue
  11. Priority queue
  12. Tree
  13. Graph

 Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). A stack is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle. Objects can be inserted at any time, but only the last (the most-recently inserted) object can be removed. Inserting an item is known as “pushing” onto the stack. “Popping” off the stack is synonymous with removing an item.

ass15_1

The Stack Abstract Data Type: A stack is an abstract data type (ADT) that supports two main methods: –

  • push(o): Inserts object o onto top of stack
    • Input: Object;
    • Output: none
  • pop(): Removes the top object of stack and returns it; if stack is empty an error occurs.
    • Input: none;
    • Output: Object

The following support methods should also be defined

  • peek(): Get the topmost object of stack
    • Input : none;
    • Output : Object;
  • size(): Returns the number of objects in stack
    • Input: none;
    • Output: integer
  • isEmpty(): Return a boolean indicating if stack is empty.
    • Input: none;
    • Output: boolean
  • top(): return the top object of the stack, without removing it; if the stack is empty an error occurs.
    • Input: none;
    • Output: Object

 A Stack Interface in Java:  While, the stack data structure is a “built-in” class of Java’s java.util package, it is possible, and sometimes preferable to define your own specific one. There are many real life examples of stack. Consider the simple example of plates stacked over one another in canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO/FILO order.

Implementation: There are two ways to implement a stack:

  • Using array
  • Using linked list

 An Array-Based Stack:

  • Create a stack using an array by specifying a maximum size N for our stack, e.g. N = 1,000.
  • The stack consists of an N-element array S and an integer variable t, the index of the top element in array S.
  • Array indices start at 0, so we initialize t to -1 • Pseudo-code Algorithm size(): return t +1 Algorithm isEmpty(): return (t
  • Algorithm push(o): if size() = N then throw a StackFullException t ← t + 1 S[t] ← o
  • Algorithm pop(): if isEmpty() then throw a StackEmptyException e←S[t] S[t]←null t←t-1 return e

 Conclusion: In this assignment, we have studied and demonstrated implementation of integer stack and its operations in Java.

Roll No. Name of Student Date of Performance Date of Assessment Grade Sign of Student Sign of Faculty
 

 

 

 

Program

 class StackDS {
    private int top;
    private int elements[];
    private int size;
    StackDS()
    {
        top=-1;
        elements =new int[1];
        size=1;
    }
    StackDS(int n)
    {
        top=-1;
        elements=new int[n];
        size=n;
    }
    void push(int num)
    {
        if(top==(size-1))
            System.out.println("Stack Full");
        else
        elements[++top]=num;
    }
    int pop()
    {
        if(top<0)
        {
            System.out.println("Stack Empty");
            return -1;
        }
        else
            return elements[top--];
    }
    int peek()
    {
        return elements[top];
    }
    void print()
    {
        System.out.println("Elements in stack are");
        for(int i=top;i>=0;i--)
            System.out.print(elements[i]+"\t");
            System.out.println();
    }
}
public class StackDemo
{
public static void main(String args[])
{
   System.out.println("Enter size of Stack");
   int size=Integer.parseInt(System.console().readLine());
   StackDS stack=new StackDS(size);
   do
   {
   System.out.println("\n\n*********MENU*************");
   System.out.println("1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\nEnter your choice:\n");
   int choice=Integer.parseInt(System.console().readLine());
   switch(choice)
   {
       case 1:
           System.out.println("Enter number to push on stack");
           int elm=Integer.parseInt(System.console().readLine());
           stack.push(elm);
           break;
        case 2:
           System.out.println("Popped Element is "+stack.pop());
           break;
        case 3:
           System.out.println("Top Element is "+stack.peek());
           break;
        case 4:
           stack.print();
           break;
        case 5:
            System.exit(0);
        default:
            System.out.println("Wrong choice");       
   }
   }while(true);
}
} 

OUTPUT:

ass-15-op1ass-15-op2ass-15-op3ass-15-op4ass-15-op5

Leave a Reply

Your email address will not be published. Required fields are marked *