Design & Implement Stack in C [without C STL] - JohnHau/mis GitHub Wiki

In this article, we have explained how to implement Stack Data Structure in C++ without using C++ STL. We have implemented using both C++ Class (OOP) and C++ Struct and demonstrated implementing Stack using 1D array and Linked List internally.

Table of contents:

Introduction to Stack data structure Implementation of stack using 1d-arrays (using Class) Implementation of Stack using linked list (using Struct) Let us get started to implement Stack in C++ without using C++ STL.

Introduction to Stack data structure The linear lists and linear arrays allows us to insert and delete elements at any place in the list – at the beginning, at the end or in the middle.

There are certain situations when we may want to restrict insertions and deletions so that they can take place only at the beginning or at the end of the list; not in the middle. One of the data structures that is useful in such situations is stack.

A stack is a linear data structure in which all the insertion and deletion operations are performed only at one end, called the top of the stack. It works on the principle of Last In First Out (LIFO). This means that the last item put on the stack is the first item that can be taken off.

There are many real-life examples of a stack. One such example is plates stacked over one another in the canteen. The plate which is at the top gets removed first, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time.

Implementation of stack using 1d-arrays (using Class) We will implement stack with the help of following functions:

Stack initialization. Push operation. Pop operation. Check for empty. Check for full. Display The code snippet for the implementation is as follows:

We start by defining the class STACK which defines the structure of the stack data type. This includes all the related functions and data members. The data members are num which is an array to store the stack elements, and top which is used to store the position of the topmost element of the array. The functions as used have been defined and explained below. The constructor STACK is used to initialize top to -1 to indicate that the stack is initially empty.

int main() { STACK stk; int choice, n, temp;

do
{
    cout<<endl;
    cout<<"0 - Exit."<<endl;
    cout<<"1 - Push Item."<<endl;
    cout<<"2 - Pop Item."<<endl;
    cout<<"3 - Display Items (Print STACK)."<<endl;
     
    cout<<"Enter your choice: ";
    cin>>choice;
     
    switch(choice)
    {
        case 0: break;
         
        case 1:
            cout<<"Enter item to insert: ";
            cin>>n;
            temp=stk.push(n);
            if(temp==-9999)
                cout<<"STACK OVERFLOW - STACK IMPLEMENTATION ERROR"<<endl;
            else
                cout<<temp<<" inserted."<<endl;
            break;
             
        case 2:
            temp=stk.pop();
            if(temp==-9999)
                cout<<"STACK UNDERFLOW - STACK ADT ERROR"<<endl;
            else
                cout<<temp<<" is removed (popped)."<<endl;
            break;
         
        case 3:
            stk.displayItems();
            break;
         
        default:
            cout<<"An Invalid choice."<<endl;
    }   
}while(choice!=0);

return 0; }

Implementation of Stack using linked list (using Struct) The advantage of implementation using linked lists is that there is no limit on the number of elements that can be pushed onto the stack.

We will implement stack with the help of following functions:

Push operation. Pop operation. Display The code snippet for the implementation is as follows:

We start by defining the structure Node which is used to create the linked list that is implemented as a stack. It contains the data item and a pointer variable to point to the next node.

int main() { int ch, val; cout<<"1) Push in stack"<<endl; cout<<"2) Pop from stack"<<endl; cout<<"3) Display stack"<<endl; cout<<"4) Exit"<<endl; do { cout<<"Enter choice: "<<endl; cin>>ch; switch(ch) { case 1: {
cout<<"Enter value to be pushed:"<<endl; cin>>val; push(val); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { cout<<"Exit"<<endl; break; } default: { cout<<"Invalid Choice"<<endl; } } }while(ch!=4); return 0; }
C++Copy Note: For all the standard stack operations (push, pop, IsEmpty, IsFull), the worst-case run-time complexity is O(1).

Applications of Stack: Some applications of stack are listed below:

Recursive function Function call Expression evaluation Expression conversion -Infix to prefix -Infix to postfix -Postfix to infix -Prefix to infix Towers of Hanoi Stack structures are also suitable for applications where information is required to be saved and later retrieved in a reverse order for further processing.

With this article at OpenGenus, you must have a strong idea of implementing Stack Data Structure in C++ Programming Language.