Queue

01 Sep 2022 in Study / Computer science on Queue

Data Structure, 이것이 자료구조+알고리즘이다 with C언어 (reference)

• A kind of data structure
• FIFO (First in, First out)

Basic Method

• enQueue : add
• deQueue : delete
• peek : just bring the top datum

Deque

• can implement both stack and queue
• can process at both ends
• ←→ □□□□□□□□ ←→
• Using Linked list

Queue In Java

• Queue is interface (we can use polymorphism with linked list)

import java.util.Queue;
import java.util.LinkedList;

public class queuepractice {

	public static void main(String[] args) {
		Queue<Integer> q = new LinkedList<Integer>();

		q.add(3); //[3]
		q.add(8); //[3, 8]
		q.add(10); //[3, 8, 10]

		System.out.println(q.remove()); //[8, 10], print : 3
		System.out.println(q.poll()); //[10], print : 8 (if isEmpty >> return null)

		System.out.println(q.isEmpty()); //false

		System.out.println(q.peek()); //10

		System.out.println(q); //[10]

	}

}

• Deque : can also be used for stack
  • Deque is interface
  • import java.util.Deque;
  • Deque d = new LinkedList();
  • Representative method
    • addFirst(element)
    • addLast(element)
    • removeFirst()
    • removeLast()
    • peekFirst()
    • peekLast()

Queue In Python

• We can implement Queue by list, Queue class, and Deque
• List
  • pop(0) & append()
  • inefficient : end processing should use linked list for fast work
• Queue class
  • from queue import Queue
  • q = Queue()
  • q.put(element) // add
  • q.get() // delete
• Deque
  • from collections import deque
  • dq = deque(list or empty)
  • append() & popleft() : implement queue
  • appendLeft() & pop() : implement queue

Queue In C with Array

• There are 2 ways for queue with C
• One way is to use Array
  • more efficient than linked list
  • cannot change the capacity of queue
• There are 2 concepts for implementing queue
  • Front index
    • The location that gonna be removed
  • Rear index
    • The location that gonna be added
  • We do adding & removing through simply moving the front & rear index
    • That is, we won’t remove actual memory of array
• If queue is implemented by linear array (first location is not connected to last location)
  • As rear index goes down to the end of array, the number of the places that are available decreases (∵ We do adding & removing through simply moving the front & rear index)
  • That’s why we use circular queue (순환큐) whose first location is connected to last location
• However, there is one matter when we use circular queue
  • Both empty state (there is no element in the queue) and full state (there is no space for adding an element) have the state that the front index is same with the rear index
  • For distinguishing them, we use the dummy node
    • That is, we add one more memory to original capacity of the array (it always stay empty state)
    • For implementing the dummy node, we make the array with (actual capacity + 1) & rear index gonna be (actual rear index + 1)
      • actual rear index means the index whose element is last element of the array
• Circular Queue Struct (let array’s element be integer)

typedef struct circularQueue
{
  int capacity;
  int front;
  int rear;

  int* data;
} CircularQueue;

• Create circular queue

void createCircularQueue(CircularQueue** queue, int capacity)
{
  *queue = (CircularQueue*)malloc(sizeof(CircularQueue));
  (*queue)->capacity = capacity;
  (*queue)->front = 0;
  (*queue)->rear = 0;

  (*queue)->data = (int*)malloc(sizeof(int) * (capacity + 1));
}

• Enqueue

void enqueueQueue(CircularQueue* queue, int datum)
{
  int position = 0;

  if (queue->rear == queue->capacity)
  {
    position = queue->rear;
    queue->rear = 0;
  }
  else
  {
    position = queue->rear++;
  }

  queue->data[position] = datum;
}

• Dequeue

int dequeueQueue(CircularQueue* queue)
{
  int position = queue->front;

  if (queue->front == queue->capacity)
  {
    queue->front = 0;
  }
  else
  {
    queue->front++;
  }

  return queue->data[position];
}

• Check whether it is empty or not

int isEmptyQueue(CircularQueue* queue)
{
  return (queue->front == queue->rear);
}

• Check whether it is full or not

int isFullQueue(CircularQueue* queue)
{
  if (queue->front < queue->rear)
  {
    return (queue->rear - queue->front == queue->capacity);
  }
  else
  {
    return (queue->rear + 1 == queue->front);
  }
}

• Destroy Circular Queue

void destroyQueue(CircularQueue** queue)
{
  free((*queue)->data);
  (*queue)->data = NULL;
  free(*queue);
  *queue = NULL;
}

Queue in C with Linked List

• There are 2 ways for queue with C
• One way is to use Linked list
  • easier for implementing queue than array
  • no limitation when it comes to the capacity
• There are 2 concepts for implementing queue
  • Front index
  • Rear index
• Unlike the array, we just make the queue with linear shape (we don’t need to consider cicular queue or dummy node) because there is no limitation about the capacity
• Data Node & Linked List Queue Struct

typedef struct node
{
  int data;
  struct node* nextNode;
} Node;

Node* createNode(int datum)
{
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = datum;
  newNode->nextNode = NULL;

  return newNode;
}

void destroyNode(Node** target)
{
  free(*target);
  *target = NULL;
}

typedef struct linkedlistqueue
{
  Node* front;
  Node* rear;

  int count;
} LinkedListQueue;

• Create Linked List Queue

void createLinkedListQueue(LinkedListQueue** queue)
{
  *queue = (LinkedListQueue*)malloc(sizeof(LinkedListQueue));
  (*queue)->front = NULL;
  (*queue)->rear = NULL;
  (*queue)->count = 0;
}

• Enqueue

void enqueueQueue(LinkedListQueue* queue, Node* newNode)
{
  if (queue->front == NULL)
  {
    queue->front = newNode;
    queue->rear = newNode;
    queue->count++;
  }
  else
  {
    queue->rear->nextNode = newNode;
    queue->rear = newNode;
    queue->count++;
  }
}

• Dequeue

Node* dequeueQueue(LinkedListQueue* queue)
{
  if (queue->front == NULL)
    return NULL;

  Node* poped = queue->front;

  if (queue->front->nextNode == NULL)
  {
    queue->front = NULL;
    queue->rear = NULL;
    queue->count--;
  }
  else
  {
    queue->front = queue->front->nextNode;
    queue->count--;
  }

  return poped;
}

• Destroy Linked List Queue

void destroyLinkedListQueue(LinkedListQueue** queue)
{
  while ((*queue)->front != NULL)
  {
    Node* poped = dequeueQueue(*queue);
    destroyNode(&poped);
  }

  free(*queue);
  *queue = NULL;
}