数据结构小记【Python/C++版】——队列篇

  • 开发
  • 30

一，基础概念

队列是由同一种数据元素组成的线性表结构。使用单向队列时，插入元素在一端进行而删除元素在另一端进行。

插入元素的一端在队列尾部(rear)，删除元素的一端在队列头部(front)。新的数据元素不断从尾部进入队列，然后一直向前移动到头部。

队列与栈的结构相反，遵循的是先进先出(FIFO)原则。

队列结构在生活中的抽象模型有：售票口的排队队伍，打印机中一堆待打印的材料，它们都是先进先出的。

二，队列的图示结构

1.顺序队列，按照顺序结构进行存储，类似于数组

2.顺序队列的假溢出问题

对于顺序队列，不断的出队和入队操作，会让队列尾部的指针一直后移(rear=rear+1)，直到超出队列的内存空间，此时，队列的存储空间还没被占满。队列的存储元素还没占满整个空间，队列的指针却发生了溢出，此现象被称为假溢出。为了避免假溢出问题，开发者更多时候使用特殊的顺序队列——循环队列。

3.特殊的顺序队列——循环队列

4.链式队列，按照链式结构进行存储，类似于链表

分别将元素12，24，36添加到队列，效果如图所示

三，队列的常见操作

Queue：初始化，创建一个空队列

enqueue：入队，在队列尾部添加一个元素

dequeue：出队，从队列头部移除一个元素，并返回

isEmpty：检查队列是否为空

size：返回队列中元素的数目

四，代码实现

注意，循环队列底层采用的是数组结构，链式队列底层采用的是单链表结构，因此，循环队列需要初始化队列的大小，即数组大小，而链式队列不需要。

1.循环队列的代码实现

循环队列在内存结构上还是一个普通数组，但是从抽象理解上，我们应该把它看作是一个头尾相连的环，通过取模运算来移动下标。

取模运算让队尾和队头的下标一直都在数组的地址空间以内移动，不会发生溢出。

假设循环队列的大小设置为maxSize

a.队尾下标往前移动一个单位：

rear = (rear + 1) % maxSize

b.队头下标往前移动一个单位：

front = (front + 1) % maxSize

c.判断队列是否为空：

front == rear（队尾和队头在同一个起点）

d.判断队列是否已满：

(rear + 1) % maxSize == front（队尾继续往前移动一个单位就可以和队头汇合）

Demo1.初始化

初始化时，顺序队列和循环队列的代码表示方式是一样的。主要初始化数组的大小、队头和队尾的初始值。

Python代码实现：

class CircularQueue():
    def __init__(self, k):
        self.k = k
        self.queue = [None] * k
        self.head = -1
        self.tail = -1

C++代码实现：

#define SIZE 6
class Queue {
private:
    int items[SIZE], front, rear;
public:
    Queue() {
        front = -1;
        rear = -1;
    }
}

Demo2.入队

Python代码实现：

def enqueue(self, data):
    if ((self.tail + 1) % self.k == self.head):
        print("The circular queue is full\n")
    elif (self.head == -1):
        self.head = 0
        self.tail = 0
        self.queue[self.tail] = data
    else:
        self.tail = (self.tail + 1) % self.k
        self.queue[self.tail] = data

C++代码实现：

void enQueue(int element) {
    if (isFull()) {
        cout << "Queue is full";
    }
    else {
        if (front == -1) front = 0;
        rear = (rear + 1) % SIZE;
        items[rear] = element;
        cout << endl << "Inserted " << element << endl;
    }
}

Demo3.出队

Python代码实现：

def dequeue(self):
    if (self.head == -1):
        print("The circular queue is empty\n")
    elif (self.head == self.tail):
        temp = self.queue[self.head]
        self.head = -1
        self.tail = -1
        return temp
    else:
        temp = self.queue[self.head]
        self.head = (self.head + 1) % self.k
        return temp

C++代码实现：

int deQueue() {
    int element;
    if (isEmpty()) {
        cout << "Queue is empty" << endl;
        return (-1);
    }
    else {
        element = items[front];
        if (front == rear) {
            front = -1;
            rear = -1;
        }
        else {
            front = (front + 1) % SIZE;
        }
        return (element);
    }
}

Demo4.完整代码实现

Python代码实现：

