Разница между статической очередью и односвязным списком
Статическая очередь : очередь - это упорядоченный список элементов. Он всегда работает в режиме «первым пришел - первым обслужен» (FIFO). Все элементы вставляются СЗАДИ и удаляются с ПЕРЕДНЕЙ части очереди. В реализации статической очереди будет использоваться массив, поэтому все операции с очередью основаны на индексах, что ускоряет выполнение всех операций, кроме удаления, поскольку удаление требует смещения всех оставшихся элементов вперед на одну позицию.
Статическая очередь - это очередь фиксированного размера, реализованная с использованием массива.
Односвязный список : связанный список также является упорядоченным списком элементов. Вы можете добавить элемент в любом месте списка, изменить элемент в любом месте списка или удалить элемент из любой позиции в списке. Каждый узел в списке хранит содержимое и указатель или ссылку на следующий узел в списке. Чтобы сохранить один связанный список, необходимо сохранить только ссылку или указатель на первый узел в этом списке. Последний узел в единственном связанном списке ни на что не указывает (или на ноль).
Вот некоторые из основных различий между статической очередью и односвязным списком. Статическая очередь Односвязный список Очередь - это набор из одного или нескольких элементов, расположенных в памяти непрерывно. Связанный список - это набор из одного или нескольких элементов, расположенных в памяти несмежным образом. Статическая очередь всегда имеет фиксированный размер. Размер списка никогда не фиксируется. В Queue хранится только один и единственный тип информации, потому что статическая реализация Queue осуществляется через массив. В списке также хранится адрес следующего узла вместе с его содержимым. Статическая очередь основана на индексах. Односвязный список основан на справочнике. Вставку всегда можно выполнить на одном конце, называемом REAR, а удаление - на другом конце, называемом FRONT . Как вставку, так и удаление можно выполнить в любом месте списка. Очередь всегда основана на FIFO. Список может быть основан на FIFI или LIFO и т. Д. Очередь имеет два указателя FRONT и REAR. В то время как List имеет только один указатель, который в основном называется HEAD.
Ниже представлена реализация статической очереди :
Джава
// Java program to implement a queue using an arrayclass Queue { private static int front, rear, capacity; private static int queue[]; Queue( int c) { front = rear = 0 ; capacity = c; queue = new int [capacity]; } // function to insert an element // at the rear of the queue static void queueEnqueue( data) int { // check queue is full or not if (capacity == rear) { System.out.printf( "
Queue is full
" ); return ; } // insert element at the rear else { queue[rear] = data; rear++; } return ; } // function to delete an element // from the front of the queue static void queueDequeue() { // if queue is empty if (front == rear) { System.out.printf( "
Queue is empty
" ); return ; } // shift all the elements from index 2 till rear // to the right by one else { for ( int i = 0 ; i < rear - 1 ; i++) { queue[i] = queue[i + 1 ]; } // store 0 at rear indicating there's no element if (rear < capacity) queue[rear] = 0 ; // decrement rear rear--; } return ; } // print queue elements static void queueDisplay() { int i; if (front == rear) { System.out.printf( "
Queue is Empty
" ); return ; } // traverse front to rear and print elements for (i = front; i < rear; i++) { System.out.printf( " %d <-- " , queue[i]); } return ; } // print front of queue static void queueFront() { if (front == rear) { System.out.printf( "
Queue is Empty
" ); return ; } System.out.printf( "
Front Element is: %d" , queue[front]); return ; }}public class StaticQueueinjava { // Driver code public static void main(String[] args) { // Create a queue of capacity 4 Queue q = new Queue( 4 ); // print Queue elements q.queueDisplay(); // inserting elements in the queue q.queueEnqueue( 20 ); q.queueEnqueue( 30 ); q.queueEnqueue( 40 ); q.queueEnqueue( 50 ); // print Queue elements q.queueDisplay(); // insert element in the queue q.queueEnqueue( 60 ); // print Queue elements q.queueDisplay(); q.queueDequeue(); q.queueDequeue(); System.out.printf( "
after two node deletion
" ); // print Queue elements q.queueDisplay(); // print front of the queue q.queueFront(); }} |
C #
// C# program to implement a queue using an arrayusing System; public class Queue{ private static int front, rear, capacity; private static int []queue; public Queue( int c) { front = rear = 0; capacity = c; queue = new int [capacity]; } // function to insert an element // at the rear of the queue public void queueEnqueue( data) int { // check queue is full or not if (capacity == rear) { Console.Write( "
Queue is full
" ); return ; } // insert element at the rear else { queue[rear] = data; rear++; } return ; } // function to delete an element // from the front of the queue public void queueDequeue() { // if queue is empty if (front == rear) { Console.Write( "
Queue is empty
" ); return ; } // shift all the elements from index 2 till rear // to the right by one else { for ( int i = 0; i < rear - 1; i++) { queue[i] = queue[i + 1]; } // store 0 at rear indicating there's no element if (rear < capacity) queue[rear] = 0; // decrement rear rear--; } return ; } // print queue elements public void queueDisplay() { int i; if (front == rear) { Console.Write( "
Queue is Empty
" ); return ; } // traverse front to rear and print elements for (i = front; i < rear; i++) { Console.Write( " {0} <-- " , queue[i]); } return ; } // print front of queue public void queueFront() { if (front == rear) { Console.Write( "
Queue is Empty
" ); return ; } Console.Write( "
Front Element is: {0}" , queue[front]); return ; }}public class StaticQueueinjava{ // Driver code public static void Main(String[] args) { // Create a queue of capacity 4 Queue q = new Queue(4); // print Queue elements q.queueDisplay(); // inserting elements in the queue q.queueEnqueue(20); q.queueEnqueue(30); q.queueEnqueue(40); q.queueEnqueue(50); // print Queue elements q.queueDisplay(); // insert element in the queue q.queueEnqueue(60); // print Queue elements q.queueDisplay(); q.queueDequeue(); q.queueDequeue(); Console.Write( "
after two node deletion
" ); // print Queue elements q.queueDisplay(); // print front of the queue q.queueFront(); }}/* This code contributed by PrinciRaj1992 */ |
Очередь пуста 20 <- 30 <- 40 <- 50 <- Очередь заполнена 20 <- 30 <- 40 <- 50 <- после удаления двух узлов 40 <- 50 <- Передний элемент: 40
Ниже представлена реализация односвязного списка :
Джава
// Java program to implement singly linked listclass SinglyLList { class Node { // node variables data; int Node next; public Node( data) int { this .data = data; this .next = null ; } } // create reference variable of Node Node head; // function to insert a node // at the beginning of the list void InsertAtStart( data) int { // create a node Node new_node = new Node(data); new_node.next = head; head = new_node; } // function to insert node // at the end of the list void InsertAtLast( data) int { Node new_node = new Node(data); if (head == null ) { head = new_node; return ; } new_node.next = null ; Node last = head; while (last.next != null ) { last = last.next; } last.next = new_node; } // function to delete a node // at the beginning of the list void DeleteAtStart() { if (head == null ) { System.out.println( "List is empty" ); return ; } head = head.next; } // function to delete a node at // a given position in the list void DeleteAtPos( int pos) throws Exception { int position = 0 ; if (pos > Count() || pos < 0 ) { throw new Exception( "Incorrect position exception" ); } Node temp = head; while (position != pos - 1 ) { temp = temp.next; position++; } temp.next = temp.next.next; } // function to delete a node // from the end of the list void DeleteAtLast() { Node delete = head; while (delete.next != null && delete.next.next != null ) { delete = delete.next; } delete.next = null ; } // function to display all the nodes of the list void Display() { Node disp = head; while (disp != null ) { System.out.print(disp.data + "->" ); disp = disp.next; } } // function to return the total nodes in the list int Count() { int elements = 0 ; Node count = head; while (count != null ) { count = count.next; elements++; } return elements; }}public class GFG { // Driver code public static void main(String[] args) throws Exception { // create object of class singlyList SinglyLList list = new SinglyLList(); // insert elements of singly linked list // at beginning list.InsertAtStart( 3 ); list.InsertAtStart( 2 ); list.InsertAtStart( 1 ); // print linked list elements list.Display(); // insert element at the end of list list.InsertAtLast( 1 ); System.out.println( "
after inserting node at the end
" ); // print linked list elements list.Display(); // delete an element at the given position list.DeleteAtPos( 1 ); // delete starting element list.DeleteAtStart(); // delete last element list.DeleteAtLast(); System.out.println( "
after deleting node: second, first and last
" ); // print linked list elements list.Display(); }} |
C #
// C# program to implement singly linked listusing System;public class SinglyLList{ public class Node { // node variables public data; int public Node next; public Node( data) int { this .data = data; this .next = null ; } } // create reference variable of Node public Node head; // function to insert a node // at the beginning of the list public void InsertAtStart( data) int { // create a node Node new_node =
|