C++ 中静态队列与单向链表的区别

2025年03月22日 | 阅读 9 分钟

在本文中，我们将讨论 C++ 中静态队列和单向链表之间的区别。在讨论它们的区别之前，我们必须先了解 C++ 中的静态队列和单向链表，以及它们的函数和示例。

什么是静态队列？

静态队列是一种基本类型的数据结构，用于根据先进先出 (FIFO) 原则来排列和管理元素集合。

元素被添加到静态队列的一端（称为队尾或尾部），并从另一端（称为队首或头部）移除。由于静态队列保持元素添加的顺序，因此最初插入的元素总是第一个被移除的。

数组是一种具有预定容量和固定大小的数据结构，常用于创建静态队列。静态队列的固定大小使其区别于动态队列，动态队列的大小可以在运行时动态修改。尽管动态队列提供了更大的灵活性，但在内存效率很重要且集合大小提前已知的情况下，静态队列很有用。

静态队列的一些优点包括易于创建、内存效率高和性能可预测。由于内存分配是预先定义且恒定的，因此无需重新分配或动态内存管理，这可以减少开销并消除内存碎片化的可能性。

此外，静态队列的入队和出队操作提供恒定的时间复杂度，因为它们只需要简单的数组索引和指针操作。需要考虑静态队列的局限性。由于其固定大小，队列最多可以容纳特定数量的元素，如果未充分利用，则可能导致内存浪费；如果计划的容量过大，则可能导致容量不足。此外，与动态队列相比，调整静态队列的大小可能更复杂且效率较低，因为它需要修改数组大小。

静态队列的函数

以下是静态队列支持的主要函数：

入队 (Enqueue): 将一个项添加到队列的尾部称为入队。一旦元素被插入到数组中由尾部指针指定的位置，尾部指针就会递增到下一个可用位置。如果数组有空间，入队操作以恒定的时间 O(1) 执行。
出队 (Dequeue): 从队列的头部移除一个项称为出队。通过将头部指针递增到队列中的下一个元素，在此操作期间会移除由头部指针指定位置处的元素。出队操作也以恒定的时间 O(1) 执行。
队首 (Front): 在不移除的情况下检索队列头部处的元素。此操作允许用户查看下一个将被出队的元素。队首操作以 O(1) 的恒定时间执行。
判空 (IsEmpty): 确定队列是否为空。如果队列中没有元素，此操作将返回 true；否则返回 false。IsEmpty 函数以 O(1) 的恒定时间执行。
判满 (IsFull): 确定队列是否已满。如果队列中的元素数量等于数组的容量，这表明队列已满，此操作将返回 true，因为数组的大小是固定的。

示例

让我们举一个 C++ 中说明静态队列的例子。

 
#include <iostream>
#define MAX_SIZE 100 
// Maximum size of the Queue
class StaticQueue
{
private:
    int data[MAX_SIZE];
    //Array for storing queue elements
    int front; 
    //Index of the front element
    int rear; 
    //Index of the rear element
public:
    // Constructor for the Queue's initialization
    StaticQueue()
    {
        front = -1;
        //Initialize the front Index
        rear = -1;
        //Initialize the rear index
    }
    // Function to verify whether the Queue is empty
    bool isEmpty() 
    {
        return front == -1; 
        //Queue is empty if the front is equal to -1
    }
    // Function to verify if the Queue is full
    bool isFull() 
    {
        return (rear + 1) % MAX_SIZE == front; 
        //Queue is full if the rear is one Position before the front
    }
    // Function to enqueue an element to the rear of the Queue
    void enqueue(int ele) 
    {
        if (isFull())
        {
            std::cout << "The Queue is full. Cannot enqueue the elements.\n";
            return;
        }
        if (isEmpty())
        {
            front = 0; 
            // If the Queue is empty, set the front to 0
        }
        rear = (rear + 1) % MAX_SIZE; 
        // Move rear circularly.
        data[rear] = ele; 
        // Insert element at rear
        std::cout << "The enqueued element is: " << ele << std::endl;
    }
    // Function to dequeue an element from the front of the Queue
    void dequeue() 
    {
        if (isEmpty())
        {
            std::cout << "Queue is empty. Cannot dequeue element.\n";
            return;
        }
        int d = data[front]; 
        // Get the element at the front
        if (front == rear)
        {
            front = -1; 
            // If there is only one element in the Queue, reset the front and rear
            rear = -1;
        }
        else
        {
            front = (front + 1) % MAX_SIZE; 
            // Move front circularly
        }
        std::cout << "The dequeued element is: " << d << std::endl;
    }
    // Function to display the elements of the Queue.
    void display()
    {
        if (isEmpty()) 
        {
            std::cout << "Queue is empty.\n";
            return;
        }
        std::cout << "The Queue elements are: ";
        int m = front;
        do {
            std::cout << data[m] << " ";
            m = (m + 1) % MAX_SIZE; 
            // Move to the next element circularly.
        } while (m != (rear + 1) % MAX_SIZE); 
        // Loop continues until the rear element is reached.
        std::cout << std::endl;
    }
};
int main() 
{
    StaticQueue q;
    q.enqueue(20);
    q.enqueue(29);
    q.enqueue(38);
    q.enqueue(42);
    q.display();
    q.dequeue();
    q.dequeue();
    q.display();
    q.enqueue(57);
    q.enqueue(64);
    q.display();
    return 0;
}   

输出

 
The enqueued element is: 20
The enqueued element is: 29
The enqueued element is: 38
The enqueued element is: 42
The Queue elements are: 20 29 38 42 
The dequeued element is: 20
The dequeued element is: 29
The Queue elements are: 38 42 
The enqueued element is: 57
The enqueued element is: 64
The Queue elements are: 38 42 57 64

说明

此 C++ 代码使用数组来指定静态队列数据结构的操作。StaticQueue 类封装了队列，它包含一个存储元素的 data 数组和整数变量 front 和 rear 来表示队列的头部和尾部索引。该类具有检查队列是否为空或已满、从头部入队元素、从尾部出队元素以及显示队列元素的方法。在 main() 方法中创建了一个名为 q 的静态队列来演示队列操作，并执行了入队、出队和显示元素的演示。通过循环数组索引，保持了队列的循环行为，并有效地管理了元素。

什么是单向链表？

在 C++ 中，单向链表是一种用于有效管理和组织元素集合的基本数据结构。它由节点组成，每个节点有两个部分：数据和一个指向序列中下一个节点的指针或引用。这种结构实现了高效的插入、删除、遍历和搜索操作，并支持动态内存分配。动态内存分配是单向链表的主要优势之一。

由于节点是根据需要动态分配的，因此可以有效地使用和管理内存。当链表的大小在运行时未知或可能经常发生显著变化时，此功能特别有用。

插入和删除操作通常是高效的，因为可以在不要求调整大小或移动元素的情况下将节点添加到链表中或从链表中移除。正是这种灵活性使得可以根据应用程序的需求创建不同大小的链表。

单向链表的遍历是一个迭代过程，从头部节点开始，通过跟随指针遍历链表中的每个节点直到结束。此方法支持诸如搜索特定数字或对数据执行计算等操作，从而能够高效地访问数据的所有元素。

但是，单向链表也有一些限制。与数组不同，链表不能基于索引进行随机访问，因为访问元素需要从头开始遍历链表。此外，单向链表需要额外的内存开销来存储指针，与数组等连续数据结构相比，这会影响内存使用和性能。

示例