class CircularQueue():
    def __init__(self, k):
        self.k = k //定义循环队列的固定大小
        self.queue = [None] * k
        self.head = -1
        self.tail = -1

    def enqueue(self, data):
        if ((self.tail + 1) % self.k == self.head):
            print("The circular queue is full\n")
        elif (self.head == -1):
            self.head = 0
            self.tail = 0
            self.queue[self.tail] = data
        else:
            self.tail = (self.tail + 1) % self.k
            self.queue[self.tail] = data

    def dequeue(self):
        if (self.head == -1):
            print("The circular queue is empty\n")
        elif (self.head == self.tail):
            temp = self.queue[self.head]
            self.head = -1
            self.tail = -1
            return temp
        else:
            temp = self.queue[self.head]
            self.head = (self.head + 1) % self.k
            return temp

    def printCQueue(self):
        if (self.head == -1):
            print("No element in the circular queue")
        elif (self.tail >= self.head):
            for i in range(self.head, self.tail + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            for i in range(self.head, self.k):
                print(self.queue[i], end=" ")
            for i in range(0, self.tail + 1):
                print(self.queue[i], end=" ")
            print()

if __name__ == '__main__':
    obj = CircularQueue(5)
    obj.enqueue(1)
    obj.enqueue(2)
    obj.enqueue(3)
    obj.enqueue(4)
    obj.enqueue(5)
    obj.enqueue(6)
    print("Initial queue")
    obj.printCQueue()

    obj.dequeue()
    print("After removing an element from the queue")
    obj.printCQueue()

运行结果：

The circular queue is full
Initial queue
1 2 3 4 5
After removing an element from the queue
2 3 4 5

C++代码实现：

#include <iostream>
#define SIZE 6  //定义循环队列的固定大小
using namespace std;
class Queue {
private:
    int items[SIZE], front, rear;
public:
    Queue() {
        front = -1;
        rear = -1;
    }
    bool isFull() {
        if (front == (rear + 1) % SIZE) {
            return true;
        }
        if (front == 0 && rear == SIZE - 1) {
            return true;
        }
        if (front == rear + 1) {
            return true;
        }
        return false;
    }
    bool isEmpty() {
        if (front == -1)
            return true;
        else
            return false;
    }
    void enQueue(int element) {
        if (isFull()) {
            cout << "Queue is full";
        }
        else {
            if (front == -1) front = 0;
            rear = (rear + 1) % SIZE;
            items[rear] = element;
            cout << endl << "Inserted " << element << endl;
        }
    }
    int deQueue() {
        int element;
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return (-1);
        }
        else {
            element = items[front];
            if (front == rear) {
                front = -1;
                rear = -1;
            }
            else {
                front = (front + 1) % SIZE;
            }
            return (element);
        }
    }
    void display() {
        int i;
        if (isEmpty()) {
            cout << endl << "Empty Queue" << endl;
        }
        else {
            cout << endl << "Queue Items -> ";
            for (i = front; i != rear; i = (i + 1) % SIZE)
                cout << items[i];
            cout << items[i] << endl;
        }
    }
};
int main() {
    Queue q;
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);
    q.enQueue(6);
    q.enQueue(7);
    q.display();
    int elem = q.deQueue();
    if (elem != -1)
        cout << endl << "Deleted Element is " << elem;
    q.display();
    return 0;
}

运行结果： 

Inserted 1
Inserted 2
Inserted 3
Inserted 4
Inserted 5
Inserted 6
Queue is full
Queue Items -> 123456
Deleted Element is 1
Queue Items -> 23456

2.链式队列的代码实现

链式队列的实现方式类似于一个单链表，需要先初始化一个节点类Node。

Demo1.初始化

Python代码实现：

class Node:  //链表节点的初始化
    def __init__(self,data):
        self.data=data
        self.next=None

class Queue:  //链式队列的初始化
    def __init__(self):
        self.front=None
        self.queueSize=0

C++代码实现：

struct node //链表节点的初始化
{
       int value;
       node* next;
};

class Queue //链式队列的初始化
{
private:
       node* front;
       node* rear;
public:
       Queue()
       {
          front = NULL;
          rear = NULL;
       }
}

Demo2.入队

Python代码实现：

def enqueue(self, data):
    temp = Node(data)
    if self.front is None:  
        self.front = temp
        self.queueSize = self.queueSize + 1
    else:
        curr = self.front
        while curr.next != None:
            curr = curr.next
        curr.next = temp
        self.queueSize = self.queueSize + 1

C++代码实现：

void EnQueue(int n)
{
    node* temp = new node();
    temp->value = n;
    temp->next = NULL;
    if (front == NULL && rear == NULL)
    {
        front = rear = temp;
        return;
    }
    rear->next = temp;
    rear = temp;
}

Demo3.出队

Python代码实现：

def dequeue(self):
    try:
        if self.front == None:
            raise Exception("Queue is Empty")
        else:
            temp = self.front
            self.front = self.front.next
            tempdata = temp.data
            self.queueSize = self.queueSize - 1
            del temp
            return tempdata
    except Exception as e:
        print(str(e))

C++代码实现：

void Dequeue()
{
    node* temp = front;
    if (front == NULL)
    {
        cout << "Queue is empty!\n";
        return;
    }
    else if (front == rear)
    {
        front = rear = NULL;
    }
    else
    {
        front = front->next;
    }

    delete temp;
}

Demo4.完整代码实现

Python代码实现：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.queueSize = 0

    def enqueue(self, data):
        newNode= Node(data)
        if self.front is None:
            self.front = newNode
            self.queueSize = self.queueSize + 1
        else:
            curr = self.front
            while curr.next != None:
                curr = curr.next
            curr.next = newNode
            self.queueSize = self.queueSize + 1

    def dequeue(self):
        try:
            if self.front == None:
                raise Exception("Queue is Empty")
            else:
                temp = self.front
                self.front = self.front.next
                tempdata = temp.data
                self.queueSize = self.queueSize - 1
                del temp
                return tempdata
        except Exception as e:
            print(str(e))

    def size(self):
        return self.queueSize

    def isEmpty(self):
        if self.queueSize == 0:
            return True
        else:
            return False

