Introduction
¢ A stack is a last in first out (LIFO) type linear data structure.
¢ Items can only be inserted from the top and removed from the top
¢ Two of the more important stack operations involve pushing data onto a stack and popping
data off the stack.
Stack of Books
Push and Pop Operations
Contrasted with the Queue Data Structure
The Stack
¢ Its uses span the spectrum from reversing items to depth-first searches in artificial intelligence
applications to keeping track of function calls
¢ It can be implemented using either a linked list or a one-dimensional array.
¢ The following code implements a stack using a linked list
¢ Note that it currently only accepts integers. A more useful stack could be created by using a
templated class (remember templated functions?)
Code
//This program implements a stack using a linked list. Note that a stack can also be
implemented using an array
#include "stdafx.h"
#include<iostream>
using namespace std;
struct node
int data;
struct node *next;
};
class stack
private:
struct node *top;
public:
stack() // constructor
top=NULL;
void push(); // to insert an element
void pop(); // to delete an element
void show(); // to show the stack
};
// PUSH Operation
void stack::push()
int value;
struct node *ptr;
cout<<"\nPUSH Operation\n";
cout<<"Enter a number to insert: ";
cin>>value;
ptr=new node;
ptr->data=value;
ptr->next=NULL;
if(top!=NULL)
ptr->next=top;
top=ptr;
cout<<"\nNew item is inserted to the stack.";
// POP Operation
void stack::pop()
struct node *temp;
if(top==NULL)
cout<<"\nThe stack is empty!";
return;
temp=top;
top=top->next;
cout<<"\nPOP Operation........\nPoped value is "<<temp->data;
delete temp;
}
// Show stack
void stack::show()
struct node *ptr1=top;
cout<<"\nThe stack is: ";
while(ptr1!=NULL)
cout<<ptr1->data<<" ->";
ptr1=ptr1->next;
cout<<"NULL\n";
// Main function
int main()
stack s;
int choice;
while(1)
cout<<"\n-----------------------------------------------------------";
cout<<"\n\t\tSTACK USING LINKED LIST\n\n";
cout<<"1:PUSH, 2:POP, 3:DISPLAY STACK, 4:EXIT";
cout<<"\nEnter your choice(1-4): ";
cin>>choice;
switch(choice)
case 1:
s.push();
break;
case 2:
s.pop();
break;
case 3:
s.show();
break;
case 4:
exit(0);
break;
default:
cout<<"Please enter correct choice(1-4)!";
break;
return 0;
}
Using The Stack Class
#include "stdafx.h"
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
stack<string> allwords; // stack of all words
string word; // input buffer for words.
// read words/tokens from input stream
for (int i = 1; i<4; i++)
cout <<"Please ente a word"<<endl;
cin>>word;
allwords.push(word);
cout << "Number of words = " << allwords.size() << endl;
// write out all the numbers in reverse order.
while (!allwords.empty())
{
cout << allwords.top() << endl;
allwords.pop(); // remove top element
return 0;
Member Functions
Returns a reference to the last and most recently
back
added element at the back of the stack.
empty Tests if the stack is empty
Returns a reference to the first element at the
front
front of the queue
pop Removes an element from the front of the stack
push Adds an element to the back of the stack
size Returns the size of the stack