让我们举一个 C++ 中说明单向链表的例子。

 
#include <iostream>
//Creating a node structure
struct Node
{
    int node_data;
    Node* next;
    //Constructor
    Node(int d) : node_data(d), next(nullptr) {}
};
//Creating a Linked List class
class LinkedList
{
private:
    Node* head;
public:
    // Constructor of the class
    LinkedList() : head(nullptr) {}
    // Destructor of the class
    ~LinkedList()
    {
        Node* curr_ent = head;
        while (curr_ent != nullptr)
        {
            Node* next = curr_ent->next;
            delete curr_ent;
            curr_ent = next;
        }
        head = nullptr;
    }
    //Insertion at the beginning
    void InsertingAtBeginning(int new_data)
    {
        Node* new_Node = new Node(new_data);
        new_Node->next = head;
        head = new_Node;
    }
    //Insertion at the end
    void InsertingAtEnd(int new_data)
    {
        Node* new_Node = new Node(new_data);
        if (head == nullptr)
        {
            head = new_Node;
        }
        else
        {
            Node* curr_ent = head;
            while (curr_ent->next != nullptr)
            {
                curr_ent = curr_ent->next;
            }
            curr_ent->next = new_Node;
        }
    }
    // Display the linked ListList
    void Display()
    {
        Node* curr_ent = head;
        while (curr_ent != nullptr)
        {
            std::cout << curr_ent->node_data << " ";
            curr_ent = curr_ent->next;
        }
        std::cout << std::endl;
    }
    // Searching for a value 
    bool search(int key_element)
    {
        Node* curr_ent = head;
        while (curr_ent != nullptr)
        {
            if (curr_ent->node_data == key_element)
            {
                return true;
            }
            curr_ent = curr_ent->next;
        }
        return false;
    }
    // Deleting a value at the beginning
    void DeletingAtBeginning() 
    {
        if (head == nullptr) 
        {
            std::cout << "ListList is empty. Cannot delete the element." << std::endl;
            return;
        }
        Node* t = head;
        head = head->next;
        delete t;
    }
    // Deleting a value at a specific position
    void DeletingAtPosition(int p)
    {
        if (head == nullptr) 
        {
            std::cout << "ListList is empty. Cannot delete the element." << std::endl;
            return;
        }
        if (p == 0)
        {
            DeletingAtBeginning();
            return;
        }
        Node* curr_ent = head;
        Node* prev = nullptr;
        int index = 0;
        while (curr_ent != nullptr && index != p) 
        {
            prev = curr_ent;
            curr_ent = curr_ent->next;
            index++;
        }
        if (curr_ent == nullptr) 
        {
            std::cout << "Position is out of range. Cannot delete the element." << std::endl;
            return;
        }
        prev->next = curr_ent->next;
        delete curr_ent;
    }
};
int main()
{
    LinkedList l;
    // Inserting some elements
    l.InsertingAtEnd(15);
    l.InsertingAtEnd(24);
    l.InsertingAtEnd(38);
    // Displaying the ListList of elements
    std::cout << "The Linked List elements are: ";
    l.Display();
    // Inserting an element at the beginning
    l.InsertingAtBeginning(1);
    std::cout << "After inserting elements at the beginning is: ";
    l.Display();
    // Deleting an element at a position
    l.DeletingAtPosition(2);
    std::cout << "After deleting element at position 2: ";
    l.Display();
    // Searching for an element
    int key_element = 38;
    if (l.search(key_element))
    {
        std::cout << key_element << " element is found in the list." << std::endl;
    } 
    else 
    {
        std::cout << key_element << " element is not found in the list." << std::endl;
    }
    // Deleting an element at the beginning
    l.DeletingAtBeginning();
    std::cout << "After deleting the element at the beginning, it is: ";
    l.Display();
    return 0;
}   

输出

 
The Linked List elements are: 15 24 38 
After inserting elements at the beginning is: 1 15 24 38 
After deleting element at position 2: 1 15 38 
38 element is found in the list.
After deleting the element at the beginning, it is: 15 38

说明

此 C++ 代码定义了一个单向链表数据结构及相关函数。LinkedList 中的每个条目都由一个 Node 结构组成，其中包含数值数据以及指向下一个节点的引用。LinkedList 类封装了链表，还提供了在链表开头和结尾插入和删除元素、搜索元素以及显示链表的方法。在 main() 方法中，创建了一个链表 (l)，并在其开头、结尾和特定位置插入了元素，并对每个元素执行了搜索操作。最后，从开头删除了一个元素。在每个阶段都会显示链表，以展示操作对每个元素的影响。

C++ 中静态队列和单向链表之间的主要区别

此表简要总结了单向链表和静态队列在实现、内存管理、操作、时间复杂度、灵活性、利用率、开销和实现复杂性方面的区别。

特性	静态队列	单向链表
内存组织	内存分配是连续的。	内存分配是非连续的。
大小	大小固定。	大小动态。
信息类型	存储单一类型的信息或数据。	存储指向下一个节点和数据的引用。
数据结构类型	使用数组实现。	使用指针和节点实现。
访问方法	索引方法	引用方法
插入和删除	可以在固定端（头部和尾部）插入或删除元素。	可以在链表中的任何位置插入或删除元素。
排序	FIFO（先进先出）先插入的元素先删除。	顺序可以是 FIFO 或 LIFO。
指针	两个指针（头部和尾部）。	单个指针（头部）。

下一主题C++ 中的小行星碰撞

C++ 中静态队列与单向链表的区别

什么是静态队列？

静态队列的函数

示例

说明

什么是单向链表？

示例

说明

C++ 中静态队列和单向链表之间的主要区别

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中静态队列与单向链表的区别

什么是静态队列？

静态队列的函数

示例

说明

什么是单向链表？

示例

说明

C++ 中静态队列和单向链表之间的主要区别

相关帖子

如何在 C++ 中使用 const_iterator 遍历列表

C++ 优先级调度程序

C++ 2-SAT 问题

C++ 与 TCL 的区别

C++ 中的毕达哥拉斯四元组

C++ 中查找给定数组中的所有好索引

C++ STL 中的 UTF-8 到宽字符转换

C++ 中翻转最少次数的连续 0 和 1 子串所需的最小翻转次数

C++ 淘汰赛

C++ 中的杰出数

订阅 Tpoint Tech

联系信息