tag:blogger.com,1999:blog-3123335323395198102024-02-07T08:09:29.020+05:30My Data StructuresData Structures in my WordsDineshhttp://www.blogger.com/profile/00223829952726243429noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-312333532339519810.post-55586674443204199942011-05-10T11:37:00.013+05:302011-05-15T20:16:56.145+05:30List Implementation of Stacks(C#, Java, C++, C)<span style="font-size:85%;"><span style="font-family:verdana;">Here is my List implementation of stack(Sample Code). </span><br /><span style="font-family:verdana;">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span><br /></span><span style="font-weight: bold; font-family:verdana;font-size:85%;" >C#</span><span style="font-size:85%;"><br /><pre style=" background: white;font-family:Consolas;font-size:13;color:black;"><span style="color:green;">//StackADTList.cs</span><br /><span style="color:blue;">using</span> System;<br /><span style="color:blue;">using</span> System.Collections.Generic;<br /><br /><span style="color:blue;">namespace</span> StackUsingLists<br />{<br /><span style="color:blue;">public</span> <span style="color:blue;">class</span> <span style="color:#2b91af;">StackADTList</span><br />{<br /> <span style="color:blue;">int</span> _top = -1;<br /> <span style="color:#2b91af;">List</span><<span style="color:blue;">int</span>> listStack = <span style="color:blue;">null</span>;<br /><br /> <span style="color:green;">//We can implement automatically growable Stack as well normal size restricted stack also</span><br /> <span style="color:green;">//Here we will see limited and size restricted stack.</span><br /> <span style="color:blue;">public</span> StackADTList(<span style="color:blue;">int</span> nCapacity)<br /> {<br /> listStack = <span style="color:blue;">new</span> <span style="color:#2b91af;">List</span><<span style="color:blue;">int</span>>(nCapacity);<br /> _top = -1;<br /> }<br /><br /> <span style="color:blue;">public</span> <span style="color:blue;">int</span> Top<br /> {<br /> <span style="color:blue;">get</span>{ <span style="color:blue;">return</span> _top;}<br /> }<br /><br /> <span style="color:blue;">public</span> <span style="color:blue;">int</span> StackSize<br /> {<br /> <span style="color:blue;">get</span>{<span style="color:blue;">return</span> listStack.Capacity;}<br /> }<br /><br /> <span style="color:blue;">public</span> <span style="color:blue;">void</span> push(<span style="color:blue;">int</span> item)<br /> {<br /> <span style="color:blue;">if</span> ((_top + 1) == StackSize)<br /> <span style="color:blue;">throw</span> <span style="color:blue;">new</span> <span style="color:#2b91af;">Exception</span>(<span style="color:#a31515;">"Stack Overflow"</span>);<br /> _top = _top + 1;<br /> listStack.Add(item);<br /> }<br /><br /> <span style="color:blue;">public</span> <span style="color:blue;">int</span> pop()<br /> {<br /> <span style="color:blue;">if</span> (_top < 0)<br /> <span style="color:blue;">throw</span> <span style="color:blue;">new</span> <span style="color:#2b91af;">Exception</span>(<span style="color:#a31515;">"Stack Underflow"</span>);<br /> <span style="color:blue;">int</span> item = listStack[_top];<br /> listStack.RemoveAt(_top);<br /> _top = _top - 1;<br /> <span style="color:blue;">return</span> item;<br /> }<br /><br /> <span style="color:blue;">public</span> <span style="color:blue;">bool</span> isFull()<br /> {<br /> <span style="color:blue;">if</span> ((_top + 1) == StackSize)<br /> <span style="color:blue;">return</span> <span style="color:blue;">true</span>;<br /> <span style="color:blue;">else</span><br /> <span style="color:blue;">return</span> <span style="color:blue;">false</span>;<br /> }<br /><br /> <span style="color:blue;">public</span> <span style="color:blue;">bool</span> isEmpty()<br /> {<br /> <span style="color:blue;">if</span> (_top < 0)<br /> <span style="color:blue;">return</span> <span style="color:blue;">true</span>;<br /> <span style="color:blue;">else</span><br /> <span style="color:blue;">return</span> <span style="color:blue;">false</span>;<br /> }<br /><br /> <span style="color:blue;">public</span> <span style="color:blue;">override</span> <span style="color:blue;">string</span> ToString()<br /> {<br /> <span style="color:blue;">string</span> strItems = <span style="color:#a31515;">"Stack : "</span>;<br /> <span style="color:blue;">if</span> (isEmpty())<br /> {<br /> strItems += <span style="color:#a31515;">"empty"</span>;<br /> }<br /> <span style="color:blue;">else</span><br /> {<br /> <span style="color:blue;">foreach</span>(<span style="color:blue;">int</span> item <span style="color:blue;">in</span> listStack)<br /> {<br /> strItems += item + <span style="color:#a31515;">" "</span>;<br /> }<br /> }<br /> <span style="color:blue;">return</span> strItems;<br /> }<br />}<br />}</pre><br /><pre style=" background: white;font-family:Consolas;font-size:13;color:black;"><span style="color:green;">//Program.cs</span><br /><span style="color:blue;">using</span> System;<br /><span style="color:blue;">namespace</span> StackUsingLists<br />{<br /><span style="color:blue;">class</span> <span style="color:#2b91af;">Program</span><br />{ <br /><span style="color:blue;"> static</span> <span style="color:blue;">void</span> Main(<span style="color:blue;">string</span>[] args)<br /> { <br /><span style="color:blue;"> try</span><br /> {<br /> <span style="color:#2b91af;">StackADTList</span> objListStack = <span style="color:blue;">new</span> <span style="color:#2b91af;">StackADTList</span>(10);<br /><br /> objListStack.push(10);<br /> objListStack.push(25);<br /> objListStack.push(50);<br /> <span style="color:#2b91af;">Console</span>.WriteLine(<span style="color:#a31515;">" "</span> + objListStack.ToString());<br /> objListStack.pop();<br /> objListStack.pop();<br /> objListStack.pop();<br /> <span style="color:#2b91af;">Console</span>.WriteLine(<span style="color:#a31515;">" "</span> + objListStack.ToString());<br /> objListStack.pop();<br /> }<br /> <span style="color:blue;">catch</span> (<span style="color:#2b91af;">Exception</span> exp)<br /> {<br /> <span style="color:#2b91af;">Console</span>.WriteLine(<span style="color:#a31515;">"Error : "</span> + exp.Message);<br /> }<br /> <span style="color:#2b91af;">Console</span>.Read();<br /> }<br />}<br />}<br /></pre></span><span style="font-size:85%;"><span style="font-family:verdana;">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span><br /></span><span style="font-weight: bold;font-family:verdana;font-size:85%;" >Java<br /><br /></span><span style="font-family:verdana;font-size:78%;">Note: Sorry for formatting, i will try to update as it is looks like in my IDE</span><span style="font-weight: bold; font-family:verdana;font-size:85%;" ><br /><br /></span><span style="font-size:85%;">package stacksadtlist;<br />import java.util.LinkedList;<br />class StacksADT<br />{<br /> int _top;<br /> int _size;<br /> LinkedList<integer> objList = null; <br /> public StacksADT(int nSize)<br /> {<br /> _size = nSize;<br /> _top = -1;<br /> objList = new LinkedList<integer>(); <br /> } <br /> public int Size()<br /> {<br /> return objList.size();<br /> } <br /> public int TopIndex()<br /> {<br /> return _top;<br /> }<br /> public void push(int item) throws Exception<br /> {<br /> if((_top + 1) == _size)<br /> { <br /> throw new Exception("Stack Overlow");<br /> }<br /> _top = _top + 1;<br /> objList.add((Integer)item);<br /> }<br /> public int pop() throws Exception<br /> {<br /> if(_top < 0)<br /> {<br /> throw new Exception("Stack Underflow");<br /> }<br /> int tmpItem = objList.remove(_top);<br /> _top = _top - 1;<br /> return tmpItem;<br /> } <br /> public boolean isFull()<br /> {<br /> if((_top + 1) == Size())<br /> return true;<br /> else<br /> return false;<br /> } <br /> public boolean isEmpty()<br /> {<br /> if(_top < 0)<br /> return true;<br /> else<br /> return false;<br /> }<br /><br /> @ Override<br /> public String toString()<br /> {<br /> String strItems = "Stack : ";<br /> if (isEmpty())<br /> {<br /> strItems += "Empty";<br /> } else {<br /> for (int i = 0; i <= _top; i++) {<br /> strItems += objList.get(i) + " ";<br /> }<br /> }<br /> return strItems;<br /> }<br />}<br /><br />public class StacksADTList<br />{<br /> public static void main(String[] args)<br /> {<br /> try<br /> {<br /> StacksADT objStack =new StacksADT(10);<br /> objStack.push(10);<br /> objStack.push(25);<br /> objStack.push(50);<br /> System.out.println(objStack.toString());<br /> <br /> objStack.pop();<br /> objStack.pop();<br /> objStack.pop();<br /> System.out.println(objStack.toString());<br /> <br /> objStack.pop();<br /> <br /> }<br /> catch(Exception exp)<br /> {<br /> System.out.println("" + exp.getMessage());<br /> }<br /> try<br /> {<br /> System.in.read();<br /> }<br /> catch(Exception exp1)<br /> {<br /> //DOn't do anything<br /> }<br /> }<br />}<br /><br /><br /></integer></integer></span><span style="font-size:85%;"><span style="font-family:verdana;">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span><br /></span><span style="font-weight: bold; font-family:verdana;font-size:85%;" >C++</span><span style="font-size:85%;"><br /></span><br /><span style="font-size:85%;"> I will update very soon</span><br /><span style="font-size:85%;"><span style="font-family:verdana;">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span><br /></span><span style="font-weight: bold; font-family:verdana;font-size:85%;" >C</span> <pre><br />#include <stdio.h><br />#include <stdlib.h><br /><br />struct node<br />{<br /> int data;<br /> struct node *nextNode;<br />}*head, *current, *tmp;<br /><br />int top;<br />int stacksize = 10;<br />int data;<br /><br />void push(int);<br />int pop();<br />int isFull();<br />int isEmpty();<br />void printStack();<br /><br />int main(int argc, char *argv[])<br />{<br /> int exitCondition = -1;<br /> int data;<br /> top = -1;<br /> //initializing Head<br /> head = malloc(sizeof(struct node));<br /> if( head == NULL)<br /> {<br /> printf("Memory Error");<br /> return;<br /> }<br /> head->data = -999;<br /> head->nextNode = NULL;<br /> current = head;<br /> //Temporary node for traversing through the list<br /> tmp = malloc(sizeof(struct node));<br /> if( tmp == NULL)<br /> {<br /> printf("Memory Error");<br /> return;<br /> }<br /> tmp = head;<br /> <br /> //Stack Menu<br /> do<br /> {<br /> printf("\nSelect an Operation \n");<br /> printf("1. Push\n"); <br /> printf("2. Pop\n");<br /> printf("3. Is Stack Empty\n");<br /> printf("4. is Stack Full\n"); <br /> printf("5. Print Stack\n"); <br /> printf("6. Exit\n"); <br /> scanf("%d",&exitCondition); <br /> <br /> switch(exitCondition)<br /> {<br /> case 1:<br /> printf("Enter a number to push into the stack \n");<br /> scanf("%d", &data);<br /> push(data);<br /> printStack();<br /> break;<br /> case 2:<br /> data = pop(); <br /> if(data == head->data)<br /> {<br /> printf("Stack :Underflow"); <br /> }<br /> else<br /> {<br /> printf(" %d reomved from the stack\n", data); <br /> printStack();<br /> }<br /> break;<br /> case 3: <br /> data = isEmpty(); <br /> if(data == 1)<br /> {<br /> printf(" Stack : Empty\n", data);<br /> } <br /> break;<br /> case 4: <br /> data = isFull(); <br /> if(data == 1)<br /> {<br /> printf(" Stack : Full\n", data);<br /> } <br /> break;<br /> case 5:<br /> printStack();<br /> break;<br /> case 6:<br /> break;<br /> default:<br /> printf("Please enter a valid option. \n");<br /> system("EXIT");<br /> }<br /> }<br /> while(exitCondition != 6);<br /> system("PAUSE"); <br /> return 0;<br />}<br /><br />void push(int item)<br />{<br /> //Creating the new node in the list - start<br /> struct node *newNode;<br /> newNode = malloc(sizeof(struct node));<br /> if( newNode == NULL)<br /> {<br /> printf("Memory Error");<br /> return;<br /> }<br /> newNode->data = item; <br /> newNode->nextNode = NULL;<br /> //Creating the new node in the list - end<br /> <br /> if((top + 1) == stacksize)<br /> printf("Stack : Overflow \n");<br /> top = top + 1;<br /> if( current != NULL)<br /> {<br /> current->nextNode = newNode;<br /> current = newNode; <br /> } <br />}<br /><br />int pop()<br />{<br /> if(top < 0)<br /> {<br /> data = head->data; <br /> }<br /> else<br /> {<br /> top = top - 1;<br /> data = current->data;<br /> //here we need to do some extra coding for removing the lst node in the list<br /> tmp = head;<br /> while(tmp->nextNode != NULL)<br /> {<br /> if(tmp->nextNode == current)<br /> {<br /> current = tmp;<br /> current->nextNode = NULL;<br /> break;<br /> }<br /> tmp = tmp->nextNode;<br /> }<br /> tmp = head;<br /> }<br /> return data;<br />}<br />int isFull()<br />{<br /> if((top+1) == stacksize)<br /> return 1;<br /> else<br /> return 0;<br />}<br />int isEmpty()<br />{<br /> if(top < 0)<br /> return 1;<br /> else<br /> return 0;<br />}<br />void printStack()<br />{ <br /> printf("Stack :");<br /> if(top < 0 )<br /> {<br /> printf(" Empty"); <br /> }<br /> else<br /> { <br /> tmp = head; <br /> do<br /> {<br /> tmp = tmp->nextNode;<br /> if(tmp!=NULL)<br /> { <br /> printf ("%d ", tmp->data); <br /> } <br /> }<br /> while(tmp->nextNode != NULL);<br /> }<br /> printf("\n");<br />}<br /></pre><br /><span style="font-size:85%;"></span><span style="font-size:85%;"><span style="font-family:verdana;">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span></span><br /><span style="font-size:85%;"><br /><br /></span>Dineshhttp://www.blogger.com/profile/00223829952726243429noreply@blogger.com0tag:blogger.com,1999:blog-312333532339519810.post-74294330479874722372011-05-09T18:45:00.022+05:302011-05-15T20:05:31.718+05:30Array Implementation of Stacks(C#, Java, C++, C)<span style="font-size:85%;"><span style="font-family:verdana;">Here is my Array Implementation of stack(Sample Code)</span><br /><span style="font-family:verdana;">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span><br /></span><span style="font-weight: bold; font-family:verdana;font-size:85%;" >C#</span><span style="font-size:85%;"><br /></span><pre style="background: none repeat scroll 0% 0% white; font-family: verdana;font-family:Consolas;font-size:13;color:black;"><span style="font-weight: bold;font-size:85%;color:green;" >//StackADT.cs</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">using</span><span style="font-size:85%;"> System;<br /></span><span style="font-size:85%;color:blue;">namespace</span><span style="font-size:85%;"> Stacks<br />{<br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">class</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#2b91af;">StackADT</span><span style="font-size:85%;"><br />{<br /></span><span style="font-size:85%;color:green;">//Array for storing stack elements</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">private</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;">[] items = </span><span style="font-size:85%;color:blue;">null</span><span style="font-size:85%;">;<br /></span><span style="font-size:85%;color:green;">//Stack size</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">private</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> _size = 0;<br /></span><span style="font-size:85%;color:green;">//Top index</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">private</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> _top = -1;<br /></span><span style="font-size:85%;color:green;">//Read only property, because to stop modifying the size of the stack during the</span> <span style="font-size:85%;color:green;">operation</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> Size<br />{<br /></span><span style="font-size:85%;color:blue;">get</span><span style="font-size:85%;"> {</span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> _size;}<br />}<br /><br /></span><span style="font-size:85%;color:green;">//Standard Stack Operations - start </span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:green;">//Constructor - for creating and initializing the stack</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;"> StackADT(</span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> nSize)<br />{<br /></span><span style="font-size:85%;color:blue;">this</span><span style="font-size:85%;">._size = nSize;<br />items = </span><span style="font-size:85%;color:blue;">new</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;">[_size];<br />}<br /></span><span style="font-size:85%;color:green;">//Getting the index of top element</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> Top<br />{<br /></span><span style="font-size:85%;color:blue;">get</span><span style="font-size:85%;"> {</span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">this</span><span style="font-size:85%;">._top;}<br />}<br /></span><span style="font-size:85%;color:green;">//For inserting elements in to Stack</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">void</span><span style="font-size:85%;"> push(</span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> item)<br />{<br /></span><span style="font-size:85%;color:blue;">if</span><span style="font-size:85%;"> (_top == (_size - 1))<br /> </span><span style="font-size:85%;color:blue;">throw</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">new</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#2b91af;">Exception</span><span style="font-size:85%;">(</span><span style="font-size:85%;color:#a31515;">"Stack Overflow"</span><span style="font-size:85%;">);<br />items[++_top] = item;<br />}<br /></span><span style="font-size:85%;color:green;">//For deleting elements in to Stack</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> pop()<br />{<br /></span><span style="font-size:85%;color:blue;">if</span><span style="font-size:85%;"> (_top < 0)<br /> </span><span style="font-size:85%;color:blue;">throw</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">new</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#2b91af;">Exception</span><span style="font-size:85%;">(</span><span style="font-size:85%;color:#a31515;">"Stack Underflow"</span><span style="font-size:85%;">);<br /></span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> items[_top--];<br />}<br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">bool</span><span style="font-size:85%;"> isFull()<br />{<br /></span><span style="font-size:85%;color:blue;">if</span><span style="font-size:85%;"> (_top == (_size - 1))<br /> </span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">true</span><span style="font-size:85%;">;<br /></span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">false</span><span style="font-size:85%;">;<br />}<br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">bool</span><span style="font-size:85%;"> isEmpty()<br />{<br /></span><span style="font-size:85%;color:blue;">if</span><span style="font-size:85%;"> (_top < 0)<br /> </span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">true</span><span style="font-size:85%;">;<br /></span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">false</span><span style="font-size:85%;">;<br />}<br /></span><span style="font-size:85%;color:green;">//Stack Operations - end</span><span style="font-size:85%;"><br /><br /></span><span style="font-size:85%;color:green;">//Just for printing the Stack</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">override</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">string</span><span style="font-size:85%;"> ToString()<br />{<br /></span><span style="font-size:85%;color:#2b91af;">String</span><span style="font-size:85%;"> strItems = </span><span style="font-size:85%;color:#a31515;">""</span><span style="font-size:85%;">;<br /></span><span style="font-size:85%;color:blue;">if</span><span style="font-size:85%;"> (isEmpty())<br />{<br /> strItems = </span><span style="font-size:85%;color:#a31515;">"Stack Empty"</span><span style="font-size:85%;">;<br />}<br /></span><span style="font-size:85%;color:blue;">else</span><span style="font-size:85%;"><br />{<br /> </span><span style="font-size:85%;color:blue;">for</span><span style="font-size:85%;"> (</span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> i = 0; i <= _top; i++)<br /> {<br /> strItems += items[i] + </span><span style="font-size:85%;color:#a31515;">" "</span><span style="font-size:85%;">;<br /> }<br />}<br /></span><span style="font-size:85%;color:#2b91af;">Console</span><span style="font-size:85%;">.WriteLine(</span><span style="font-size:85%;color:#a31515;">""</span><span style="font-size:85%;"> + strItems);<br /></span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> strItems;<br />}<br />}<br />}<br /></span></pre><span style=" font-weight: bold;font-family:verdana;font-size:85%;color:green;" >//Program.cs</span><span style="font-size:85%;"><br /></span><pre style="background: none repeat scroll 0% 0% white; font-family: verdana;font-family:Consolas;font-size:13;color:black;"><span style="font-size:85%;color:blue;">using</span><span style="font-size:85%;"> System;<br /></span><span style="font-size:85%;color:blue;">namespace</span><span style="font-size:85%;"> Stacks<br />{<br /></span><span style="font-size:85%;color:blue;">class</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#2b91af;">Program</span><span style="font-size:85%;"><br />{<br /></span><span style="font-size:85%;color:blue;">static</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">void</span><span style="font-size:85%;"> Main(</span><span style="font-size:85%;color:blue;">string</span><span style="font-size:85%;">[] args)<br />{<br /></span><span style="font-size:85%;color:#2b91af;">StackADT</span><span style="font-size:85%;"> objStack = </span><span style="font-size:85%;color:blue;">new</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#2b91af;">StackADT</span><span style="font-size:85%;">(10);<br /></span><span style="font-size:85%;color:blue;">try</span><span style="font-size:85%;"><br />{<br /> objStack.push(10);<br /> objStack.push(25);<br /> objStack.push(50);<br /> objStack.ToString();<br /> objStack.pop();<br /> objStack.pop();<br /> objStack.ToString();<br /> objStack.pop();<br /> objStack.ToString();<br /> objStack.pop();<br /> objStack.Restring();<br />}<br /></span><span style="font-size:85%;color:blue;">catch</span><span style="font-size:85%;"> (</span><span style="font-size:85%;color:#2b91af;">Exception</span><span style="font-size:85%;"> exp)<br />{<br /> </span><span style="font-size:85%;color:#2b91af;">Console</span><span style="font-size:85%;">.WriteLine(</span><span style="font-size:85%;color:#a31515;">""</span><span style="font-size:85%;"> + exp.Message);<br />}<br /></span><span style="font-size:85%;color:#2b91af;">Console</span><span style="font-size:85%;">.ReadLine();<br />}<br />}<br />}</span><br /></pre><span style="font-size:85%;"><span style="font-family:verdana;"><br />++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span><br /><span style="font-weight: bold; font-family:verdana;font-size:85%;" >C++</span><span style="font-size:85%;"><br /></span><pre style="background: none repeat scroll 0% 0% white; font-family: verdana;font-family:Consolas;font-size:13;color:black;"><span style="font-weight: bold;font-size:85%;color:green;" >//StackADT.h</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">class</span><span style="font-size:85%;"> StackADT<br />{<br /></span><span style="font-size:85%;color:blue;"> int</span><span style="font-size:85%;"> _top;<br /></span><span style="font-size:85%;color:blue;"> int</span><span style="font-size:85%;"> _size;<br /></span><span style="font-size:85%;color:blue;"> int</span><span style="font-size:85%;">* Items;<br /></span><span style="font-size:85%;color:blue;">public</span><span style="font-size:85%;">:<br />StackADT(</span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;">);<br />~StackADT(</span><span style="font-size:85%;color:blue;">void</span><span style="font-size:85%;">);<br /></span><span style="font-size:85%;color:blue;"> void</span><span style="font-size:85%;"> push(</span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;">);<br /></span><span style="font-size:85%;color:blue;"> int</span><span style="font-size:85%;"> pop();<br /></span><span style="font-size:85%;color:blue;"> int</span><span style="font-size:85%;"> getTop();<br /></span><span style="font-size:85%;color:blue;"> bool</span><span style="font-size:85%;"> isFull();<br /></span><span style="font-size:85%;color:blue;"> bool</span><span style="font-size:85%;"> isEmpty();<br /></span><span style="font-size:85%;color:blue;"> void</span><span style="font-size:85%;"> DisplayStack();<br />};<br /></span></pre><span style="font-weight: bold;font-size:85%;color:blue;" ><span style="color:green;">//StackADT.cpp</span></span><br /><pre style="background: none repeat scroll 0% 0% white; font-family: verdana;font-family:Consolas;font-size:13;color:black;"><span style="font-size:85%;color:blue;">#include</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#a31515;">"StackADT.h"</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">#include</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#a31515;"><iostream></span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">#include</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#a31515;"><ios> </span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">using</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">namespace</span><span style="font-size:85%;"> std;<br />StackADT::~StackADT(</span><span style="font-size:85%;color:blue;">void</span><span style="font-size:85%;">)<br />{<br />}<br />StackADT::StackADT(</span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> nSize)<br />{<br />Items =</span><span style="font-size:85%;color:blue;">new</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;">[nSize];<br />_top = -1;<br />_size = nSize;<br />}<br /></span><span style="font-size:85%;color:blue;">void</span><span style="font-size:85%;"> StackADT::push(</span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> item)<br />{<br /></span><span style="font-size:85%;color:blue;"> if</span><span style="font-size:85%;">((_top + 1) == _size)<br />{<br />cout << </span><span style="font-size:85%;color:#a31515;">"Stack Overflow"</span><span style="font-size:85%;"> << endl;<br /></span><span style="font-size:85%;color:blue;"> return</span><span style="font-size:85%;">;<br />}<br />_top = _top + 1;<br />Items[_top] = item;<br />}<br /></span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> StackADT::pop()<br />{<br /></span><span style="font-size:85%;color:blue;"> if</span><span style="font-size:85%;"> (_top < 0)<br />{<br />cout << </span><span style="font-size:85%;color:#a31515;">"Stack Underflow"</span><span style="font-size:85%;"> << endl;<br /></span><span style="font-size:85%;color:blue;"> return</span><span style="font-size:85%;"> -1;<br />}<br /></span><span style="font-size:85%;color:blue;"> int</span><span style="font-size:85%;"> item = Items[_top];<br />_top = _top - 1;<br /></span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> item;<br />}<br /></span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> StackADT::getTop()<br />{<br /></span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> _top;<br />}<br /></span><span style="font-size:85%;color:blue;">bool</span><span style="font-size:85%;"> StackADT::isEmpty()<br />{<br /></span><span style="font-size:85%;color:blue;">if</span><span style="font-size:85%;"> (_top < 0)<br /></span><span style="font-size:85%;color:blue;"> return</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">true</span><span style="font-size:85%;">;<br /></span><span style="font-size:85%;color:blue;"> return</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">false</span><span style="font-size:85%;">;<br />}<br /></span><span style="font-size:85%;color:blue;">bool</span><span style="font-size:85%;"> StackADT::isFull()<br />{<br /></span><span style="font-size:85%;color:blue;"> if</span><span style="font-size:85%;"> (_top == _size)<br /></span><span style="font-size:85%;color:blue;"> return</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">true</span><span style="font-size:85%;">;<br /></span><span style="font-size:85%;color:blue;">return</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">false</span><span style="font-size:85%;">;<br />}<br /></span><span style="font-size:85%;color:blue;">void</span><span style="font-size:85%;"> StackADT::DisplayStack()<br />{<br /></span><span style="font-size:85%;color:blue;">if</span><span style="font-size:85%;">(isEmpty())<br />{<br />cout << </span><span style="font-size:85%;color:#a31515;">"Stack Empty"</span><span style="font-size:85%;"> << endl;<br />}<br /></span><span style="font-size:85%;color:blue;"> else</span><span style="font-size:85%;"><br />{<br /></span><span style="font-size:85%;color:blue;"> for</span><span style="font-size:85%;">(</span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> i=0;i<=_top;i++)<br />{<br />cout << Items[i] << </span><span style="font-size:85%;color:#a31515;">" "</span><span style="font-size:85%;">;<br />}<br />}<br />cout << endl;<br />}</span></pre><span style=" font-weight: bold;font-size:85%;color:green;" >//Stacks.cpp</span><br /><pre style="background: none repeat scroll 0% 0% white; font-family: verdana;font-family:Consolas;font-size:13;color:black;"><span style="font-size:85%;color:blue;">#include</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#a31515;"><iostream></span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">#include</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:#a31515;">"StackADT.h"</span><span style="font-size:85%;"><br /></span><span style="font-size:85%;color:blue;">using</span><span style="font-size:85%;"> </span><span style="font-size:85%;color:blue;">namespace</span><span style="font-size:85%;"> std;<br /><br /></span><span style="font-size:85%;color:blue;">int</span><span style="font-size:85%;"> main()<br />{<br />StackADT objStack(10);<br />objStack.push(10);<br />objStack.push(25);<br />objStack.push(50);<br />objStack.DisplayStack();<br />objStack.pop();<br />objStack.pop();<br />objStack.DisplayStack();<br />objStack.pop();<br />objStack.DisplayStack();<br />objStack.pop();<br />objStack.DisplayStack();<br /></span><span style="font-size:85%;color:blue;"> return</span><span style="font-size:85%;"> 0;<br />}</span></pre><span style="font-size:85%;"><span style="font-family:verdana;"><br />++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span><br /></span><span style="font-weight: bold; font-family:verdana;font-size:85%;" >Java</span><span style="font-size:85%;"><br /><pre><span style="font-size:100%;"><br /></span><span class="comment" style="font-size:100%;">//StackADT.java</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">package</span><span style="font-size:100%;"> stacks;<br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">class</span><span style="font-size:100%;"> StackADT<br />{<br /></span><span class="comment" style="font-size:100%;">//Array for storing stack elements</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">private</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;">[] items = </span><span class="keyword-directive" style="font-size:100%;">null</span><span style="font-size:100%;">;<br /></span><span class="comment" style="font-size:100%;">//Stack size</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">private</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;"> _size = 0;<br /></span><span class="comment" style="font-size:100%;">//Top index</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">private</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;"> _top = -1;<br /><br /></span><span class="comment" style="font-size:100%;">//Read only property, because to stop modifying the size of the stack during the</span><span style="font-size:100%;"><br /></span><span class="comment" style="font-size:100%;">//operation</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;"> getSize() {<br /> </span><span class="keyword-directive" style="font-size:100%;">return</span><span style="font-size:100%;"> _size;<br />}<br /></span><span class="comment" style="font-size:100%;">//Standard Stack Operations - start </span><span style="font-size:100%;"><br /><br /></span><span class="comment" style="font-size:100%;">//Constructor - for creating and initializing the stack</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> StackADT(</span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;"> nSize) {<br /> </span><span class="keyword-directive" style="font-size:100%;">this</span><span style="font-size:100%;">._size = nSize;<br /> items = </span><span class="keyword-directive" style="font-size:100%;">new</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;">[_size];<br />}<br /><br /></span><span class="comment" style="font-size:100%;">//Getting the index of top element</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;"> getTop() {<br /> </span><span class="keyword-directive" style="font-size:100%;">return</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">this</span><span style="font-size:100%;">._top;<br />}<br /><br /></span><span class="comment" style="font-size:100%;">//For inserting elements in to Stack</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">void</span><span style="font-size:100%;"> push(</span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;"> item) </span><span class="keyword-directive" style="font-size:100%;">throws</span><span style="font-size:100%;"> Exception {<br /> </span><span class="keyword-directive" style="font-size:100%;">if</span><span style="font-size:100%;"> (_top == (_size - 1)) {<br /> </span><span class="comment" style="font-size:100%;">//System.out.println("Stack Overflow");</span><span style="font-size:100%;"><br /> </span><span class="keyword-directive" style="font-size:100%;">throw</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">new</span><span style="font-size:100%;"> Exception(</span><span class="character" style="font-size:100%;">"</span><span class="character" style="font-size:100%;">Stack Overflow</span><span class="character" style="font-size:100%;">"</span><span style="font-size:100%;">);<br /> }<br /> items[++_top] = item;<br />}<br /><br /></span><span class="comment" style="font-size:100%;">//For deleting elements in to Stack</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;"> pop() </span><span class="keyword-directive" style="font-size:100%;">throws</span><span style="font-size:100%;"> Exception {<br /> </span><span class="keyword-directive" style="font-size:100%;">if</span><span style="font-size:100%;"> (_top < 0) {<br /> </span><span class="comment" style="font-size:100%;">//System.out.println("Stack Underflow");</span><span style="font-size:100%;"><br /> </span><span class="keyword-directive" style="font-size:100%;">throw</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">new</span><span style="font-size:100%;"> Exception(</span><span class="character" style="font-size:100%;">"</span><span class="character" style="font-size:100%;">Stack Underflow</span><span class="character" style="font-size:100%;">"</span><span style="font-size:100%;">);<br /> }<br /> </span><span class="keyword-directive" style="font-size:100%;">return</span><span style="font-size:100%;"> items[_top--];<br />}<br /><br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">boolean</span><span style="font-size:100%;"> isFull() {<br /> </span><span class="keyword-directive" style="font-size:100%;">if</span><span style="font-size:100%;"> (_top == _size) {<br /> </span><span class="keyword-directive" style="font-size:100%;">return</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">true</span><span style="font-size:100%;">;<br /> }<br /> </span><span class="keyword-directive" style="font-size:100%;">return</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">false</span><span style="font-size:100%;">;<br />}<br /><br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">boolean</span><span style="font-size:100%;"> isEmpty() {<br /> </span><span class="keyword-directive" style="font-size:100%;">if</span><span style="font-size:100%;"> (_top < 0) {<br /> </span><span class="keyword-directive" style="font-size:100%;">return</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">true</span><span style="font-size:100%;">;<br /> }<br /> </span><span class="keyword-directive" style="font-size:100%;">return</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">false</span><span style="font-size:100%;">;<br />}<br /></span><span class="comment" style="font-size:100%;">//Stack Operations - end</span><span style="font-size:100%;"><br /><br /></span><span class="comment" style="font-size:100%;">//Just for printing the Stack</span><span style="font-size:100%;"><br />@ Override<br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> String toString() {<br /> String strItems = </span><span class="character" style="font-size:100%;">""</span><span style="font-size:100%;">;<br /><br /> </span><span class="keyword-directive" style="font-size:100%;">if</span><span style="font-size:100%;"> (isEmpty()) {<br /> strItems = </span><span class="character" style="font-size:100%;">"</span><span class="character" style="font-size:100%;">Stack Empty</span><span class="character" style="font-size:100%;">"</span><span style="font-size:100%;">;<br /> } </span><span class="keyword-directive" style="font-size:100%;">else</span><span style="font-size:100%;"> {<br /> </span><span class="keyword-directive" style="font-size:100%;">for</span><span style="font-size:100%;"> (</span><span class="keyword-directive" style="font-size:100%;">int</span><span style="font-size:100%;"> i = 0; i <= _top; i++) {<br /> strItems += items[i] + </span><span class="character" style="font-size:100%;">"</span><span style="font-size:100%;"> </span><span class="character" style="font-size:100%;">"</span><span style="font-size:100%;">;<br /> }<br /> }<br /> System.out.println(</span><span class="character" style="font-size:100%;">""</span><span style="font-size:100%;"> + strItems);<br /> </span><span class="keyword-directive" style="font-size:100%;">return</span><span style="font-size:100%;"> strItems;<br />}<br />}<br /></span></pre><pre><span style="font-size:100%;"><br /></span><span class="comment" style="font-size:100%;">//Stacks.java</span><span style="font-size:100%;"><br /></span><span class="keyword-directive" style="font-size:100%;">package</span><span style="font-size:100%;"> stacks;<br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">class</span><span style="font-size:100%;"> Stacks<br />{<br /></span><span class="keyword-directive" style="font-size:100%;">public</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">static</span><span style="font-size:100%;"> </span><span class="keyword-directive" style="font-size:100%;">void</span><span style="font-size:100%;"> main(String[] args)<br />{<br /> StackADT objStack = </span><span class="keyword-directive" style="font-size:100%;">new</span><span style="font-size:100%;"> StackADT(10);<br /> </span><span class="keyword-directive" style="font-size:100%;">try</span><span style="font-size:100%;"><br /> {<br /> objStack.push(10);<br /> objStack.push(25);<br /> objStack.push(50);<br /> objStack.toString();<br /><br /> </span><span class="comment" style="font-size:100%;">//50 will be removed</span><span style="font-size:100%;"><br /> objStack.pop();<br /> objStack.pop();<br /> objStack.toString(); <br /> objStack.pop();<br /> objStack.toString(); <br /> objStack.pop();<br /> objStack.toString(); <br /> System.in.read();<br /> }<br /> </span><span class="keyword-directive" style="font-size:100%;">catch</span><span style="font-size:100%;">(Exception exp)<br /> {<br /> System.out.println(</span><span class="character" style="font-size:100%;">""</span><span style="font-size:100%;"> + exp.getMessage());<br /> }<br /><br />}<br />}</span><br /></pre>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span><br /><span style="font-family:verdana;">C</span><br /><span style="font-family:verdana;">I will post the code in C very soon. I am getting some issues in installing C in my laptop.</span><br /><pre><br />#include <stdio.h><br />#include <stdlib.h><br />int top = -1;<br />int stacksize = 10;<br />int stack[10];<br />void push(int);<br />int pop();<br />void isFull();<br />void isEmpty();<br />void printStack();<br />int main(int argc, char *argv[])<br />{ <br /> int exitCondition = -1;<br /> int data;<br /> do<br /> {<br /> printf("\nSelect an Operation \n");<br /> printf("1. Push\n"); <br /> printf("2. Pop\n");<br /> printf("3. Is Stack Empty\n");<br /> printf("4. is Stack Full\n"); <br /> printf("5. Print Stack\n"); <br /> printf("6. Exit\n"); <br /> scanf("%d",&exitCondition); <br /> <br /> switch(exitCondition)<br /> {<br /> case 1:<br /> printf("Enter a number to push into the stack \n");<br /> scanf("%d", &data);<br /> push(data);<br /> printStack();<br /> break;<br /> case 2:<br /> data = pop(); <br /> printStack();<br /> break;<br /> case 3: <br /> isEmpty();<br /> break;<br /> case 4: <br /> isFull(); <br /> break;<br /> case 5:<br /> printStack();<br /> break;<br /> case 6:<br /> return 0;<br /> default:<br /> printf("Please enter a valid option. \n");<br /> }<br /> }<br /> while(exitCondition != 6);<br /> <br /> system("PAUSE"); <br /> return 0;<br />}<br />void push(int item)<br />{<br /> if(top == stacksize)<br /> printf("Stack Overflow");<br /> top = top + 1;<br /> stack[top] = item;<br />}<br />int pop()<br />{<br /> int item;<br /> if(top < 0 )<br /> printf("Stack Underflow");<br /> item = stack[top];<br /> top = top - 1 ;<br /> return item;<br />}<br />void isFull()<br />{<br /> if(top == stacksize)<br /> printf("Stack : Full"); <br />}<br />void isEmpty()<br />{<br /> if(top < 0)<br /> printf("Stack : Empty"); <br />}<br />void printStack()<br />{<br /> int i=0; <br /> printf(" Stack : ");<br /> if(top < 0)<br /> {<br /> printf(" Empty ");<br /> }<br /> else<br /> {<br /> for( i= 0;i<=top;i++)<br /> {<br /> printf(" %d ",stack[i]);<br /> }<br /> }<br /> printf("\n");<br />}<br /></pre><br /><span style="font-family:verdana;">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span><br /></span>Dineshhttp://www.blogger.com/profile/00223829952726243429noreply@blogger.com0tag:blogger.com,1999:blog-312333532339519810.post-20714939753928975012011-05-07T23:34:00.047+05:302011-05-09T19:49:21.251+05:30Stacks<div style="text-align: justify;"><span style="font-size:85%;"><span style="font-weight: bold;"> Stack </span><span style="font-family:verdana;">is data structure in which all the operations will be done on the top element. It is also called as </span><span style="font-weight: bold;">LIFO</span><span style="font-family:verdana;">(</span><span style="font-weight: bold;">L</span><span style="font-family:verdana;">ast </span><span style="font-weight: bold;">I</span><span style="font-family:verdana;">n, </span><span style="font-weight: bold;">F</span><span style="font-family:verdana;">irst </span><span style="font-weight: bold;">O</span><span style="font-family:verdana;">ut) model, in which the element which is inserted last will be removed first. It's a kind of Linear Data Structure. </span><span style="font-family:verdana;">At any point of time, Only top element is visible outside.</span> </span><br /></div><br /><div style="text-align: justify;"><span style="font-size:85%;"><span style="font-family:verdana;">List of Operations allowed on a Stack</span></span><br /><span style="font-size:85%;"><span style="font-family:verdana;"> <strong>Create(S)</strong> - creates the stack S</span></span><br /><span style="font-size:85%;"><span style="font-family:verdana;"> <strong>Push(S, x) </strong>- for inserting elements in to Stack</span></span><br /><span style="font-size:85%;"><span style="font-family:verdana;"> <strong>Pop (S) </strong> - for deleting elements from stack</span></span><br /><span style="font-size:85%;"><span style="font-family:verdana;"> <strong>Top(S) </strong> - returns the top element of the stack</span></span><br /><span style="font-size:85%;"><span style="font-family:verdana;"> <strong>isEmpty(S)</strong> - used to check whether the stack is empty or not</span></span><br /><span style="font-size:85%;"><span style="font-family:verdana;"> <strong>isFull(S) </strong> - used to check whether the stack is full or not. </span></span><br /><br /><span style="font-size:85%;"><span style="font-family:verdana;"><span style="font-size:78%;"><span style="font-weight: bold;">Note :</span> isFull is a special method, used in array based implementations only.</span></span></span><br /></div><span style="font-size:85%;"><span style="font-family:verdana;"> </span></span><br /><br /><span style="font-size:85%;"> <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" style="font-family: verdana;" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg11JQH7NPxnTf4A3Nm0o2G9OtFoA2zcJQzpf_bOUiQ4KyRznGVTJRMId6UgWzbiS3ILgPCahcqXCL_ylQCkWlKoZ0bCLca9N3vqkxXCcVAJmAQJwZYaNV4jRSY5OYLvdRB1BfpqEigvy1H/s1600/Stacks.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 198px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg11JQH7NPxnTf4A3Nm0o2G9OtFoA2zcJQzpf_bOUiQ4KyRznGVTJRMId6UgWzbiS3ILgPCahcqXCL_ylQCkWlKoZ0bCLca9N3vqkxXCcVAJmAQJwZYaNV4jRSY5OYLvdRB1BfpqEigvy1H/s320/Stacks.jpg" alt="" id="BLOGGER_PHOTO_ID_5604039361240022754" border="0" /></a></span><br /><div style="text-align: justify;"><span style="font-size:85%;"><span style="font-family:verdana;">We can implement Stack with Arrays as well as with Lists also. Before we look into Algorithms and implementation details, first we will see the <span style="font-weight: bold;">advantages </span>and <span style="font-weight: bold;">disadvantages </span>with Stacks.</span></span><br /></div><br /><div style="text-align: justify;"><span style="font-size:85%;"><span style="font-family:verdana;"> + Stacks are used to manage methods at run time (when a method is called, its parameters and local variables are pushed onto a stack; when the method returns, the values are popped from the stack).</span></span><br /></div><br /><div style="text-align: justify;"><span style="font-size:85%;"><span style="font-family:verdana;"> + Many parsing algorithms (used by compilers to determine whether a program is syntactically correct) involve the use of stacks.</span></span><br /></div><br /><span style="font-size:85%;"><span style="font-family:verdana;">+ stacks can be used to evaluate arithmetic expressions (e.g., by a simple calculator program)</span></span><br /><br /><span style="font-size:85%;"><span style="font-family:verdana;"> + Stacks also useful for some operations on graphs</span></span><br /><br /><div style="text-align: justify;"><span style="font-size:85%;"><span style="font-family:verdana;"> + Stacks are also used for reversing things. If you push something, say a String onto a Stack one character at a time, and then construct a String from the members popped off the Stack, then the String is reversed.</span></span><br /></div><br /><div style="text-align: justify;"><span style="font-size:85%;"><span style="font-family:verdana;"> + The advantage of an array implementation of stack is simplicity. The disadvantage is lack of expansion, i.e. the size of the stack is preset.</span></span><br /></div><br /><div style="text-align: justify;"><span style="font-size:85%;"><span style="font-family:verdana;"> + The advantage of a linked list implementation of stack is automatic expandability. The disadvantage is complexity, but the linked list is probably a better idea.</span></span><br /></div><br /><div style="text-align: justify;"><span style="font-size:85%;"><span style="font-family:verdana;"> Now lets see how we can implement Stacks. As we know, there 2 ways of implementing Stacks. One is using Arrays and another one is using Lists. Both ways follows the same algorithm.</span></span><br /></div><br /><span style="font-size:85%;"><span style="font-family:verdana;"><strong>Stack Algorithms</strong> (These are my steps, what i have understood from the book)</span></span><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVpJsR-gw_g5Lt0aY3dz_uYCD8PJA58mbQg_V0VXxN62YeWamBQX0cdovwuihV_XBKMggPqp72VwWwSgFE2k7EnZmH700XRVjwcYlU5v75x_5KsQm0bMxy7a5JgHSrNxtI4q8vfFdQbmMr/s1600/Picture1.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 202px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVpJsR-gw_g5Lt0aY3dz_uYCD8PJA58mbQg_V0VXxN62YeWamBQX0cdovwuihV_XBKMggPqp72VwWwSgFE2k7EnZmH700XRVjwcYlU5v75x_5KsQm0bMxy7a5JgHSrNxtI4q8vfFdQbmMr/s320/Picture1.png" alt="" id="BLOGGER_PHOTO_ID_5604718470442556306" border="0" /></a><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtMCEvco8qDxaAzkEagJ9j7twGJzqnq5o59sCkTU99lW4ZAvkCzovm1CzV4uQlQsoRN7v9WrEaJJFJjtaKqoj2-rsjWqpdtDImz3SKdVZHY7D_xt3UcuwH_5WKdjxUQiH1lw2i6E13YtZp/s1600/Picture2.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 184px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtMCEvco8qDxaAzkEagJ9j7twGJzqnq5o59sCkTU99lW4ZAvkCzovm1CzV4uQlQsoRN7v9WrEaJJFJjtaKqoj2-rsjWqpdtDImz3SKdVZHY7D_xt3UcuwH_5WKdjxUQiH1lw2i6E13YtZp/s320/Picture2.png" alt="" id="BLOGGER_PHOTO_ID_5604720180660317746" border="0" /></a><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicCs3m91aSNaOHBBoqn2I0KIArS5QKVq8NYLJFKd5ittGbHFsUzdAP9nE-bs6J6Uf8f1B5MD1tjwlSFBOY5RxH62A3tiA_WfTHc-Bu9jTx5SV479QqaanWotnUefamju4usaHFB4Yg3jT9/s1600/Picture3.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 169px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicCs3m91aSNaOHBBoqn2I0KIArS5QKVq8NYLJFKd5ittGbHFsUzdAP9nE-bs6J6Uf8f1B5MD1tjwlSFBOY5RxH62A3tiA_WfTHc-Bu9jTx5SV479QqaanWotnUefamju4usaHFB4Yg3jT9/s320/Picture3.png" alt="" id="BLOGGER_PHOTO_ID_5604720186482507234" border="0" /></a><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi06uBBxrRtK5AdvhKNhTHZSQgoniDdBViy-irLuuuO8RRCNzefeZOCXm28PrIqC16L6lMSiOQBwaa8Y-GDiCcDFRjqcyme6aLVce3at_2l-AYqWQBm6DAF-_LeRVNc1fFqq6H8o7AgGTiJ/s1600/Picture4.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 169px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi06uBBxrRtK5AdvhKNhTHZSQgoniDdBViy-irLuuuO8RRCNzefeZOCXm28PrIqC16L6lMSiOQBwaa8Y-GDiCcDFRjqcyme6aLVce3at_2l-AYqWQBm6DAF-_LeRVNc1fFqq6H8o7AgGTiJ/s320/Picture4.png" alt="" id="BLOGGER_PHOTO_ID_5604720188068145874" border="0" /></a><span style="font-size:85%;"><span style="font-family:verdana;"><br />These are 4 basic operations. Other operations are just for facilitating Stack to perform these operations. Just like CreateStack, DisplayStack etc.. methods. Whatever the implementation type the basic algorithms </span></span><span style="font-size:85%;"><span style="font-family:verdana;">are same. We know that each algorithm will have Time Complexity. From the above algorithms, we can say that the </span></span><span style="font-size:85%;"><span style="font-family:verdana;"><b>time complexity of Stack is</b></span></span><span style="font-family:verdana;font-size:85%;"> <strong>O(1)</strong>.</span>Dineshhttp://www.blogger.com/profile/00223829952726243429noreply@blogger.com0tag:blogger.com,1999:blog-312333532339519810.post-70753832425424131262011-05-07T22:08:00.000+05:302011-05-07T22:35:02.014+05:30ADT (Abstract Data Types)<div style="text-align: justify;"><span style="font-family: verdana;font-size:85%;" >What is an abstract data type? An abstract data type (ADT) is a data type defined only in terms of the operations that may be performed on objects of the type. Users (programmers) are allowed to examine and manipulate objects using only these operations and they are unaware of how the objects are implemented in the programming language.</span><br /><br /><span style="font-family: verdana;font-size:85%;" >"<b style="font-weight: bold;">An Abstract Data Type</b><span style="font-weight: bold;"> (</span><b style="font-weight: bold;">ADT</b><span style="font-weight: bold;">) is a data structure and a collection of functions or procedures which operate on the data structure.</span> "</span><br /><span style="font-family: verdana;font-size:85%;" > </span><br /><span style="font-family: verdana;font-size:85%;" >Data Type vs Abstract Data Type :</span><br /><span style="font-family: verdana;font-size:85%;" >A <span style="font-weight: bold;">Data Type </span>is characterized by</span><br /><span style="font-family: verdana;font-size:85%;" > - a set of values</span><br /><span style="font-family: verdana;font-size:85%;" > - a data representation, which is common to all these values</span><br /><span style="font-family: verdana;font-size:85%;" > - a set of operations, which can be applied uniformly to all these values.</span><br /><br /><span style="font-family: verdana;font-size:85%;" >where as an <span style="font-weight: bold;">Abstract Data Type</span> is characterized by</span><br /><span style="font-family: verdana;font-size:85%;" > - a set of values</span><br /><span style="font-family: verdana;font-size:85%;" > - a set of operations, which can be applied uniformly to all these values</span><br /><span style="font-family: verdana;font-size:85%;" > - it won't give the external access to the data representation</span><br /><br /><span style="font-family: verdana;font-size:85%;" >Abstract Data Type (<span class="caps">ADT</span>) simplifies the task of specifying an algorithm by abstracting the details of it. So, the end user no need to worry, how it is implemented.</span><br /><br /><span style="font-family: verdana;font-size:85%;" >In simple Java or C# terms, It's just a <span style="font-weight: bold;">Class</span>.</span><br /><br /></div>Dineshhttp://www.blogger.com/profile/00223829952726243429noreply@blogger.com0tag:blogger.com,1999:blog-312333532339519810.post-50591825232303426332011-05-07T21:28:00.000+05:302011-05-07T22:36:28.185+05:30An introduction to Data Structures<p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;"><strong>Data Structure</strong> is one of the very popular buzz words we will be listening in the field of Computer Science. It is used every where, every program and almost every software system. Literally we can say, without a Data Structure we can't write a perfect and an efficient program.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;"><strong>What is a Data Structure?</strong></span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">There are so many definitions available, but i like this one "<strong>A data structure is a specialized format for organizing and storing data</strong>,<strong> so that it can be used efficiently</strong>". There are different types of data structures available.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">Data Structures can be classified in to two types</span></p><ol style="text-align: justify; font-family: verdana;"><li><span style="font-size:85%;">Primitive Data Structures</span></li><li><span style="font-size:85%;">Non Primitive Data Structures</span></li></ol><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">The Data Structures that can be operated directly are called as <strong>Primitive Data Structures</strong>. Also called as simple data types. Integer, Float, Character are some examples of Primitive Data Structures. These data structures supports very basic operations like creation, deletion, selection and updation.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">The data structures which are not primitive are called <strong>Non-Primitive Data Structures</strong> which means these are data structures that cannot be directly manipulated . For example, Complex number. It can't be expressed as a simple type. Because it will have both imaginary part and real part. Stacks, Queues, Linked lists, Trees are few more examples of non-primitive data structures.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">Again this non primitive data types can be divided in to two types</span></p><ol style="text-align: justify; font-family: verdana;"><li><span style="font-size:85%;">Linear Data Structures</span></li><li><span style="font-size:85%;">Non-Linear Data Structures</span></li></ol><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;"><strong>Linear Data Structures</strong> are those, in which sequential addition and updation is possible. In another way, Elements in the data structure will form a sequence or adjacent to each other or can be arranged in a straight line. In terms of memory allocation, Contiguous blocks of memory will be allocated. Stacks, Queues, Arrays, Lists are few examples of linear data structures.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;"><strong>Non-Linear Data Structures</strong> are those, if one element can be connected to more than two adjacent elements then it is known as non-linear data structure. It's exactly opposite to linear data structures. Trees and Graphs are the examples of Non-Linear data structures.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">See <a title="List of Data Structures" href="http://en.wikipedia.org/wiki/List_of_data_structures" target="_blank">here </a>for a full list of data structures and it's types.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">The major advantages of data structures are :</span></p><ul style="text-align: justify; font-family: verdana;"><li><span style="font-size:85%;">It gives different level of organizing data.</span></li><li><span style="font-size:85%;">It tells how data can be stored and accessed in its elementary level</span></li></ul><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">We have so many data structures giving different types of data organization. It's good. But how we can select a data structure that can fit into our requirements. Which factors affect the selection of a data structure? To answer these questions, first we should know when a program is said to be good? A program is said to be good,if it meets all our requirements, good speed and efficiency. How you will you achieve the speed and efficiency? To answer this question, first we should know, what is an algorithm? what is the relationship between a program, an algorithm and a Data Structure.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">In simple terms,</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;"><strong>Algorithm</strong> : Steps to solve a problem</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;"><strong>Program</strong> : Used to implement the algorithm</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;"><strong>Data Structure</strong> : Organization of data, so that the data can used efficiently by the program.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">If we want our program to be good and efficient, the underlying Algorithm and Data Structure should be efficient.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">The efficiency of an Algorithm and Data structure will be calculated in terms of <strong>Space(Memory) and time</strong>.This Time factor is also called as <strong>Time Complexity</strong> where as Space measure is called as <strong>Space Complexity</strong>. There are different types notations available to specify the efficiency of a Data Structure and an Algorithm. Those are Big-Oh notation, Small-Oh notation, Big-Omega notation, Small-Omega notation and Theta Notation.</span></p><p style="text-align: justify; font-family: verdana;"><span style="font-size:85%;">Why we need to know, all these details? Because, Each operation on a data structure will have these efficiency measures(Time Complexity and Space Complexity) which will decide the efficiency of the data structure. in turn it will help us in choosing the data structure for our program.</span></p>Dineshhttp://www.blogger.com/profile/00223829952726243429noreply@blogger.com0