WEILAI Online Academic assistant
WEILAI Online Academic assistant
Back to 课程

Computer-Science-A-level-Ocr

0% Complete
0/0 Steps
  1. 3-3-networks
    8 主题
  2. 3-2-databases
    7 主题
  3. 3-1-compression-encryption-and-hashing
    4 主题
  4. 2-5-object-oriented-languages
    7 主题
  5. 2-4-types-of-programming-language
    4 主题
  6. 2-3-software-development
    5 主题
  7. 2-2-applications-generation
    6 主题
  8. 2-1-systems-software
    8 主题
  9. 1-3-input-output-and-storage
    2 主题
  10. 1-2-types-of-processor
    3 主题
  11. 1-1-structure-and-function-of-the-processor
    1 主题
  12. structuring-your-responses
    3 主题
  13. the-exam-papers
    2 主题
  14. 8-2-algorithms-for-the-main-data-structures
    4 主题
  15. 8-1-algorithms
    10 主题
  16. 7-2-computational-methods
    11 主题
  17. 7-1-programming-techniques
    14 主题
  18. 6-5-thinking-concurrently
    2 主题
  19. 6-4-thinking-logically
    2 主题
  20. 6-3-thinking-procedurally
    3 主题
  21. 6-2-thinking-ahead
    1 主题
  22. 6-1-thinking-abstractly
    3 主题
  23. 5-2-moral-and-ethical-issues
    9 主题
  24. 5-1-computing-related-legislation
    4 主题
  25. 4-3-boolean-algebra
    5 主题
  26. 4-2-data-structures
    10 主题
  27. 4-1-data-types
    9 主题
  28. 3-4-web-technologies
    16 主题
课 Progress
0% Complete

Implementing Linear Queues

How Do You Program a Queue?

  • To recap the main operations of Queues and how they work, follow this link

  • When programming a queue, the main operations listed below must be included in your program

    • Initialise the queue

    • Enqueue

    • Dequeue

    • Peek

Algorithm to Implement a Linear Queue

  • The code below initialises an array and index pointers to service a linear queue

  • The constant MAX_SIZE informs the size of the array

  • The front index pointer is initialised to 0 and the rear index pointer is initialised to -1

  • The rear index pointer will be incremented every time you add an item to the queue, so the initial value will ensure the first item is added into the first position of the array (index 0)

  • Once the first item has been added, both front and rear will correctly point to the item in the array 

Pseudocode

Python

Java

MAX_SIZE = 6

ARRAY queue[max_size]

front = 0

rear = -1

MAX_SIZE = 6

queue[]

front = 0

rear = -1

public class Main {

public static final int MAX_SIZE = 6;

public static ArrayList<Integer> queue = new ArrayList<>();

public static int front = 0;

public static int rear = -1;

public static void main(String[] args) {

// Your code here

}

}

EnQueue Data

  • Before adding an item to the queue you need to check that the queue is not full

  • When the rear index pointer is pointing to the final space in the array there is no room to add new items

  • A subroutine isFull() is used to carry out the check. 

  • If the end of the array has not been reached, the rear index pointer is incremented and the new item is added to the queue

Pseudocode

Python

Java

FUNCTION isFull(rear)

IF(rear+1) == MAX_SIZE THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDFUNCTION

FUNCTION enqueue(queue, rear, data)

IF isFull(rear) == True THEN

PRINT (“Full”)

ELSE 

rear = rear + 1

queue[rear] = data

ENDIF

RETURN rear

ENDFUNCTION

def isFull(rear):

if rear + 1 == MAX_SIZE:

return True

else:

return False

def enqueue(queue, rear, data):

if isFull(rear):

print("Full")

else:

rear = rear + 1

queue[rear] = data

return rear

# Example usage

queue = [None] * MAX_SIZE

rear = -1

rear = enqueue(queue, rear, 10)

rear = enqueue(queue, rear, 20)