if __name__ == '__main__':
    Queue_obj = Queue()
    Queue_obj.enqueue("a")
    Queue_obj.enqueue("b")
    Queue_obj.enqueue("c")
    print("deque the elem: ", Queue_obj.dequeue())
    print("deque the elem: ", Queue_obj.dequeue())
    print("now the size is: ", Queue_obj.size())

运行结果：

deque the elem:  a
deque the elem:  b
now the size is:  1

C++代码实现：

#include<iostream>
using namespace std;
struct node
{
       int value;
       node* next;
};
class Queue
{
private:
       node* front;
       node* rear;
public:
       Queue()
       {
              front = NULL;
              rear = NULL;
       }
       void EnQueue(int n)
       {
              node* temp = new node();
              temp->value = n;
              temp->next = NULL;
              if (front == NULL && rear == NULL)
              {
                      front = rear = temp;
                      return;
              }
              rear->next = temp;
              rear = temp;
       }
       void Dequeue()
       {
              node* temp = front;
              if (front == NULL)
              {
                      cout << "Queue is empty!\n";
                      return;
              }
              else if (front == rear)
              {
                      front = rear = NULL;
              }
              else
              {
                      front = front->next;
              }
              delete temp;
       }
       void Display()
       {
              node* temp = front;
              cout << "Queue Item: ";
              while (temp != NULL)
              {
                      cout << temp->value << " ";
                      temp = temp->next;
              }
              cout << "\n";
       }
};
int main()
{
       Queue q;
       q.EnQueue(1);
       q.EnQueue(2);
       q.EnQueue(3);
       q.EnQueue(4);
       q.Display();
       q.Dequeue();  
       q.Dequeue();  
       q.Display();  
       return 0;
}

运行结果：

Queue Item: 1 2 3 4
Queue Item: 3 4

3. 内置数据类型实现

C++内置数据类型：STL标准库中的std::queue

Python内置数据类型：Queue模块

Demo1：

#include <iostream>
#include <queue>
using namespace std;
void showq(queue<int> gq)
{
    queue<int> g = gq;
    while (!g.empty()) {
        cout << '\t' << g.front();
        g.pop();
    }
    cout << '\n';
}
int main()
{
    queue<int> queObj;
    queObj.push(10);
    queObj.push(20);
    queObj.push(30);
    cout << "The queue queObj is : ";
    showq(queObj);
    cout << "queObj.size() : " << queObj.size() << endl;
    cout << "queObj.front() : " << queObj.front() << endl;
    cout << "queObj.back() : " << queObj.back() << endl;
    cout << "queObj.pop() : " << endl;
    queObj.pop();
    showq(queObj);
    return 0;
}

Demo2：

from queue import Queue

q = Queue(maxsize=6)
print(q.qsize())

q.put('a')
q.put('b')
q.put('c')

print("\nElements dequeued from the queue")
print(q.get())
print(q.get())
print(q.get())

print("\nEmpty: ", q.empty())

五，参考阅读

《Problem Solving with Algorithms and Data Structures Using Python, Second Edition》

https://www.programiz.com/dsa/circular-queue

https://prepinsta.com/c-program/implementation-of-queues-using-linked-list/

阅读全部

相关推荐

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-11 21:46:03       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-11 21:46:03       101 阅读

  9. 在Django里面运行非项目文件

    2024-03-11 21:46:03       82 阅读

  19. Python语言-面向对象

    2024-03-11 21:46:03       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-03-11 21:46:03       85 阅读

热门阅读

  1. 理论学习 消融实验

    2024-03-11 21:46:03       46 阅读

  2. 自定义注解【项目篇】

    2024-03-11 21:46:03       40 阅读

  5. [网络安全提高篇] 一二五.恶意软件分析之PE文件解析和利用Python获取样本时间戳及溯源

    2024-03-11 21:46:03       46 阅读

  7. 行为型模式

    2024-03-11 21:46:03       42 阅读

  9. 【微信小程序开发】如何去除scroll-view默认的滚动条

    2024-03-11 21:46:03       28 阅读

  12. 738. 单调递增的数字

    2024-03-11 21:46:03       45 阅读

  14. sqoop-import 详解

    2024-03-11 21:46:03       38 阅读

  15. 最多几个直角三角形python

    2024-03-11 21:46:03       47 阅读

  18. Node docker 容器部署及配置参数

    2024-03-11 21:46:03       43 阅读

  19. 用户登录问题——登录态

    2024-03-11 21:46:03       43 阅读

  23. 算法补习基础完整版

    2024-03-11 21:46:03       39 阅读

  28. LeetCode解法汇总2129. 将标题首字母大写

    2024-03-11 21:46:03       38 阅读