Stacks
Is a collection of items that exhibits the behavior that the last item in is the first item out Last-in-First-out (LIFO). Also, consist of a linear or sequence of all insertions and deletion is made at one end, called the top of the stack.
Stack Operation
push
The insertion (or addition) stacks operation. Pushing an element to a stack will add the new element at the top. After every push operation, the top is incremented by one. If the array is full and no new element can be accommodated, then the stack overflow condition occurs.
pop
The deletion (or remove) stacks operation. After every pop operation, the stack is decremented by one. If there is no element in the stack (empty stack) and the pop operation is performed then the stack underflow condition occurs.
top
Place where insertion and deletion takes place. Collection of data items can only be accessed in this location.
Please watch video for further discussion on STACKS
Stack Implementation using Standard Library Functions
Program 1
//stack array implementation
//libraries
#include <iostream>
#include <stack>
using namespace std;
int main()
{
int i,x;
stack<int> nums;
cout << "stack size"<<nums.size()<<endl;
nums.push(11);
nums.push(22);
nums.push(33);
cout << "stack size"<<nums.size()<<endl;
cout << "top " << nums.top()<<endl;
for (i=nums.size();i>0;i--)
{
x=nums.top();
cout << x <<endl;
nums.pop();
}
cout << "stack size"<<nums.size()<<endl;
return 0;
}
Program 2
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
stack<string> name;
string n;
char quest;
cout << "Enter data y/n? ";
cin >> quest;
while (quest=='Y' || quest=='y')
{
cout << "Enter name ";
cin >> n;
name.push(n);
cout << "enter again y/n? ";
cin >> quest;
}
cout << " size of stack " << name.size()<<endl;
while(!name.empty())
{
cout << name.top() << endl;
name.pop();
}
cout << " size of stack " << name.size()<<endl;
return 0;
}
Program 3
/*
* C++ Program to Implement Stack in Stl
*/
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
stack<int> st;
int choice, item;
while (1)
{
cout<<"\n---------------------"<<endl;
cout<<"Stack Implementation in Stl"<<endl;
cout<<"\n---------------------"<<endl;
cout<<"1.Insert "<<endl;
cout<<"2.Delete "<<endl;
cout<<"3.Size of the Stack"<<endl;
cout<<"4.Top Element"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter value to be inserted: ";
cin>>item;
st.push(item);
break;
case 2:
item = st.top();
st.pop();
cout<<"Element "<<item<<" Deleted"<<endl;
break;
case 3:
cout<<"Size of the Queue: ";
cout<<st.size()<<endl;
break;
case 4:
cout<<"Top Element of the Stack: ";
cout<<st.top()<<endl;
break;
case 5:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
Stack Implementation (User defined function)
Video Demonstration on STACK UDF
Program 4
//UDF of stack using array
//operations -> push, pop, traverse(display), empty()
#include <iostream>
#define STACK_SIZE 5
using namespace std;
int stackNum[STACK_SIZE];
int top=-1;
void push(int);
void display();
void pop();
void clear();
int main()
{
while(1)
{
int choice, num;
system ("cls");
cout << "STACK implementation using array\n";
cout << "[1] Push\n";
cout << "[2] Pop \n";
cout << "[3] Traverse\n";
cout << "[4] Clear\n";
cout << "[5] Exit\n";
cout << "Enter your choice ";
cin >> choice;
switch(choice)
{
case 1:
cout << "Enter number ";
cin >> num;
push(num);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
clear();
break;
case 5:
exit(1);
cin.ignore();
default:
cout <<"error";
break;
}
cin.ignore();
}
cin.ignore();
return 0;
}
void push(int n)
{
if (top==STACK_SIZE-1)
cout<< "stack is full \n";
else
stackNum[++top]=n;
}
void display()
{
if (top==-1)
cout << "stack is empty";
else
for (int i=top; i>=0;i--)
cout << stackNum[i] << endl;
}
void pop()
{
if (top==-1)
cout << "Stack is empty \n";
else
cout << "You pop the value "<<stackNum[top--];
}
void clear()
{
top=-1;
}
Program 5
//UDF of stack using array
//operations -> push, pop, traverse(display), isempty(), isfull
#include <iostream>
#define STACK_SIZE 5
using namespace std;
void display(int[]);
void push(int,int[]);
void pop(int[]);
void clear(int[]);
bool isfull(int[]);
bool isempty(int[]);
int main()
{
int stackNum[STACK_SIZE]={};
while(1)
{
int choice, num;
system ("cls");
cout << "STACK implem using array\n";
cout << "[1] Push\n";
cout << "[2] Pop \n";
cout << "[3] Traverse\n";
cout << "[4] Clear\n";
cout << "[5] Exit\n";
cout << "Enter your choice ";
cin >> choice;
switch(choice)
{
case 1:
if (!isfull(stackNum))
{
cout << "\nEnter n ";
cin >> num;
push(num,stackNum);
display(stackNum);
}
else
{
cout << "stack is full ";
}
break;
case 2:
if (!isempty(stackNum))
{
pop(stackNum);
display(stackNum);
}
else
{
cout << "stack is empty\n";
}
break;
case 3:
display(stackNum);
break;
case 4:
clear(stackNum);
display(stackNum);
break;
case 5:
exit(1);
cin.ignore();
default:
cout <<"error";
break;
}
cin.ignore();
}
cin.ignore();
return 0;
}
void push(int num, int n[])
{
for (int i=STACK_SIZE-1; i>0;i--)
{
n[i]=n[i-1];
}
n[0]=num;
cout << "you push the value " << num << " into the stack"<<endl;
}
void pop(int n[])
{
for (int i=0; i<STACK_SIZE-1;i++)
{
n[i]=n[i+1];
}
n[STACK_SIZE-1]=0;
}
void display(int n[])
{
for (int i =0; i<STACK_SIZE;i++)
{
cout << "[" << i << "]" << n[i] << endl;
}
}
bool isfull(int n[])
{
if (n[STACK_SIZE-1]==0)
return false;
return true;
}
bool isempty(int n[])
{
if (n[0]==0)
return true;
return false;
}
void clear(int n[])
{
for (int i=0; i<STACK_SIZE;i++)
n[i]=0;
}
Stack Implementation using Linked List
Program 6
//UDF of stack using linked list
//operations -> push, pop, traverse(display)
#include <iostream>
#include <iomanip>
using namespace std;
struct node{
int data;
node *next;
}*top;
void pop();
void push(int);
void display();
int main()
{
while(1)
{
int choice, num;
system ("clear");
cout << "STACK implem using linked list\n";
cout << "[1] Push\n";
cout << "[2] Pop \n";
cout << "[3] Traverse\n";
cout << "[4] Exit\n";
cout << "Enter your choice ";
cin >> choice;
switch(choice)
{
case 1:
cout << "Enter n: ";
cin >> num;
push(num);
display();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
cin.ignore();
default:
cout <<"error";
break;
}
cin.ignore().get();
}
cin.ignore().get();
return 0;
}
void push(int n)
{
node *p = new node;
p->data=n;
if (top==NULL)
p->next=NULL;
else
p->next=top;
top=p;
}
void pop()
{
if (top==NULL)
cout << "stack is empty\n";
else
{
node *tmp = top;
cout << "you poped the value " << top->data << endl;
top=top->next;
tmp->next=NULL;
delete(tmp);
}
}
void display()
{
node *p;
if (top==NULL)
cout << "Nothing to display\n";
else
{
cout << "Stack elements \n";
cout << setw(10) << "POINTER"
<< setw(20) << "VALUE"
<< setw(30) << "NEXT"
<< endl;
p=top;
while(p!=NULL)
{
cout << setw(10) << p
<< setw(20) << p->data
<< setw(30) << p->next
<< endl;
p=p->next;
}
}
}
STACK Implementation using OOP (Using Array)
Program 7
Filename: IntStack.h
class IntStack {
private:
int *stackArray;
int stackSize;
int top;
public:
IntStack(int size);
void push(int num);
void pop(int &num);
bool isFull();
bool isEmpty();
};
Filename: IntStack.cpp
Program 8
#include <iostream>
#include "IntStack.h"
using namespace std;
// Constructor
IntStack::IntStack(int size)
{
stackArray = new int[size];
stackSize = size;
top = -1;
}
//*************************************************
// Member function push pushes the argument onto
// the stack.
void IntStack::push(int num)
{
if (isFull())
{
cout << "The stack is full.\n";
}
else
{
top++;
stackArray[top] = num;
}
}
//****************************************************
// Member function pop pops the value at the top
// of the stack off, and copies it into the variable
// passed as an argument.
void IntStack::pop(int &num)
{
if (isEmpty())
{
cout << "The stack is empty. n";
}
else
{
num = stackArray[top];
top--;
}
}
//***************************************************
// Member function isFull returns true if the stack
// is full, or false otherwise.
bool IntStack::isFull()
{
bool status;
if (top == stackSize - 1)
status = true;
else
status = false;
return status;
}
//****************************************************
// Member function isEmpty returns true if the stack
// is empty, or false otherwise.
bool IntStack::isEmpty()
{
bool status;
if (top == -1)
status = true;
else
status = false;
return status;
}
int main()
{
IntStack stack(5);
int catchVar;
cout << "Pushing 5\n";
stack.push(5);
cout << "Pushing 10\n";
stack.push(10);
cout << "Pushing 15\n";
stack.push(15);
cout << "Pushing 20\n";
stack.push(20);
cout << "Pushing 25\n";
stack.push(25);
cout << "Popping..\n";
stack.pop(catchVar);
cout << catchVar << endl;
stack.pop(catchVar);
cout << catchVar << endl;
stack.pop(catchVar);
cout << catchVar << endl;
stack.pop(catchVar);
cout << catchVar << endl;
stack.pop(catchVar);
cout << catchVar << endl;
}
STACK Implementation using OOP (Using Linked list)
Program 9
Filename: DynIntStack.h
class DynIntStack
{
private:
struct StackNode
{
int value;
StackNode *next;
};
StackNode *top;
public:
DynIntStack()
{ top = NULL; }
void push(int num);
void pop(int &num);
bool isEmpty();
};
Program 10
Filename: DynIntStack.cpp
#include <iostream>
#include "DynIntStack.h"
using namespace std;
void DynIntStack::push(int num)
{
StackNode *newNode;
// Allocate a new node & store Num
newNode = new StackNode;
newNode -> value = num;
// If there are no nodes in the list
// make newNode the first node
if (isEmpty())
{
top = newNode;
newNode ->next = NULL;
}
else // Otherwise, insert NewNode before top
{ newNode ->next =top;
top = newNode;
}
}
//****************************************************
// Member function pop pops the value at the top
// of the stack off, and copies it into the variable
// passed as an argument.
void DynIntStack::pop(int &num)
{
StackNode *temp;
if (isEmpty())
{
cout << "The stack is empty.\n";
}
else // pop value off top of stack
{
num = top ->value;
temp = top ->next;
delete top;
top = temp;
}
}
//****************************************************
// Member function isEmpty returns true if the stack
// is empty, or false otherwise.
bool DynIntStack::isEmpty()
{
bool status;
if (!top)
status = true;
else
status = false;
return status;
}
int main()
{
DynIntStack stack;
int catchVar;
cout << "Pushing 5\n";
stack.push(5);
cout << "Pushing 10\n";
stack.push(10);
cout << "Pushing 15\n";
stack.push(15);
cout << "Popping...\n";
stack.pop(catchVar);
cout << catchVar << endl;
stack.pop(catchVar);
cout << catchVar << endl;
stack.pop(catchVar);
cout << catchVar << endl;
cout << "\nAttempting to pop again... ";
stack.pop(catchVar);
}