Stacks
¢ 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?)
//This program implements a stack using a linked list
#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;
}
#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 words in reverse order.
while (!allwords.empty()) {
cout << allwords.top() << endl;
allwords.pop();
// remove top element
}
return 0;
}
Member Functions
| back | Returns a reference to the last and most recently added element at the back of the stack. |
| empty | Tests if the stack is empty |
| front | Returns a reference to the first element at the 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 |