上一节:
下一节:

  数据结构&算法 队列

  • 队列

    队列是一种抽象的数据结构，有点类似于堆栈。与堆栈不同，队列的两端都是打开的。一端始终用于插入数据（入队），另一端用于删除数据（出队）。队列遵循先进先出的方法，即首先存储的数据项将首先被访问。
    队列的真实示例可以是单车道单向道路，车辆首先进入，然后首先离开。在售票窗口和公交车站的队列中，可以看到更多实际示例。

  • 队列表示

    现在我们知道在队列中，出于不同的原因访问两端。下面给出的下图试图将队列表示解释为数据结构-
    与在堆栈中一样，也可以使用数组，链接列表，指针和结构来实现队列。为了简单起见，我们将使用一维数组实现队列。

  • 基本操作

    队列操作可能涉及初始化或定义队列，利用它，然后从内存中完全擦除它。在这里，我们将尝试了解与队列相关的基本操作-
    • enqueue() -向队列添加（存储）项目。
    • dequeue() -从队列中删除（访问）一个项目。
    需要很少的功能来使上述队列操作高效。这些是-
    • peek -在队列的最前面获取元素而不删除它。
    • isfull -检查队列是否已满。
    • isempty -检查队列是否为空。
    在队列中，我们总是使前指针所指向的数据出队（或访问），而在队列中将数据入队（或存储）时，我们会使用后指针。首先让我们了解队列的支持函数-
    peek()
    此功能有助于查看队列前面的数据。peek()函数的算法如下- 
    
begin procedure peek
   return queue[front]
end procedure
    用C编程语言实现peek()函数- 
    
int peek() {
   return queue[front];
}
    isfull()
    当我们使用单维数组实现队列时，我们只需检查后指针达到MAXSIZE即可确定队列已满。如果我们将队列维护在循环链表中，则算法将有所不同。isfull()函数的算法- 
    
begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure
    用C编程语言实现isfull()函数- 
    
bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}
    isempty()
    isempty（）函数的算法- 
    
begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure
    如果front的值小于MIN或0，则表明队列尚未初始化，因此为空。
    用C编程语言实现isempty()函数- 
    
bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

  • 入队操作

    队列维护两个数据指针，前和后。因此，它的操作比堆栈的实现相对困难。应该采取以下步骤将数据排队（插入）到队列中-
    • 步骤1-检查队列是否已满。
    • 步骤2-如果队列已满，则产生溢出错误并退出。
    • 步骤3-如果队列未满，请增加后指针以指向下一个空白空间。
    • 步骤4-将数据元素添加到后方指向的队列位置。
    • 步骤5-返回成功。
    有时，我们还会检查队列是否已初始化，以处理任何无法预料的情况。
    入队操作算法 
    
procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure
    enqueue()在C编程语言中的实现-- 
    
int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

  • 出队操作

    从队列访问数据是两个任务的过程-访问前端指向的数据并在访问后删除数据。采取以下步骤执行出队操作-
    • 步骤1-检查队列是否为空。
    • 步骤2-如果队列为空，则产生下溢错误并退出。
    • 步骤3-如果队列不为空，请访问front指向的数据。
    • 步骤4-递增前指针以指向下一个可用的数据元素。
    • 步骤5-返回成功。
    出队操作算法 
    
procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure
    用C编程语言实现dequeue（）- 
    
int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

  • 队列在C中完整实现

    我们将在这里看到用C编程语言实现的堆栈实现。 
    
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 6

int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;

int peek() {
   return intArray[front];
}

bool isEmpty() {
   return itemCount == 0;
}

bool isFull() {
   return itemCount == MAX;
}

int size() {
   return itemCount;
}  

void insert(int data) {

   if(!isFull()) {
  
      if(rear == MAX-1) {
         rear = -1;            
      }       

      intArray[++rear] = data;
      itemCount++;
   }
}

int removeData() {
   int data = intArray[front++];
  
   if(front == MAX) {
      front = 0;
   }
  
   itemCount--;
   return data;  
}

int main() {
   /* insert 5 items */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);

   // front : 0
   // rear  : 4
   // ------------------
   // index : 0 1 2 3 4 
   // ------------------
   // queue : 3 5 9 1 12
   insert(15);

   // front : 0
   // rear  : 5
   // ---------------------
   // index : 0 1 2 3 4  5 
   // ---------------------
   // queue : 3 5 9 1 12 15
  
   if(isFull()) {
      printf("Queue is full!\n");   
   }

   // remove one item 
   int num = removeData();
  
   printf("Element removed: %d\n",num);
   // front : 1
   // rear  : 5
   // -------------------
   // index : 1 2 3 4  5
   // -------------------
   // queue : 5 9 1 12 15

   // insert more items
   insert(16);

   // front : 1
   // rear  : -1
   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15

   // As queue is full, elements will not be inserted. 
   insert(17);
   insert(18);

   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15
   printf("Element at front: %d\n",peek());

   printf("----------------------\n");
   printf("index : 5 4 3 2  1  0\n");
   printf("----------------------\n");
   printf("Queue:  ");
  
   while(!isEmpty()) {
      int n = removeData();           
      printf("%d ",n);
   }   
}
    尝试一下
    如果我们编译并运行上述程序，它将产生以下结果- 
     
Queue is full!
Element removed: 3
Element at front: 5
----------------------
index : 5 4 3 2 1 0
----------------------
Queue: 5 9 1 12 15 16
上一节:
下一节: