Data structure , stack , queue

Data Structure , Stack , Queue And Linked List Presented By:Rajkiran R. Nadar (SYMCA16)

Data Structure:  Data Structures are structures programmed to store ordered data, so that various operations can be performed on it easily. It represents the knowledge of data to be organized in memory. It should be designed and implemented in such a way that it reduces the complexity and increases the efficiency.

Characteristics of a Data Structure  · Correctness − Data structure implementation should implement its interface correctly.  · Time Complexity − Running time or the execution time of operations of data structure must be as small as possible.  · Space Complexity − Memory usage of a data structure operation should be as little as possible.

Need for Data Structure  As applications are getting complex and data rich, there are three common problems that applications face now-a-days.  · Data Search − Consider an inventory of 1 million(106) items of a store. If the application is to search an item, it has to search an item in 1 million(106) items every time slowing down the search. As data grows, search will become slower.  · Processor Speed − Processor speed although being very high, falls limited if the data grows to billion records.  · Multiple Requests − As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data.

Stack  Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.

Stack Representation  A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it a fixed size stack implementation.

Basic Operations  Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations −  push() − Pushing (storing) an element on the stack.  pop() − Removing (accessing) an element from the stack.  To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks  isFull() − check if stack is full.  isEmpty() − check if stack is empty.

Algorithm for PUSH Operation  begin procedure push: stack, data if stack is full return null endif top ← top + 1 stack[top] ← data end procedure

Algorithm for Pop Operation begin procedure pop: stack if stack is empty return null endif data ← stack[top] top ← top – 1 return data end procedure

Example For Stack:  Stack Demo

Program Implementation Using C++: #include<iostream.h> class stack { int a[5],i; public: void init(); void push(int n); void pop(); void display(); };

void stack::init() { i=0; for(int j=0;j<5;j++) { a[j]=0; } } void stack::push(int n) { if(i<5) { a[i]=n; i++; } else { cout<<"Stack is Full"; } }

void stack::pop() { if(i!=-1) { a[i]=0; i--; } else { cout<<"Stack is Empty"; } } void stack::display() { for(int j=0;j<i;j++) { cout<<a[j]<<endl; } }

int main() { int n=0,no=0; stack s1; s1.init(); while(n!=4) { cout<<"1.Push"<<endl<<"2.Pop"<<endl<<"3.Display"<<endl<<"4.Exit"; cin>>n; switch(n) { case 1: cout<<"Enter Element To PUSH:"; cin>>no; s1.push(no); break; case 2: s1.pop(); break; case 3: s1.display(); break; case 4: goto a;

default: cout<<"Invalid Input"; break; } } a: return 0; }

Queue:  Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of existing element takes place from the other end called as FRONT(also called head). This makes queue as FIFO(First in First Out) data structure, which means that element inserted first will also be removed first.

Basic Operations  Queue operations may involve initializing or defining the queue, utilizing it, and then completely erasing it from the memory. Here we shall try to understand the basic  operations associated with queues −  · enqueue() − add (store) an item to the queue.  · dequeue() − remove (access) an item from the queue.  Few more functions are required to make the above-mentioned queue operation efficient.  These are −  · isfull() − Checks if the queue is full.  · isempty() − Checks if the queue is empty.

Algorithm for enqueue Operation procedure enqueue(data) if queue is full return overflow endif rear ← rear + 1 queue[rear] ← data return true end procedure

Algorithm for dequeue Operation procedure dequeue if queue is empty return underflow end if data = queue[front] front ← front + 1 return true end procedure

Program for Queue #include<iostream> #include<conio.h> #include<stdlib.h> using namespace std; class queue { int queue1[5]; int rear,front;

public: queue() { rear=-1; front=-1; } void insert(int x) { if(rear > 4) { cout <<"queue over flow"; front=rear=-1; return; } queue1[++rear]=x; cout <<"inserted" <<x; }

void delet() { if(front==rear) { cout <<"queue under flow"; return; } cout <<"deleted" <<queue1[++front]; } void display() { if(rear==front) { cout <<" queue empty"; return; } for(int i=front+1;i<=rear;i++) cout <<queue1[i]<<" "; } };

main() { int ch; queue qu; while(1) { cout <<"n1.insert 2.delet 3.display 4.exitnEnter ur choice"; cin >> ch; switch(ch) { case 1: cout <<"enter the element"; cin >> ch; qu.insert(ch); break; case 2: qu.delet(); break; case 3: qu.display();break; case 4: exit(0); } } return (0); }

Linked List:  A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.

Linked List Representation  Linked list can be visualized as a chain of nodes, where every node points to the next node.  As per the below illustration, following are the important points to be considered.  · Linked List contains a link element called first.  · Each link carries a data field(s) and a link field called next.  · Each link is linked with its next link using its next link.  · Last link carries a link as null to mark the end of the list.

Types of Linked List  Following are the various types of linked list.  · Simple Linked List − Item navigation is forward only.  · Doubly Linked List − Items can be navigated forward and backward.  · Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

Basic Operations  Following are the basic operations supported by a list.  · Insertion − Adds an element at the beginning of the list..  · Display − Displays the complete list.  · Search − Searches an element using the given key.  · Delete − Deletes an element using the given key.

Algorithm for Insertion Operation //insert link at the first location void insertFirst(int key, int data) { //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; //point it to old first node link->next = head; //point first to new first node head = link; }

Algorithm for Deletion Operation //delete first item struct node* deleteFirst() { //save reference to first link struct node *tempLink = head; //mark next to first link as first head = head->next; //return the deleted link return tempLink; }

Program for Linked List include <iostream> using namespace std; struct node { int data; node *next; };

class linked_list { private: node *head,*tail; public: linked_list() { head = NULL; tail = NULL; } void add_node(int n) { node *tmp = new node; tmp->data = n; tmp->next = NULL;

if(head == NULL) { head = tmp; tail = tmp; } else { tail->next = tmp; tail = tail->next; } } };

int main() { linked_list a; a.add_node(1); a.add_node(2); return 0; }

Data structure , stack , queue

More Related Content

What's hot

Similar to Data structure , stack , queue

Recently uploaded

In this document

Data structure , stack , queue