Home » C++ Programing » Implementation of STACK using Arrays in C C++

Implementation of STACK using Arrays in C C++

implementation of stack data structure c/c++
Advertisements
Loading...

Implementation of Stack using Arrays in C C++

1. Stack using Arrays: Static allocation

Since all the elements of a stack are of the same type, so implementation of the stack using Arrays in C or C++ is very easy. 

The first element of the stack can be put in the first array slot, the second element of the stack in the second array slot, and so on. 

The top of the stack is the index of the last element added to the stack. In this implementation of a stack, stack elements are stored in an array.

And an array is a random access data structure that is, you can directly access any element of the array. 

However, by definition, a STACK is a data structure in which the elements are accessed (popped or pushed) at only one end i.e. a Last In First Out data structure.

 Thus, a stack element is accessed only through the top, not through the bottom or middle.

This feature of a stack is extremely important and must be understood well.

To keep track of the top position of the array, we can simply declare another variable, called Top of Stack.

But before the implementation of the stack using arrays in c/c++ just have a look first actually what a stack is.

implementation of stack data structure c/c++

What is a Stack?

The stack is a non-primitive linear data structure in which the addition of new data elements and deletion of already existing data elements is performed only from one end i.e, the top of the stack.

Stack uses the LIFO algorithm i.e, Last In First Out (LIFO) structure.
For beginners, it is a little bit confusing, but it is a very easy concept

Now take an example.
1. 10 plates placed on each other in a kitchen is a stack because when we add more plates we put them on the top. and when we take a plate from it we pick up the top plate first.

So it simply follows the LIFO (Last In First Out) data structure.

stack using arrays in c/c++ data structures.
Advertisements
Loading...

Push and Pop are the standard forms for the insertion and deletions of data elements in the stack.

1. Push is simply placing data on the top of the stack. Or when we add data to this list we call it to push into the stack.

2. Pop is simply deleting the elements but only from the top. It is called pop from the stack.

Since stack elements are only accessed from the top so we must update top in all the operations.

Whenever a stack is created, the stack base remains fixed, as new elements are added to the stack from the top.

Advertisements
Loading...

 

Full C/C++ Code of Stack using Arrays

//C++ program of stack using arrays #include<iostream> #include<stdio.h> #include<conio.h> #include<process.h> using namespace std; #define SIZE 5 //make a class & name it stk class stk { int stack[SIZE]; //stack using arrays int top; public: void push(); int pop(); void display(); stk() { top=-1; } }; void stk::push() //push function definition { int item; if(top==SIZE-1) { cout<<"Stack is Full\n"; return(0); } else{ cout<<"Enter element to push: \n"; cin>>item; top=top+1; stack[top]=item; } } int stk::pop() { int temp; if(top==-1) { cout<<"Empty Stack:\n"; return(0); } else { temp=stack[top]; top=top-1; }return(temp); } //travese and display void stk::display() { if(top==-1) cout<<"stack empty\n"; else { for(int i=top; i>=0; i--) { cout<<"Elements are:\t"; cout<<stack[i]; } }cout<<endl; } int main(){ int option=0; stk s; int element; while(1) { cout<<" ---------------------------------\n"; cout<<"enter 1 to push:\nenter 2 for pop:\n"; cout<<"enter 3 for display:\nenter 4 for exit\n"; cout<<" ---------------------------------\n"; cout<<"Enter option: \n"; cin>>option; switch(option){ case 1: s.push(); break; case 2: element=s.pop(); cout<<" ---- sucessful ----"; cout<<"popped element is= "<<element<<endl; break; case 3: s.display(); break; case 4: exit(0); default: cout<<"wrong choice\n"; break; } } getch(); return 0; }

Applications of Stacks | Implementation of stack

Stack is the most important data structure, which has a wide range of uses both in the user programs and system programs.

Suppose that you have a program with several functions.

To be specific, suppose that you have the functions A, B, C, and D in your program.

  1. Now suppose that function A calls function B, function B calls function C, and function C calls function D. 

When function D terminates, control goes back to function C;

when function C terminates, control goes back to function B; and when function B terminates, control goes back to function A. 

2. During program execution, how do you think the computer keeps track of the function calls? What about recursive functions? 

Recursion is the most and important result of the stack.

Since various problems are recursive in nature that must be solved recursively for better results and performances. 

Recursion works completely on the stack operations.

It’s pushes are the return values and variables into the stack and after all the recursive calls are called and calculated then it pops the results from the stack to summarize the final results and returns this back to the calling function. 

The computer uses stacks to implement function calls.

Stacks can also be used to convert recursive algorithms into non-recursive algorithms, especially recursive algorithms that are not tail recursive.

 Stacks have numerous other applications in computer science. 

  1. Postfix Expression, The stack is also very helpful in the evaluation of Postfix expressions. As expressions needs to be computed correctly so by using stack we change the general expressions into the Postfix expression.
  2. Stack Frames, Almost programs compiled from modern high level languages make use of a stack frame for the working memory or each procedure or function invocation.
  3. Reversing a String, Since stack operates from top to bottom, therefore reversing a string is quite easy by using stacks.

After developing the tools necessary to implement a stack, we will examine some applications of stacks.

A stack can be implemented in two ways static so size is fixed at compile-time and cannot be changed during run time.

Also in Dynamic, we do not set any size because the stack can grow during run time and shrink during run time.

1. Implementation of stack using arrays in C/C++ is Static.

2. Implementation of stack using Linked Lists in C/C++ is Dynamic.

Related Programs

  1. linked lists
  2. Doubly linked lists
  3. Queues
  4. Bisection method c++
  5. Gauss elimination method
  6. Regula Falsi method

Advertisements
Loading...

1 thought on “Implementation of STACK using Arrays in C C++”

Leave a Comment

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