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

Posted on by hackdl

一，基础概念

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

插入元素的一端在队列尾部(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 fulln")
    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

Demo3.出队

Python代码实现：

def dequeue(self):
    if (self.head == -1):
        print("The circular queue is emptyn")
    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

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 fulln")
        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 emptyn")
        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 
#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  ";
            for (i = front; i != rear; i = (i + 1) % SIZE)
                cout

运行结果：

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 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
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 == NUL服务器托管网L)
              {
                      front = rear = temp;
                      return;
              }
              rear->next = temp;
              rear = temp;
       }
       void Dequeue()
       {
              node* temp = front;
              if (front == NULL)
              {
                      cout next;
              }
              delete temp;
       }
       void Display()
       {
              node* temp = front;
              cout value next;
              }
              cout

运行结果：

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

3. 内置数据类型实现

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

Python内置数据类型：Queue模块

Demo1：

#include 
#include 
using namespace std;
void showq(queue gq)
{
    queue g = gq;
    while (!g.empty()) {
        cout  queObj;
    queObj.push(10);
    queObj.push(20);
    queObj.push(30);
    cout

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

Queues using Linked List in C

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 使用html-webpack-plugin对HTML文件进行预处理

原文地址：https://segmentfault.com/a/1190000021518323作者：Fw恶龙本文首发于：思否 一、前言 先整理一波之前和webpack相关的文章: 使用Webpack对CSS文件进行后处理 基于Webpack的CSS Spri…

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: