Data Structure: Stack implementation in C++
(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
Source code for top of stack varying method
#include
#include
#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; ithis->size(); i++){
cout ";
}
cout
}
};
int main(){
int choice;
int temp;
Stack stack;
while(true){
coutChoose any one of the following"
cout1. Push Item. "
cout2. Pop Item."
cout3. Size of Stack."
cout4. Display all elements of stack."
cout5. Exit."
coutYour Choice: ";
cin>>choice;
switch(choice){
case 1:
if(!stack.is_full()){
coutEnter number to push: ";
cin>>temp;
stack.push(temp);
}else{
coutCan't push. Stack is Full!!"
}
break;
case 2:
if(!stack.is_empty()){
coutThe number popped is: "
}else{
coutCant't pop. Stack is Empty!!"
}
break;
case 3:
coutThe size of the stack is: "
break;
case 4:
if(!stack.is_empty()){
coutThe elements in stack are: ";
stack.display();
cout
}else{
coutStack is Empty"
}
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
Source code for top fixed method
#include
#include
#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
item[i] = item[i+1];
}
BOS--;
return temp;
}
void display(){
for(int i = 0; i
cout ";
}
cout
}
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){
cout1. Push a Data"
cout2. Pop a Data"
cout3. Display All Element of Stack"
cout4. Quit"
coutEnter your choice: ";
cin>>choice;
switch(choice){
case 1:
if(!stack.isFull()){
coutEnter the data to push: ";
cin>>data;
stack.push(data);
cout
}else{
coutSTACK IS FULL!!"
}
break;
case 2:
if(!stack.isEmpty()){
coutThe data popped is "
}else{
coutTHE STACK IS EMPTY"
}
break;
case 3:
if(!stack.isEmpty()){
stack.display();
}else{
coutSTACK IS EMPTY"
}
break;
case 4:
exit(0);
break;
}
}
return 0;
}