rear = enqueue(queue, rear, 30)

print(queue) # [10, 20, 30]

public static boolean isFull(int rear) {

if (rear + 1 == MAX_SIZE) {

return true;

} else {

return false;

}

}

public static int enqueue(int[] queue, int rear, int data) {

if (isFull(rear)) {

System.out.println("Full");

} else {

rear = rear + 1;

queue[rear] = data;

}

return rear;

}

DeQueue Data

  • Before taking an item from the queue you need to make sure that the queue is not empty

  • A subroutine isEmpty() can be defined for this purpose

  • The subroutine will check whether the front index pointer is ahead of the rear index pointer

  • If the queue is not empty the item at the front of the queue is returned and front is incremented by 1

Pseudocode

Python

Java

FUNCTION isEmpty(front, rear)

IF front > rear THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDFUNCTION

FUNCTION dequeue(queue, rear, front)

IF isEmpty(front, rear) THEN

PRINT (“Empty”)

dequeuedItem = Null

ELSE 

dequeuedItem = queue[front]

front = front + 1

ENDIF

RETURN (dequeuedItem, front)

ENDFUNCTION

def isEmpty(front, rear):

if front > rear:

return True

else:

return False

def dequeue(queue, rear, front):

if isEmpty(front, rear):

print("Empty")

dequeuedItem = None

else:

dequeuedItem = queue[front]

front = front + 1

return dequeuedItem, front

# Example usage

MAX_SIZE = 100

queue = [10, 20, 30, 40, 50]

front = 0

rear = len(queue) - 1

dequeuedItem, front = dequeue(queue, rear, front)

print("Dequeued item:", dequeuedItem)

print("Front:", front)

dequeuedItem, front = dequeue(queue, rear, front)

print("Dequeued item:", dequeuedItem)

print("Front:", front)

import java.util.Arrays;

public class Main {

public static boolean isEmpty(int front, int rear) {

if (front > rear) {

return true;

} else {

return false;

}

}

public static Object[] dequeue(int[] queue, int rear, int front) {

if (isEmpty(front, rear)) {

System.out.println("Empty");

Object[] result = { null, front };

return result;

} else {

Object[] result = { queue[front], front + 1 };

return result;

}

}

public static void main(String[] args) {

int MAX_SIZE = 100;

int[] queue = { 10, 20, 30, 40, 50 };

int front = 0;

int rear = queue.length - 1;

Object[] dequeuedResult = dequeue(queue, rear, front);

Object dequeuedItem = dequeuedResult[0];

front = (int) dequeuedResult[1];

System.out.println("Dequeued item: " + dequeuedItem);

System.out.println("Front: " + front);

dequeuedResult = dequeue(queue, rear, front);

dequeuedItem = dequeuedResult[0];

front = (int) dequeuedResult[1];

System.out.println("Dequeued item: " + dequeuedItem);

System.out.println("Front: " + front);

}

}

Implementing Circular Queues

Algorithm to Implement a Circular Queue

  • When you manipulate the items in a circular queue you must be able to advance the index pointers in such a way that they will reset to 0 once the end has been reached

(pointer + 1) MOD MAX_SIZE

  • This can be used to calculate the new position for the index pointer

  • Where the pointer is front or rear and max_size is the maximum number of items in the queue. 

Let’s imagine there is an array with 7 items. 

Initial Position

Pointer + 1

(Pointer + 1) MOD 7

New Position

0

1

1

1

1

2

2

2

2

3

3

3

3

4

4

4

4

5

5

5

5

6

6

6

6

7

0

0

  • When the index pointer references the last position in the array, position 6, the next position is calculated as (6+1) MOD 7 which gives the result 0

  • This allows the index pointer to move back to the reference at the start of the array

Initialise Circular Queue

  • The initialisation is the same as a linear queue apart from you initialise the front index to -1 as this will allow you to be certain that you have an empty queue

Pseudocode

Python

Java

