double ended queue c with examples
C ++의 Deque 또는 Double-ended Queue에 대한 심층 자습서. 튜토리얼은 Deque, 기본 작업, C ++ 및 Java 구현 및 응용 프로그램에 대해 설명합니다.
Double ended queue 또는 간단히“Deque”라고하는 것은 Queue의 일반화 된 버전입니다.
Queue와 Deque의 차이점은 FIFO (선입 선출) 방식을 따르지 않는다는 것입니다. Deque의 두 번째 기능은 전면 또는 후면 끝에서 요소를 삽입하고 제거 할 수 있다는 것입니다.
학습 내용 :
이중 종료 대기열 분류
Deque는 다음과 같이 분류 할 수 있습니다.
제한된 터치 입력; 입력 제한에서는 양쪽 끝에서 삭제가 가능하지만 삽입은 대기열의 뒷부분에서만 가능합니다.
출력 제한 Deque : 출력 제한 큐에서 삽입은 양쪽 끝에서 수행 할 수 있지만 삭제는 한쪽 끝, 즉 큐의 프런트 엔드에서만 수행됩니다.
deque를 사용하여 스택과 큐를 구현할 수도 있습니다.
기본 터치 조작
다음은 deque에서 수행 할 수있는 기본 작업입니다.
- 전면 삽입 : 데크 앞에 항목을 삽입하거나 추가합니다.
- insertLast : 데크 뒷면에 항목을 삽입하거나 추가합니다.
- deleteFront : 대기열 맨 앞에서 항목을 삭제하거나 제거합니다.
- 마지막 삭제 : 대기열 뒤쪽에서 항목을 삭제하거나 제거합니다.
- getFront : 데크의 앞 항목을 검색합니다.
- getLast : 대기열의 마지막 항목을 검색합니다.
- 비었다: deque가 비어 있는지 확인합니다.
- 가득: 데크가 가득 찼는 지 확인합니다.
및 일러스트레이션
빈 데크는 다음과 같이 표시됩니다.
ipad 용 POS 소프트웨어
다음으로 요소 1을 앞에 삽입합니다.
이제 후면에 요소 3을 삽입합니다.
다음으로 요소 5를 전면에 추가하고 전면 포인트를 4로 증가시킵니다.
그런 다음 요소 7을 후면에, 9를 전면에 삽입합니다. 데크는 아래와 같이 보일 것입니다.
다음으로 전면에서 요소를 제거하겠습니다.
따라서 요소가 전면에 삽입되면 전면 위치가 감소하고 요소가 제거되면 증가하는 것을 볼 수 있습니다. 후단의 경우 삽입시 위치가 증가하고 제거시 감소 .
및 구현
100 ++ 터치 구현
연결 목록뿐만 아니라 배열을 사용하여 C ++에서 deque를 구현할 수 있습니다. 이 외에도 표준 템플릿 라이브러리 (STL)에는이 데이터 구조에 대한 모든 기능을 구현하는 'deque'클래스가 있습니다.
deque의 배열 구현은 다음과 같습니다. 양단 대기열이기 때문에 구현을 위해 원형 배열을 사용했습니다.
#include using namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array(MAX_size); int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array(front) = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout << ' Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!!
' << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << ' Underflow!!
' << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!!
' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!!
' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end
'; dq.insertrear(1); cout << 'insert element 3 at rear end
'; dq.insertrear(3); cout << 'rear element of deque ' << ' ' << dq.getRear() << endl; dq.deleterear(); cout << 'After deleterear, rear = ' << dq.getRear() << endl; cout << 'inserting element 5 at front end
'; dq.insertfront(5); cout << 'front element of deque ' << ' ' << dq.getFront() << endl; dq.deletefront(); cout << 'After deletefront, front = ' << dq.getFront() << endl; return 0; } 산출:
후면 끝에 요소 1 삽입
Xbox One 용 최고의 vr 헤드셋
뒤쪽 끝에 요소 3 삽입
deque 3의 후면 요소
삭제 후 후방 = 1
전면 끝에 요소 5 삽입
deque 5의 전면 요소
deletefront 후, front = 1
자바 구현 재검토
Java의 deque 인터페이스 'java.util.Deque'는 'java.util.Queue'인터페이스에서 파생됩니다. Deque는 대기열 (선입 선출) 또는 스택 (후입 선출)으로 사용할 수 있습니다. 이러한 구현은 연결된 목록보다 빠르게 작동합니다.
다음은 Java의 Deque 인터페이스에 대한 계층 구조입니다.
Java의 Deque 인터페이스에 대한 몇 가지 사항을 기억해야합니다.
- 구현은 외부 동기화가 없기 때문에 스레드로부터 안전하지 않습니다.
- Deque는 여러 스레드에 의한 동시성을 지원하지 않습니다.
- 배열을 사용하여 구현 된 Deque는 NULL 요소의 사용을 허용하지 않습니다.
- 제한없는 용량과 크기 조정이 가능한 어레이 지원이 가장 중요한 두 가지 기능으로 요구 사항에 따라 어레이를 확장 할 수 있습니다.
다음은 Deque 인터페이스에서 지원하는 다양한 방법입니다.
네트워크에 방화벽을 설정하는 방법
| 하지 마라. | 방법 | 기술 |
|---|---|---|
| 7 | 반복자 () | deque에 대한 반복자를 반환합니다. |
| 1 | 추가 (요소) | 꼬리에 요소를 추가합니다. |
| 두 | addFirst (요소) | 머리 / 전면에 요소를 추가합니다. |
| 삼 | addLast (요소) | 꼬리 / 뒤에 요소를 추가합니다. |
| 4 | 제공 (요소) | 꼬리에 요소를 추가합니다. 삽입 성공 여부를 나타내는 부울 값을 반환합니다. |
| 5 | offerFirst (요소) | 머리에 요소를 추가합니다. 삽입 성공 여부를 나타내는 부울 값을 반환합니다. |
| 6 | offerLast (요소) | 꼬리에 요소를 추가합니다. 삽입 성공 여부를 나타내는 부울 값을 반환합니다. |
| 8 | 내림차순 반복자 () | 이 deque의 순서가 반대 인 반복기를 반환합니다. |
| 9 | push (요소) | 데크의 머리에 요소를 추가합니다. |
| 10 | pop (요소) | deque의 헤드에서 요소를 제거하고 반환합니다. |
| 열한 | removeFirst () | 데크 헤드의 요소를 제거합니다. |
| 12 | removeLast () | 데크의 꼬리에있는 요소를 제거합니다. |
| 13 | 투표() | deque의 첫 번째 요소를 검색하고 제거합니다 (deque의 헤드로 표시됨). deque가 비어 있으면 NULL을 반환합니다. |
| 14 | pollFirst () | 이 deque의 첫 번째 요소를 검색하고 제거합니다. 이 deque가 비어 있으면 null을 반환합니다. |
| 열 다섯 | pollLast () | 이 deque의 마지막 요소를 검색하고 제거합니다. 이 deque가 비어 있으면 null을 반환합니다. |
| 16 | 몰래 엿보다() | 이 deque가 나타내는 큐의 head (deque의 첫 번째 요소)를 검색합니다. 이 deque가 비어 있으면 null을 반환합니다. 참고 :이 작업은 요소를 제거하지 않습니다. |
| 17 | peekFirst () | 이 deque의 첫 번째 요소를 검색합니다. 이 deque가 비어 있으면 null을 반환합니다. 참고 :이 작업은 요소를 제거하지 않습니다. |
| 18 | peekLast () | 이 deque의 마지막 요소를 검색하거나이 deque가 비어있는 경우 null을 반환합니다. 참고 :이 작업은 요소를 제거하지 않습니다. |
다음 Java 구현은 위에서 설명한 다양한 작업을 보여줍니다.
import java.util.*; class Main { public static void main(String() args) { Deque deque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + '
'); // Iterate through the queue elements. System.out.println('Standard Iterator'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println('
Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println('
Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println('
Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } } 산출:
그리고 (11, 7, 3, 1, 5, 9, 13)
표준 반복자
11 7 3 1 5 9 13
역방향 반복자
13 9 5 1 3 7 11
11 엿보기
엿보기 후 : (11, 7, 3, 1, 5, 9, 13)
팝 11
팝 후 : (7, 3, 1, 5, 9, 13)
요소 3 포함? : true
첫 번째와 마지막 요소를 제거한 후 Deque : (3, 1, 5, 9)
위의 프로그램에서 우리는 Java의 Deque 인터페이스를 사용했고 정수 요소의 deque를 정의했습니다. 그런 다음이 deque에 대해 다양한 작업을 수행하고 이러한 작업의 결과가 표시됩니다.
응용
Deque는 다음 응용 프로그램 중 일부에서 사용할 수 있습니다.
# 1) 스케줄링 알고리즘 : 스케줄링 알고리즘 'A-steal 스케줄링 알고리즘'은 다중 프로세서 시스템의 다양한 프로세서에 대한 작업 스케줄링을 구현합니다. 이 구현은 deque를 사용하고 프로세서는 실행을 위해 deque에서 첫 번째 요소를 가져옵니다.
# 2) 활동 목록 실행 취소 : 소프트웨어 응용 프로그램에는 많은 작업이 있습니다. 하나는 '실행 취소'입니다. 실행 취소 작업을 여러 번 수행하면 이러한 모든 작업이 목록에 저장됩니다. 이 목록은 deque로 유지되므로 모든 끝에서 항목을 쉽게 추가 / 제거 할 수 있습니다.
#삼) 잠시 후 항목 제거 : 앱은 재고 항목을 나열하는 앱 등과 같이 목록의 항목을 새로 고칩니다. 이러한 앱은 얼마 후 항목을 제거하고 새 항목도 삽입합니다. 이것은 데크를 사용하여 수행됩니다.
결론
Deque는 큐의 양쪽 끝 (즉, 앞뒤)에서 요소를 추가 / 제거 할 수있게 해주는 양면 큐입니다. Deque는 배열 또는 연결 목록을 사용하여 구현할 수 있습니다. 그러나 Deque의 다양한 작업을 구현하는 STL (Standard Template Library) 클래스도 있습니다.
Java에는 Deque를 구현하기 위해 큐 인터페이스에서 상속 된 Deque 인터페이스가 있습니다. Deque의 기본 표준 작업 외에도이 인터페이스는 Deque에서 수행 할 수있는 다양한 다른 작업을 지원합니다.
Deque는 일반적으로 양쪽 끝에서 요소를 추가 / 제거해야하는 응용 프로그램에 사용됩니다. 또한 다중 프로세서 시스템의 프로세서 스케줄링에도 주로 사용됩니다.