OOP – ASSIGNMENT III

Lab Manual download: Write a program in C++ to implement Stack. Design the class for stack and the operations to be  performed on stack. Use Constructors and destructors. The objective of this assignment is to learn the concepts classes and objects, constructors and destructors.

ASSIGNMENT NO 3

 Title: Implementation of Stack in C++

Objectives: To learn and implement operations on Stack

Problem Statement:  Write a program in C++ to implement Stack. Design the class for stack and the operations to be  performed on stack. Use Constructors and destructors. The objective of this assignment is to learn the concepts classes and objects, constructors and destructors

Outcomes: Students will be able to demonstrate various operations on stack.

 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, g++ or TurboC compiler

 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.

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

 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 C++.

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

 

PROGRAM

#include<iostream.h>
#include<stdlib.h>
class Stack
{
    private:
        int top;
        int elements[30];
    public:
        Stack()
        {
            top=-1;
        }
        ~Stack()
        {
            top=-1;
        }
        void push(int i);
        int pop();
        int peek();
        void display();
};
void Stack::push(int i)
{
    if(top>=30)
    {
        cout<<"Stack is full";
    }
    else
    {
        top++;
        elements[top]=i;
    }
}
int Stack::pop()
{
    if(top<0)
    {
        cout<<"Stack is Empty";
        return 0;
    }
    else
    {
        int temp=elements[top];
        top--;
        return temp;
        //return elements[top--];
    }
}
int Stack::peek()
{
    return elements[top];
}
void Stack::display()
{
    if(top<0)
    {
        cout<<"Empty Stack";
        return;

    }
    else
    {
        cout<<"**************Elements in Stack************* \n:";
        int i;
        for(i=top;i>=0;i--)
            cout<<elements[i]<<"\t";
    }
}
int main()
{
int choice;
int elm;
Stack s;
do
{
cout<<"\n*************MENU************";
cout<<"\n1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit";
cout<<"\nEnter your choice:";
cin>>choice;
switch(choice)
{
    case 1:
        cout<<"\nEnter element you want to add";
        cin>>elm;
        s.push(elm);
    break;
    case 2:
        elm=s.pop();
        cout<<"\nPopped element is:\t"<<elm;
    break;
    case 3:
        elm=s.peek();
        cout<<"\nTop element is:\t"<<elm;
    break;
    case 4:
        s.display();
    break;
    case 5:
        ;
    break;
    default:
        cout<<"\nWrong choice";
}
}while(choice!=5);
}

OUTPUT:

Leave a Reply

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