Data Structure: Stack implementation in C++
The more detailed explanations can be found here.
(A) Top of stack varying method
Algorithm for top of stack varying method
1. Declare and initialize necessary variables, eg top = -1, MAXSIZE etc.
2. For push operation,
If top = MAXSIZE – 1
print ” stack overflow”
else
top = top + 1;
Read item from user
stack[top] = item
3. For next push operation, goto step 2.
4. For pop operation,
If top = -1
print “Stack underflow”
Else
item = stack[top]
top = top – 1
Display item
5. For next pop operation, goto step 4.
6. stop
2. For push operation,
If top = MAXSIZE – 1
print ” stack overflow”
else
top = top + 1;
Read item from user
stack[top] = item
3. For next push operation, goto step 2.
4. For pop operation,
If top = -1
print “Stack underflow”
Else
item = stack[top]
top = top – 1
Display item
5. For next pop operation, goto step 4.
6. stop
Source code for top of stack varying method
#include<iostream>
#include<cstdlib>
#define MAX_SIZE 10
using namespace std;
class Stack{
private:
int item[MAX_SIZE];
int top;
public:
Stack(){
top = -1;
}
void push(int data){
item[++top] = data;
}
int pop(){
return item[top--];
}
int size(){
return top+1;
}
bool is_empty(){
if(top==-1)
return true;
else
return false;
}
bool is_full(){
if(top==MAX_SIZE-1)
return true;
else
return false;
}
void display(){
for(int i=0; i<this->size(); i++){
cout<<item[i]<<" ";
}
cout<<endl;
}
};
int main(){
int choice;
int temp;
Stack stack;
while(true){
cout<<"Choose any one of the following"<<endl;
cout<<"1. Push Item. "<<endl;
cout<<"2. Pop Item."<<endl;
cout<<"3. Size of Stack."<<endl;
cout<<"4. Display all elements of stack."<<endl;
cout<<"5. Exit."<<endl;
cout<<"Your Choice: ";
cin>>choice;
switch(choice){
case 1:
if(!stack.is_full()){
cout<<"Enter number to push: ";
cin>>temp;
stack.push(temp);
}else{
cout<<"Can't push. Stack is Full!!"<<endl;
}
break;
case 2:
if(!stack.is_empty()){
cout<<"The number popped is: "<<stack.pop()<<endl;
}else{
cout<<"Cant't pop. Stack is Empty!!"<<endl;
}
break;
case 3:
cout<<"The size of the stack is: "<<stack.size()<<endl;
break;
case 4:
if(!stack.is_empty()){
cout<<"The elements in stack are: ";
stack.display();
cout<<endl;
}else{
cout<<"Stack is Empty"<<endl;
}
break;
case 5:
exit(0);
break;
}
}
return 0;
}
(B) Top Fixed method ( Base varying method)
Algorithm for top fixed method
1. Declare and initialize necessary variables e.g. BOS = 0, MAXSIZE etc.
2. For push operation,
If BOS = MAXSIZE
print “stack overflow”
Else
Insert new element by making vacant space at stack[0] location
/* for(i = BOS; i > 0; i–){
stack[i] = stack[i-1];
}
stack[0] = BOS
++BOS
*/
3. For next push operation goto step 2.
4. For pop operation
If BOS = 0
print”stack underflow”
else
extract item from stack[0]. Decrement BOS and refil empty space by lowering each step by 1.
5. For next pop operation, goto step 4.
6. Stop
2. For push operation,
If BOS = MAXSIZE
print “stack overflow”
Else
Insert new element by making vacant space at stack[0] location
/* for(i = BOS; i > 0; i–){
stack[i] = stack[i-1];
}
stack[0] = BOS
++BOS
*/
3. For next push operation goto step 2.
4. For pop operation
If BOS = 0
print”stack underflow”
else
extract item from stack[0]. Decrement BOS and refil empty space by lowering each step by 1.
5. For next pop operation, goto step 4.
6. Stop
Source code for top fixed method
#include<iostream>
#include<cstdlib>
#define MAX_SIZE 10
using namespace std;
class Stack{
private:
int item[MAX_SIZE];
int BOS;
public:
Stack(){
BOS = 0;
}
void push(int data){
for(int i=BOS; i>0; i--){
item[i] = item[i-1];
}
item[0] = data;
++BOS;
}
int pop(){
int temp = item[0];
for(int i = 0; i<BOS; i++){
item[i] = item[i+1];
}
BOS--;
return temp;
}
void display(){
for(int i = 0; i<BOS; i++){
cout<<item[i]<<" ";
}
cout<<endl;
}
bool isEmpty(){
if(BOS == 0){
return true;
}else{
return false;
}
}
bool isFull(){
if(BOS == MAX_SIZE){
return true;
}else{
return false;
}
}
};
int main(){
int choice, data;
Stack stack;
while(true){
cout<<"1. Push a Data"<<endl;
cout<<"2. Pop a Data"<<endl;
cout<<"3. Display All Element of Stack"<<endl;
cout<<"4. Quit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice){
case 1:
if(!stack.isFull()){
cout<<"Enter the data to push: ";
cin>>data;
stack.push(data);
cout<<endl;
}else{
cout<<"STACK IS FULL!!"<<endl;
}
break;
case 2:
if(!stack.isEmpty()){
cout<<"The data popped is "<<stack.pop()<<endl;
}else{
cout<<"THE STACK IS EMPTY"<<endl;
}
break;
case 3:
if(!stack.isEmpty()){
stack.display();
}else{
cout<<"STACK IS EMPTY"<<endl;
}
break;
case 4:
exit(0);
break;
}
}
return 0;
}
good job
Implementation in C++
Algorithm for PUSH Operation:
Step 1: If TOP >= SIZE – 1 then
Write “Stack is Overflow”
Step 2: TOP = TOP + 1
Step 3: STACK [TOP] = X
Algorithm for POP Operation:
Step 1: If TOP = -1 then
Write “Stack is Underflow”
Step 2: Return STACK [TOP]
Step 3: TOP = TOP – 1
If any error in this code segment
If(top<size) then
Top=top+1
Stack[top]=can
Else
Print "stack over flow"
End of if