Share deque c++

[nguyenphuongbach.lien]

#deque #C ++ #DatSource #LinkedList #STL ## deque trong C ++

Một deque (hàng đợi kết thúc kép) là một cấu trúc dữ liệu tuyến tính cho phép các phần tử được chèn và xóa ở cả hai đầu.Nó tương tự như hàng đợi, nhưng với khả năng thêm và loại bỏ các phần tử từ phía trước của deque.Deques thường được sử dụng trong các ứng dụng trong đó dữ liệu cần được thêm và xóa theo cách không phá hủy, chẳng hạn như trong một ứng dụng phát trực tuyến thời gian thực.

## Thực hiện Deque trong C ++

Cấu trúc dữ liệu Deque có thể được thực hiện trong C ++ bằng cách sử dụng danh sách được liên kết gấp đôi.Một danh sách được liên kết gấp đôi là một danh sách được liên kết trong đó mỗi nút có hai con trỏ, một đến nút tiếp theo và một cho nút trước đó.Điều này cho phép các yếu tố được chèn và xóa khỏi một trong hai đầu của danh sách trong thời gian không đổi.

Mã sau đây cho thấy việc triển khai đơn giản của một deque trong C ++:

`` `C ++
#include <Istream>
#include <Bart>

sử dụng không gian tên STD;

// Nút danh sách được liên kết gấp đôi
Nút cấu trúc {
dữ liệu int;
Nút* tiếp theo;
Nút* trước;
};

// một lớp deque
lớp deque {
công cộng:
// Người xây dựng
Deque () {
đầu = nullptr;
đuôi = nullptr;
}

// Destructor
~ Deque () {
while (head! = nullptr) {
Nút* temp = đầu;
đầu = đầu-> tiếp theo;
xóa temp;
}
}

// Chèn một phần tử ở phía trước của deque
void push_front (int data) {
Nút* new_node = new node ();
new_node-> data = data;
new_node-> next = head;
new_node-> prev = nullptr;

if (head! = nullptr) {
đầu-> prev = new_node;
}

đầu = new_node;

if (đuôi == nullptr) {
đuôi = new_node;
}
}

// Chèn một phần tử ở phía sau của deque
void push_back (int data) {
Nút* new_node = new node ();
new_node-> data = data;
new_node-> next = nullptr;
new_node-> prev = đuôi;

if (đuôi! = nullptr) {
đuôi-> next = new_node;
}

đuôi = new_node;

if (head == nullptr) {
đầu = new_node;
}
}

// loại bỏ một phần tử khỏi phía trước của deque
int pop_front () {
if (head == nullptr) {
Ném "Deque trống";
}

int data = head-> data;
Nút* temp = đầu;
đầu = đầu-> tiếp theo;

if (head! = nullptr) {
đầu-> prev = nullptr;
}

xóa temp;

if (head == nullptr) {
đuôi = nullptr;
}

trả về dữ liệu;
}

// loại bỏ một phần tử khỏi phía sau của deque
int pop_back () {
if (đuôi == nullptr) {
Ném "Deque trống";
}

int data = đuôi-> dữ liệu;
Nút* temp = đuôi;
đuôi = đuôi-> trước;

if (đuôi! = nullptr) {
đuôi-> next = nullptr;
}

xóa temp;

if (đuôi == nullptr) {
đầu = nullptr;
}

trả về dữ liệu;
}

// Nhận phần tử phía trước của deque
int front () {
if (head == nullptr) {
=======================================
#deque #C++ #datastructure #LinkedList #STL ## Deque in C++

A deque (double-ended queue) is a linear data structure that allows elements to be inserted and deleted at both ends. It is similar to a queue, but with the added ability to add and remove elements from the front of the deque. Deques are often used in applications where data needs to be added and removed in a non-destructive manner, such as in a real-time streaming application.

## Deque Implementation in C++

The deque data structure can be implemented in C++ using a doubly linked list. A doubly linked list is a linked list in which each node has two pointers, one to the next node and one to the previous node. This allows elements to be inserted and deleted from either end of the list in constant time.

The following code shows a simple implementation of a deque in C++:

```c++
#include <iostream>
#include <list>

using namespace std;

// A doubly linked list node
struct Node {
int data;
Node* next;
Node* prev;
};

// A deque class
class Deque {
public:
// Constructor
Deque() {
head = nullptr;
tail = nullptr;
}

// Destructor
~Deque() {
while (head != nullptr) {
Node* temp = head;
head = head->next;
delete temp;
}
}

// Insert an element at the front of the deque
void push_front(int data) {
Node* new_node = new Node();
new_node->data = data;
new_node->next = head;
new_node->prev = nullptr;

if (head != nullptr) {
head->prev = new_node;
}

head = new_node;

if (tail == nullptr) {
tail = new_node;
}
}

// Insert an element at the back of the deque
void push_back(int data) {
Node* new_node = new Node();
new_node->data = data;
new_node->next = nullptr;
new_node->prev = tail;

if (tail != nullptr) {
tail->next = new_node;
}

tail = new_node;

if (head == nullptr) {
head = new_node;
}
}

// Remove an element from the front of the deque
int pop_front() {
if (head == nullptr) {
throw "Deque is empty";
}

int data = head->data;
Node* temp = head;
head = head->next;

if (head != nullptr) {
head->prev = nullptr;
}

delete temp;

if (head == nullptr) {
tail = nullptr;
}

return data;
}

// Remove an element from the back of the deque
int pop_back() {
if (tail == nullptr) {
throw "Deque is empty";
}

int data = tail->data;
Node* temp = tail;
tail = tail->prev;

if (tail != nullptr) {
tail->next = nullptr;
}

delete temp;

if (tail == nullptr) {
head = nullptr;
}

return data;
}

// Get the front element of the deque
int front() {
if (head == nullptr) {