Knowledge in stacks and queues
data structures and algorithms
data structures and algorithms includes introduction,array,sorting,searching,linked lists,graphs and stacks and queues.
Prabhanshi Dhankar
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); } } } }
Rituparna Mazumder
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); } }
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; }
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; }
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; }
Data Structures and Algorithms (Stack and Queue)
DSA stack and queues
Ankita Bhardwaj
Priority Queue Code KIIT UNIVERSITY
This is a code to get priority queue running in C.
SIDDHANT KUMAR
Stacks and Queue
Stack and Queue
neelay choudhury
Object oriented programming through C++
These PDFs contain different types of questions given for us as assignments in object oriented programming through c++ .This questions are created by expert faculty in our college and all these questions are advanced level in c++.Writing the code for these type of questions will improve knowledge to students in c++.
Supraja Adusumalli
Probability and statistics
This document contains information about the standard results of statistics and probability.variables classification are also available.
Sourav Jha
QUEUE IN DATA STRUCTURE
you will gain how to store data in a queue.
Deepak kumar Sahoo