FIFO using JAVA
import java.util.LinkedList; import java.util.Queue; public class QueueExample { public static void main(String[] args) { Queue<Integer> q = new LinkedList<>(); // Adds elements {0, 1, 2, 3, 4} to queue for (int i = 0; i < 5; i++) q.add(i); // Display contents of the queue. System.out.println("Elements of queue-" + q); // To remove the head of queue. // In this the oldest element '0' will be removed int removedele = q.remove(); System.out.println("removed element-" + removedele); System.out.println(q); // To view the head of queue int head = q.peek(); System.out.println("head of queue-" + head); // Rest all methods of collection interface, // Like size and contains can be used with this // implementation. int size = q.size(); System.out.println("Size of queue-" + size); } }
Rituparna Mazumder
Sorting a Queue without using Extra Space
#include <bits/stdc++.h> using namespace std; // Queue elements after sortedIndex are // already sorted. This function returns // index of minimum element from front to // sortedIndex int minIndex(queue<int> &q, int sortedIndex) { int min_index = -1; int min_val = INT_MAX; int n = q.size(); for (int i=0; i<n; i++) { int curr = q.front(); q.pop(); // This is dequeue() in C++ STL // we add the condition i <= sortedIndex // because we don't want to traverse // on the sorted part of the queue, // which is the right part. if (curr <= min_val && i <= sortedIndex) { min_index = i; min_val = curr; } q.push(curr); // This is enqueue() in // C++ STL } return min_index; } // Moves given minimum element to rear of // queue void insertMinToRear(queue<int> &q, int min_index) { int min_val; int n = q.size(); for (int i = 0; i < n; i++) { int curr = q.front(); q.pop(); if (i != min_index) q.push(curr); else min_val = curr; } q.push(min_val); } void sortQueue(queue<int> &q) { for (int i = 1; i <= q.size(); i++) { int min_index = minIndex(q, q.size() - i); insertMinToRear(q, min_index); } } // driver code int main() { queue<int> q; q.push(30); q.push(11); q.push(15); q.push(4); // Sort queue sortQueue(q); // Print sorted queue while (q.empty() == false) { cout << q.front() << " "; q.pop(); } cout << endl; return 0; }
Implement a stack using single Queue
#include<bits/stdc++.h> using namespace std; // User defined stack that uses a queue class Stack { queue<int>q; public: void push(int val); void pop(); int top(); bool empty(); }; // Push operation void Stack::push(int val) { // Get previous size of queue int s = q.size(); // Push current element q.push(val); // Pop (or Dequeue) all previous // elements and put them after current // element for (int i=0; i<s; i++) { // this will add front element into // rear of queue q.push(q.front()); // this will delete front element q.pop(); } } // Removes the top element void Stack::pop() { if (q.empty()) cout << "No elements\n"; else q.pop(); } // Returns top of stack int Stack::top() { return (q.empty())? -1 : q.front(); } // Returns true if Stack is empty else false bool Stack::empty() { return (q.empty()); } // Driver code int main() { Stack s; s.push(10); s.push(20); cout << s.top() << endl; s.pop(); s.push(30); s.pop(); cout << s.top() << endl; return 0; }
Double Ended Queue
# include<stdio.h> #include<process.h> #define MAX 30 typedef struct dequeue { int data[MAX]; int rear,front; }dequeue; void initialize(dequeue *p); int empty(dequeue *p); int full(dequeue *p); void enqueueR(dequeue *p,int x); void enqueueF(dequeue *p,int x); int dequeueF(dequeue *p); int dequeueR(dequeue *p); void print(dequeue *p); void main() { int i,x,op,n; dequeue q; initialize(&q); do { printf("\n1.Create\n2.Insert(rear)\n3.Insert(front)\n4.Delete(rear)\n5.Delete(front)"); printf("\n6.Print\n7.Exit\n\nEnter your choice:"); scanf("%d",&op); switch(op) { case 1: printf("\nEnter number of elements:"); scanf("%d",&n); initialize(&q); printf("\nEnter the data:"); for(i=0;i<n;i++) { scanf("%d",&x); if(full(&q)) { printf("\nQueue is full!!"); exit(0); } enqueueR(&q,x); } break; case 2: printf("\nEnter element to be inserted:"); scanf("%d",&x); if(full(&q)) { printf("\nQueue is full!!"); exit(0); } enqueueR(&q,x); break; case 3: printf("\nEnter the element to be inserted:"); scanf("%d",&x); if(full(&q)) { printf("\nQueue is full!!"); exit(0); } enqueueF(&q,x); break; case 4: if(empty(&q)) { printf("\nQueue is empty!!"); exit(0); } x=dequeueR(&q); printf("\nElement deleted is %d\n",x); break; case 5: if(empty(&q)) { printf("\nQueue is empty!!"); exit(0); } x=dequeueF(&q); printf("\nElement deleted is %d\n",x); break; case 6: print(&q); break; default: break; } }while(op!=7); } void initialize(dequeue *P) { P->rear=-1; P->front=-1; } int empty(dequeue *P) { if(P->rear==-1) return(1); return(0); } int full(dequeue *P) { if((P->rear+1)%MAX==P->front) return(1); return(0); } void enqueueR(dequeue *P,int x) { if(empty(P)) { P->rear=0; P->front=0; P->data[0]=x; } else { P->rear=(P->rear+1)%MAX; P->data[P->rear]=x; } } void enqueueF(dequeue *P,int x) { if(empty(P)) { P->rear=0; P->front=0; P->data[0]=x; } else { P->front=(P->front-1+MAX)%MAX; P->data[P->front]=x; } } int dequeueF(dequeue *P) { int x; x=P->data[P->front]; if(P->rear==P->front) //delete the last element initialize(P); else P->front=(P->front+1)%MAX; return(x); } int dequeueR(dequeue *P) { int x; x=P->data[P->rear]; if(P->rear==P->front) initialize(P); else P->rear=(P->rear-1+MAX)%MAX; return(x); } void print(dequeue *P) { if(empty(P)) { printf("\nQueue is empty!!"); exit(0); } int i; i=P->front; while(i!=P->rear) { printf("\n%d",P->data[i]); i=(i+1)%MAX; } printf("\n%d\n",P->data[P->rear]); }
Priority Queue using Linked List
#include <stdio.h> #include <stdlib.h> // Node typedef struct node { int data; // Lower values indicate higher priority int priority; struct node* next; } Node; // Function to Create A New Node Node* newNode(int d, int p) { Node* temp = (Node*)malloc(sizeof(Node)); temp->data = d; temp->priority = p; temp->next = NULL; return temp; } // Return the value at head int peek(Node** head) { return (*head)->data; } // Removes the element with the // highest priority form the list void pop(Node** head) { Node* temp = *head; (*head) = (*head)->next; free(temp); } // Function to push according to priority void push(Node** head, int d, int p) { Node* start = (*head); // Create new Node Node* temp = newNode(d, p); // Special Case: The head of list has lesser // priority than new node. So insert new // node before head node and change head node. if ((*head)->priority > p) { // Insert New Node before head temp->next = *head; (*head) = temp; } else { // Traverse the list and find a // position to insert new node while (start->next != NULL && start->next->priority < p) { start = start->next; } // Either at the ends of the list // or at required position temp->next = start->next; start->next = temp; } } // Function to check is list is empty int isEmpty(Node** head) { return (*head) == NULL; } // Driver code int main() { // Create a Priority Queue // 7->4->5->6 Node* pq = newNode(4, 1); push(&pq, 5, 2); push(&pq, 6, 3); push(&pq, 7, 0); while (!isEmpty(&pq)) { printf("%d ", peek(&pq)); pop(&pq); } return 0; }
BFS tree
#include<iostream> #include <list> using namespace std; // This class represents a directed graph using // adjacency list representation class Graph { int V; // No. of vertices // Pointer to an array containing adjacency // lists list<int> *adj; public: Graph(int V); // Constructor // function to add an edge to graph void addEdge(int v, int w); // prints BFS traversal from a given source s void BFS(int s); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void Graph::BFS(int s) { // Mark all the vertices as not visited bool *visited = new bool[V]; for(int i = 0; i < V; i++) visited[i] = false; // Create a queue for BFS list<int> queue; // Mark the current node as visited and enqueue it visited[s] = true; queue.push_back(s); // 'i' will be used to get all adjacent // vertices of a vertex list<int>::iterator i; while(!queue.empty()) { // Dequeue a vertex from queue and print it s = queue.front(); cout << s << " "; queue.pop_front(); // Get all adjacent vertices of the dequeued // vertex s. If a adjacent has not been visited, // then mark it visited and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } }