�� The Stack
A stack is a pile of item kept one over another,i.e. A stack only have a head or top no bottom. Any item added becames the new op of the stack. And any item deleted or takenout from the stack is also taken out from the top & the top of Stack get reduced by one. That is the first item which goes in to the stack will come out of the stack the last as the last item. From this we conclude that a stack is a LIFO (last in first out) Stack is not the same as array. From the definition we found that stack provide provisions for addingof items and deleting of item from it, But it can be done from only with on end which is the top of the stack. A stack doesn�t have tail or the end point. When we add any item to stack the head of stack goes up. And when we delete any items from a stack the head(top) of the stack goes down.
Operation of Stack
From the above explanation we can fairly understand that stack can do only two work i.e. adding of item and deleting of item from it. We now points to the operation of stacks
1) Push : It is the operation by which we can add any item to a stack. This operation required the item to be added and a stack in which the item will be added.
2) Pop : It is the operation by which We can delete the upper item from the stack and this operation gives us the item that it is deleted from the stack. In other words this operation is used to take out the upper item from any stack.
3) IsEmpty : This operation is used to check whether the stack we are using is empty or filled by any item. If the stack is empty this operation gives us as appropriate answer.
<u>Code of Stack
Code of Stack in C.
Here we use a Structure to hold stack. The structure members are an integer called top to hold the stack top position and an integer array to hold the stack data. We only check the top variable if it is equal to zero than your stack is empty. If it is equal to the maximum value of stack member than the stack is full. Otherwise the top shows the currentposition or index of the top value in the stack array member. If we want to add any item to stack we increase the value of top by one and add any item to the stack array with the increased top as the index of the array. If we want to delete or want to Pop any item from the stack we decrease the top by one and return the current or top item of the stack array.
//codeing of Stack in C.
#include<stdio.h>
#include<conio.h>
#define max 5
/*Here we declare a Stack with the help of Structure where we
used an Array
to store the data in the array. The Top or Head of the stack is
denoted by
a integer data called top.
*/
struct stack
{
int top; //Data to hold top of stack
stackarray[max]; //Data to hold stack item
};
//This function is used to check wheter the stack is empty or not
int isempty(tmp)
struct stack tmp;
{
printf("%d",tmp.top);
if (tmp.top==0)
return 0;
else
return 1;
}
//This function is used to put an item in the stack.
void push(tmp,item)
struct stack *tmp; /*We have refrence the stack by pointer
the value of stack is chaced by the func*/
int item;
{
if(tmp->top==max)
printf("Data overflow\n");
else
{
tmp->top++;
tmp->stackarray[tmp->top]=item;
printf("The item is Push %d in %d\n",item,tmp->top);
}
}
//This is used to delete or take out an item from the stack.
void pop(tmp)
struct stack *tmp;
{
if(tmp->top==0)
printf("Data underflow\n");
else
{
printf("The Data Poped is
%d\n",tmp->stackarray[tmp->top--]);
}
}
void main()
{
int l;
struct stack stk={0};
if(isempty(stk))
printf("Stack is Empty\n");
else
printf("Stack is not empty\n");
for(l=1; l<=10;l++)
push(&stk,l);
for(l=1;l<=10;l++)
pop(&stk);
}
Code in C++
In C++ we used a class to denote a stack Data. We use a private member data as top (integer) and stackarray(as integer array). Here also the work of both the variables are same as that of in C Expained earlier. We also here defined memeber functions as Public for Push, Pop, IsEmpty. These member function are declared as Public so as to call them from outside the class. As we declared the member variables as Private so as to avoid the misused of data variables from outside the class. Only the member
functions can used the private data.
//Code in C++
#include<iostream.h>
#include<conio.h>
#define max 5
class stack
{
int top;
int stackarray[max];
public :
//Constructor
stack()
{
top=0;
}
//Push function used to put item in the stack.
void push(int item)
{
if(top==max)
cout<<"Data over flow\n";
else
{
stackarray[++top]=item;
cout<<"The item "<<item<<" is
pushed in "<<top<<"\n";
}
}
//pop function is used to delete or take out item from the stack.
void pop()
{
if(top==0)
cout<<"Data under flow\n";
else
{
cout<<"The item
"<<stackarray[top]<<" is poped from
"<<top--<<"\n";
}
}
//This function is used to check weather the stack is empty or
not.
int isempty()
{
if (top==0)
return 1;
else
return 0;
}
};
void main()
{
stack stk;
if(stk.isempty())
cout<<"The stack is empty\n";
for(int l=1;l<=10;l++)
stk.push(l);
for(l=1;l<=10;l++)
stk.pop();
}
*********************************************************************************
Source: http://library.thinkquest.org/C005618/text/stacks.htm
Stacks
A stack is a special type of list, where only the element at one end can be accessed. Items can be "pushed" onto one end of the stack structure. New items are inserted before the others, as each old element moves down one position. The first element is referred to as the "top" item, and is the only item that may be accessed at any time. In order to access items that are further down the stack, they must be moved to the top by "popping" the appropriate number of items. Popping refers to removing the top element of a stack. This is referred to as a LIFO structure, "Last In, First Out".
These rules make stacks very restricted in use, however they are very efficient and much easier to implement than lists. The uses of stacks vary from programming a simple card game, to maintaining the order of operations in a complex program. For example, a stack is useful in a management program where the newest tasks must be executed first. The node of a stack is usually presented with the following structure, which is very similar to that of a list node.
template <class ItemType>
struct StackNode
{
ItemType data;
StackNode<ItemType> *next;
};Implementing a generic stack class, which can be modified to work in any type of programming situation is very easy to do. A definition of such a class is shown below.
template <class ItemType>
class Stack
{
public:
Stack(); //class constructor - initialize private variables
~Stack(); //class destructor - free up used memory
void push(const ItemType); //add a new node to the top of the stack
ItemType pop(); //remove the top node and return its contents
ItemType top() const; //return the top node without popping it
void clear(); //delete all nodes in the stack
bool IsEmpty() const; //return true if the stack has no elements
bool IsFull() const; //return true if there is no free memory for new nodes
int count() const; //return the amount of nodes on the stack
private:
StackNode<ItemType> *top; //pointer to the top node in stack
int counter; //maintain the amount of nodes in the stack
};The class constructor sets counter to zero. Since there are no nodes in the stack when an instance of the class is first created, top is set to NULL.
template <class ItemType>
Stack<ItemType>::Stack()
{
counter = 0;
top = NULL;
}The role of the destructor is to delete all nodes in the list, and return the memory they occupy to free store. Since the clear() function does this task, it can be called by the destructor.
template <class ItemType>
Stack<ItemType>::~Stack()
{
clear();
}The push() function inserts a new node on top of the stack, and sets the top pointer to reference this new node. First, we check if there is enough system memory to create a new node, and then create the node, assigning it to
top. The node's value is set equal to item, and its next component is set to the node that was on top before the creation of the new node.template <class ItemType>
void Stack<ItemType>::push(const ItemType item)
{
assert(!IsFull()); //abort if there is not enough memory to create a new node
StackNode<ItemType> *tmp = new StackNode<ItemType>; //create a new node on top of the others with value item. set the original top node to follow the new one.
tmp->data = item; tmp->next = top; top = tmp; counter++; //increment the amount of nodes in the stack
}The pop() function removes the top node from the stack (freeing up the memory it uses) and returns its value.
top is set to the next node in the stack, and a temporary local variable(tmp) is created to point to the original top node. It is then used to reference the memory address of the node to delete. If we were to delete the node using top as a reference, the position of the next node in the stack would be lost, since top->next would no longer exist.template <class ItemType>
ItemType Stack<ItemType>::pop()
{
assert(!IsEmpty()); //abort if the stack is empty, no node to pop
ItemType item = top->data; //maintain top value, to be returned later
StackNode<ItemType> *tmp = top; //create a temporary reference to the top node
top = top->next; //set top to be the next node
delete tmp; //delete the top node
counter--; //decrement the amount of nodes in the stack
return item; //return the original top value
}The
top() function simple returns the value of the top node, without any modifications to the stack.template <class ItemType>
ItemType Stack<ItemType>::top() const
{
assert(!IsEmpty());
return top->data;
}The
clear() function delete all nodes in the stack, and frees the memory they occupy. Each node in the stack is visited using a loop, which executes until it reaches a NULL reference. A temporary variable is used for the same reason as in the list implementation. If we were to delete a node using top as a reference, the position of the next node in the list would be lost, since top->next would no longer exist.template <class ItemType>
void Stack<ItemType>::clear()
{
StackNode<ItemType> *tmp;
while(top != NULL) //loop through every node in the stack
{
tmp = top; //reference the top node
top = top->next; //set top to the next node
delete tmp; //delete the original top node
}
}The
IsEmpty() function returns true if the stack has no nodes. This task is accomplished very simply by checking to see if the top pointer is NULL.template <class ItemType>
bool Stack<ItemType>::IsEmpty() const
{
return (top == NULL);
}The
IsFull() function checks to see if there is enough system memory avaliable to create a new node for the stack. It works exactly the same way as it did in the linked list class. A node is "created" using the new command, which is then evaluated. If the new command had failed to set aside the necessary memory, its value is NULL, in which case the function returns true. If the new node is created successfully, it is deleted, and the function returns false.template <class ItemType>
bool Stack<ItemType>::IsFull() const
{
StackNode<ItemType> *tmp = new StackNode<ItemType>;
if(tmp == NULL)
return true;
else
{
delete tmp;
return false;
}
}The
count() function returns the amount of nodes in the stack, which is maintained by the class' private counter member. Again, this value can be maintained using a public member which the programmer can access directly, however it is good practice to hide this value from the programmer, since it can be modified without any nodes being added or removed. Also, if we were to change the class implementation, a program using the stack class would not require any change, since all the new code will be written in the count() function.template <class ItemType>
int Stack<ItemType>::count() const
{
return counter;
}
.png)
.png)
.png)
0 comments:
Post a Comment