MAX_SIZE = 4

ARRAY cQueue[max_size]

front = -1

rear = -1

MAX_SIZE = 4

cQueue[]

front = -1

rear = -1

public class CircularQueue {

private static final int MAX_SIZE = 4;

private int[] cQueue = new int[MAX_SIZE];

private int front = -1;

private int rear = -1;

public static void main(String[] args) {

CircularQueue circularQueue = new CircularQueue();

// Use the circularQueue object to perform operations on the circular queue

}

}

Enqueue Circular Queue

  • Before an item can be enqueued the array needs to be checked to see if it’s full

  • It will be full if the next position to be used is already occupied by the item at the front of the queue

  • If the queue is not full then the rear index pointer must be adjusted to reference the next free position so that the new item can be added

Pseudocode

Python

Java

MAX_SIZE = 4

ARRAY cQueue[max_size]

front = -1

rear = -1

FUNCTION is_full(front, rear)

IF (rear + 1) MOD MAX_SIZE == front THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDFUNCTION 

FUNCTION enqueue(queue, front, rear, data)

IF is_full(front, rear) == True THEN

PRINT("Queue is full")

ELSE

rear = (rear + 1) MOD MAX_SIZE

queue[rear] = data

IF front = -1 THEN // First item to be queued

front = 0

ENDIF

ENDIF

RETURN (front, rear)

ENDFUNCTION

MAX_SIZE = 4

cQueue = [None] * MAX_SIZE

front = -1

rear = -1

def is_full(front, rear):

if (rear + 1) % MAX_SIZE == front:

return True

else:

return False

def enqueue(queue, front, rear, data):

if is_full(front, rear):

print("Queue is full")

else:

rear = (rear + 1) % MAX_SIZE

queue[rear] = data

if front == -1: # First item to be queued

front = 0

return front, rear

public class CircularQueue {

private static final int MAX_SIZE = 4;

private int[] cQueue = new int[MAX_SIZE];

private int front = -1;

private int rear = -1;

public static void main(String[] args) {

CircularQueue circularQueue = new CircularQueue();

// Use the circularQueue object to perform operations on the circular queue

}

}

DeQueue Circular Queue

  • Before dequeuing the array needs to be checked if it’s empty. If the queue is not empty then the item at the front is dequeued

  • If this is the only item that was in the queue, the rear and front pointers are reset 

  • Otherwise the pointer moves to reference the next item in the queue

Pseudocode

Python

Java

MAX_SIZE = 4

ARRAY cQueue[max_size]

front = -1

rear = -1

FUNCTION is_empty(rear)

IF front == -1 THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDFUNCTION

FUNCTION dequeue(queue, front, rear)

IF is_empty(rear) == True THEN

PRINT("Queue is empty - nothing to dequeue")

dequeued_item = Null

ELSE

dequeued_item = queue[front]

// Check if the queue is empty

IF front == rear THEN

front = -1

rear = -1

ELSE

front = (front + 1) MOD maxsize 

ENDIF

ENDIF

RETURN (dequeued_item, front, rear)

ENDFUNCTION

def is_empty(front):

if front == -1:

return True

else:

return False

def dequeue(queue, front, rear):

if is_empty(front):

print("Queue is empty - nothing to dequeue")

dequeued_item = None

else:

dequeued_item = queue[front]

if front == rear:

front = -1

rear = -1

else:

front = (front + 1) % MAX_SIZE

return dequeued_item, front, rear

public class CircularQueue {

private static final int MAX_SIZE = 4;

private Object[] cQueue = new Object[MAX_SIZE];

private int front = -1;

private int rear = -1;

public static void main(String[] args) {

CircularQueue circularQueue = new CircularQueue();

// Use the circularQueue object to perform operations on the circular queue

}

private boolean isEmpty(int front) {

if (front == -1) {

return true;

} else {

return false;</code

Responses

您的邮箱地址不会被公开。 必填项已用 * 标注