Wednesday, August 27, 2014

Implementing a Stack using Array - Data Structures - C++ Program (Object Oriented)

Problem Question


To implement stack using array

Explanation of Problem


In this program we would be using the basic data structure array, to implement stack which is a widely used data structure. A stack is a LIFO (Last In First Out) data structure. This means the data that is entered in the stack latest, is the first to be taken out, just like a stack of plates. In the implementation of such a data structure, we need an important pointer, called Top of Stack that points to the Top of the stack. It is used to check the Stack Overflow (Stack Full) condition. The operation via which we insert a new element into the stack is called Push Operation. Taking the analogy of a stack of plates, when a new plate is inserted into the stack, the rest of the plates are “pushed” down, so the operation is called Push Operation. Just like that, when an element is removed, it is called Pop Operation.

Code


#include <iostream>
/**@Title: OOarray_Stack.cpp*
*@Programming Paradigm: Object Oriented*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 27-08-2014*
*/
class myArrayStack
{
private:
  int stackArray [ 1000 ];
  int topOfStack;

public:
  myArrayStack()
  {
    topOfStack = 0;
  }

  void pop()
  {
    if ( topOfStack <= 0 )
      std::cout << "\n\a\aStack Underflow!\n";
    else
      std::cout << std::endl << stackArray [ --topOfStack ] << " popped out of stack Successful\n";
  }

  void push(int element)
  {
    if ( topOfStack >= 1000 )
      std::cout << "\n\n\a\aStack Overflow!\n\n\a\a";
    else
    {
      stackArray [ topOfStack++ ] = element;
      std::cout << element << " pushed on stack successfully\n";
    }
  }

  void displayStack()
  {
    int i = 0;
    std::cout << std::endl << "Stack: ";
    if ( topOfStack <= 0 )
      std::cout << "\n\a\a!!!STACK EMPTY!!!\n";
    else
    {
      for ( i = 0; i < topOfStack - 1; i++ )
        std::cout << stackArray [ i ] << " ";
      std::cout << stackArray [ topOfStack - 1 ] << std::endl;
    }
  }
};

int main()
{
  myArrayStack myStack;
  int choice = 0, elementOfStack;
  std::cout << "\a\aWelcome to Stack v2.0\nMade by Rogue Coder\n\nThis Stack has a limit of 1000 elements.";
  do
  {
    std::cout << "\n\aMenu:\n1. Push\n2. Pop\n3. Display\n4. Exit\nYour Choice: ";
    std::cin >> choice;
    switch ( choice )
    {
    case 1:
      std::cout << "\nEnter the element you wish to push on stack: ";
      std::cin >> elementOfStack;
      myStack.push( elementOfStack );
      break;
    case 2:
      myStack.pop();
      break;
    case 3:
      myStack.displayStack();
      break;
    case 4:
      std::cout << "\n\n\a\aThank You for using Stack v2.0\nMade by Rogue Coder\nPress any key to exit.";
      std::cin.get();
      break;
    default:
      std::cout << "\n\n\a\a!!!Wrong Choice!!!\n\n";
      break;
    }
  }
  while ( choice != 4 );
  return 0;
}

Explanation of Code


#include <iostream> -> The compiler calls the Preprocessor to include the IOSTREAM(Standard Input / Output Streams Library) header file into the program, thus letting the use of the Standard Input / Output Streams functions like std::cin and std::cout. As per C++11 specification, including <iostream> automatically includes also <ios>, <streambuf>, <istream>, <ostream> and <iosfwd>.

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

std::cin (extern istream cin) -> Standard Input Stream, and object of class istream. It is generally used with the extraction operator (>>), though we can use member functions like get (cin.get()), read (cin.read()), etc. for the input. The use of extraction operator is much more popular due to the fact that it aids in getting formatted input.

std::cout (extern ostream cout) -> Standard Output Stream, and object of class ostream. It is generally used with the insertion operator (<<), though we can use member functions like write (cout.write()) for the output. The use of insertions operator is much more popular due to the fact that it aids in giving formatted output.

std::endl (ostream& endl (ostream& os)) -> This is a function which is used to insert a newline character and flush the stream. Because this function is a manipulator, it is designed to be used alone with no arguments in conjunction with the insertion (<<) operations on output streams.

int stackArray[1000], topOfStack represent the private variables in our class myArrayStack. choice = 0, elementOfStack are the basic variables that are used in the main function. stackArray is the array which we are going to transform into a Stack. The variable, choice, is used to store the user’s choice in our menu driven program. elementOfStack denotes the value that user wishes to push onto the stack. topOfStack is the variable that acts as the pointer to top of the stack.

myArrayStack()
{
topOfStack = 0;
}
-> This is the constructor that is used to initialise topOfStack pointer.

void pop()
{
if ( topOfStack <= 0 )
std::cout << "\n\a\aStack Underflow!\n";
else
std::cout << std::endl << stackArray [ --topOfStack ] << " popped out of stack Successful\n";
}
-> This is the first method of our program, in which the program first inspects for stack underflow. If the topOfStack is already pointing at the base of stack(0), then it means the stack is empty, hence nothing can be popped. Thus, “stack underflow” is displayed. Else, the element is removed from the stack, i.e, topOfStack is decremented. Actually, all the referencing in stack depends on topOfStack pointer. Thus, if there is an element that is out of bounds of it can never be referenced. This is how we pop the element.

void push(int element)
{
if ( topOfStack >= 1000 )
std::cout << "\n\n\a\aStack Overflow!\n\n\a\a";
else
{
stackArray [ topOfStack++ ] = element;
std::cout << element << " pushed on stack successfully\n";
}
}
-> This is the second method in our program. In this method we implement the Push Operation. As the control enters here, we check the pointer topOfStack. If it has already crossed the top(we have a 100 element storage in our stack, thus 0-99), user gets the message of Stack Overflow. Else, the method uses the user input which is passed as the argument to this method. The element is then pushed on stack and the topOfStack is incremented by one.


void displayStack()
{
int i = 0;
std::cout << std::endl << "Stack: ";
if ( topOfStack <= 0 )
std::cout << "\n\a\a!!!STACK EMPTY!!!\n";
else
{
for ( i = 0; i < topOfStack - 1; i++ )
std::cout << stackArray [ i ] << " ";
std::cout << stackArray [ topOfStack - 1 ] << std::endl;
}
}
-> The third method of our program where the stack is displayed to the user. This is just for information purpose, though no such operation on stacks exists. Stacks actually have only push/pop operations so that only the most recent information can be referenced. So here, we just check if the stack is empty and display the appropriate message to the user, else the for loop traverses the array and displays the stack to the user.

myArrayStack myStack;
myStack.push( elementOfStack );
myStack.pop();
myStack.displayStack();
-> The first statement creates an instance of the class myArrayStack. The rest of the statements call different methods of the class of which myStack is an instance of.

do{..}while() -> The program loop which encapsulates the whole program. Until the user chooses to exit the program, the control loops within this.

exit(0); -> This function is used to exit the program with an error code as it's argument. '0' implies normal exit. Other values are used for debugging purposes.

std::cin.get() -> This statement is used to pause our program, until user presses a key. This function is not necessary in your program, I use it to see my outputs at a paused screen. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)




Download Source Code



Saturday, August 09, 2014

Implementing a Stack using Array - Data Structures - C++ Program (Procedural)

Problem Question


To implement stack using array

Explanation of Problem


In this program we would be using the basic data structure array, to implement stack which is a widely used data structure. A stack is a LIFO (Last In First Out) data structure. This means the data that is entered in the stack latest, is the first to be taken out, just like a stack of plates. In the implementation of such a data structure, we need an important pointer, called Top of Stack that points to the Top of the stack. It is used to check the Stack Overflow (Stack Full) condition. The operation via which we insert a new element into the stack is called Push Operation. Taking the analogy of a stack of plates, when a new plate is inserted into the stack, the rest of the plates are “pushed” down, so the operation is called Push Operation. Just like that, when an element is removed, it is called Pop Operation.

Code


/**@Title: Array_Stack.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 09-08-2014*
*/
#include <iostream>

int main()
{
  int stackArray[100], choice = 0, elementOfStack, topOfStack = 0, i;
  std::cout << "\a\aWelcome to Stack v1.0\nMade by Rogue Coder\n\nThis Stack has a limit of 100 elements.";
  do
  {
    std::cout << "\n\aMenu:\n1. Push\n2. Pop\n3. Display\n4. Exit\nYour Choice: ";
    std::cin >> choice;
    switch ( choice )
    {
    case 1:
      if ( topOfStack >= 99 )
        std::cout << "\n\n\a\aStack Overflow!\n\n\a\a";
      else
      {
         std::cout << "\nEnter the element you wish to push on stack: ";
         std::cin >> elementOfStack;
        stackArray [ topOfStack++ ] = elementOfStack;
        std::cout << "PUSH Operation Successful\n";
      }
      break;
    case 2:
      if ( topOfStack <= 0 )
        std::cout << "\n\a\aStack Underflow!\n";
      else
        std::cout << std::endl << stackArray [ --topOfStack ] << " popped out of stack Successful\n";
      break;
    case 3:
      std::cout << std::endl << "Stack: ";
      if ( topOfStack <= 0 )
        std::cout << "\n\a\a!!!STACK EMPTY!!!";
      else
      {
        for ( i = 0; i < topOfStack - 1; i++ )
          std::cout << stackArray [ i ] << " ";
        std::cout << stackArray [ topOfStack - 1 ];
      }
      break;
    case 4:
      std::cout << "\n\n\a\aThank You for using Stack v1.0\nMade by Rogue Coder\nPress any key to exit.";
      std::cin.get();
      break;
    default:
      std::cout << "\n\n\a\a!!!Wrong Choice!!!\n\n";
      break;
    }
  }
  while ( choice != 4 );
  return 0;
}

Explanation of Code


#include <iostream> -> The compiler calls the Preprocessor to include the IOSTREAM(Standard Input / Output Streams Library) header file into the program, thus letting the use of the Standard Input / Output Streams functions like std::cin and std::cout. As per C++11 specification, including <iostream> automatically includes also <ios>, <streambuf>, <istream>, <ostream> and <iosfwd>.

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

std::cin (extern istream cin) -> Standard Input Stream, and object of class istream. It is generally used with the extraction operator (>>), though we can use member functions like get (cin.get()), read (cin.read()), etc. for the input. The use of extraction operator is much more popular due to the fact that it aids in getting formatted input.

std::cout (extern ostream cout) -> Standard Output Stream, and object of class ostream. It is generally used with the insertion operator (<<), though we can use member functions like write (cout.write()) for the output. The use of insertions operator is much more popular due to the fact that it aids in giving formatted output.

std::endl (ostream& endl (ostream& os)) -> This is a function which is used to insert a newline character and flush the stream. Because this function is a manipulator, it is designed to be used alone with no arguments in conjunction with the insertion (<<) operations on output streams.

int stackArray[100], choice = 0, elementOfStack, topOfStack = 0, i; -> These are the basic variables that form the backbone of our program. stackArray is the array which we are going to transform into a Stack. The variable, choice, is used to store the user’s choice in our menu driven program. elementOfStack denotes the value that user wishes to push onto the stack. topOfStack is the variable that acts as the pointer to top of the stack. The variable, i, is used as the loop counter.

if ( topOfStack > 99 )
std::cout << "\n\n\a\aStack Overflow!\n\n\a\a";
else
{
std::cout << "\nEnter the element you wish to push on stack: ";
std::cin >> elementOfStack;
stackArray [ topOfStack++ ] = elementOfStack;
std::cout << "PUSH Operation Successful\n";
}
-> This is the first case in our program. In this case we implement the Push Operation. As the control enters here, we check the pointer topOfStack. If it has already crossed the top(we have a 100 element storage in our stack, thus 0-99), user gets the message of Stack Overflow. Else, the program prompt for user input. The element is then pushed on stack and the topOfStack is incremented by one.

if ( topOfStack <= 0 )
std::cout << "\n\a\aStack Underflow!\n";
else
std::cout << std::endl << stackArray [ --topOfStack ] << " popped out of stack Successful\n";
-> This is the second case of our program, in which the program first inspects for stack underflow. If the topOfStack is already pointing at the base of stack(0), then it means the stack is empty, hence nothing can be popped. Thus, “stack underflow” is displayed. Else, the element is removed from the stack, i.e, topOfStack is decremented. Actually, all the referencing in stack depends on topOfStack pointer. Thus, if there is an element that is out of bounds of it can never be referenced. This is how we pop the element.

std::cout << std::endl << "Stack: ";
if ( topOfStack <= 0 )
std::cout << "\n\a\a!!!STACK EMPTY!!!";
else
{
for ( i = 0; i < topOfStack - 1; i++ )
std::cout << stackArray [ i ] << " ";
std::cout << stackArray [ topOfStack - 1 ];
}
-> The third case of our program where e stack is displayed to the user. This is just for information purpose, though no such operation on stacks exists. Stacks actually have only push/pop operations so that only the most recent information can be referenced. So here, we just check if the stack is empty and display the appropriate message to the user, else the for loop traverses the array and displays the stack to the user.

do{..}while() -> The program loop which encapsulates the whole program. Until the user chooses to exit the program, the control loops within this.

exit(0); -> This function is used to exit the program with an error code as it's argument. '0' implies normal exit. Other values are used for debugging purposes.

std::cin.get() -> This statement is used to pause our program, until user presses a key. This function is not necessary in your program, I use it to see my outputs at a paused screen. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)




Download Source Code