Queue data structure

Speak, my chair! All beauty with you?

We have already studied lists and stacks, in this article we will review the main points about the queue data structure and answer some questions.

theory

at queuesor queues In English, she Abstract data types (Boy). be private menus that follow the principle FIFO (first in, first out), where the first item to be inserted is the first to be removed.

Elements are added to the end of the structure and removed from its beginning. In the rows, we use one end of the input and the other for removal.

Figure 1: Queue structure.

The principle followed by waiting lists is FIFO (First In First Out), that is, the first element to be entered is the first to leave. As a similar principle, we have lilo (Last In Last Out): The last item to be entered is the last item to be left.

Usage examples:

  • control of documents for printing;
  • Exchange of messages between computers on the network.

Queues can be, like piles outlet In two ways:

  • fixed shape, using array(vector); or
  • dynamic shapeusing the linked list.

We can get the following operations To handle the stack:

  • Create a queue: informs the power in the case of sequential execution (bus)
  • List (standing in line):
    • Adds an item after the last item in the queue;
    • The element to be added is the parameter of this operation;
  • deco (Unfamiliar):
    • removes the item in the first position from the queue;
    • return this item;
  • Empty: checks if the queue is empty;
  • Full of: Checks if the queue is full.

have Waiting List Specialties How do:

  • circular queues; And
  • floors.

at circular rows It helps to eliminate the relative waste of time in sequential queue, caused by shifting queue elements to the first positions. They can be very useful in enabling reuse of vacancies, without the need for data transfer.

circular queue

Figure 2: A circular queue.

you floors (Double-ended queues) are double-end queues, that is, insertions and removals are possible at the beginning of the queue and at the end of the queue.

Usage examples:

  • a marine or river channel;
  • Ease of use with two-way traffic.

Quiz questions

[UFSM 2017 UFSM – Técnico de Tecnologia da Informação] Check the variant which is a data structure where each new element is inserted at the end of the structure and removed at the beginning.

[A] vector.
[B] headquarters.
[C] Row.
[D] battery.
[E] tree

comments:

The question brought the correct perception of queues.

reactions: letter c.

[SUGEP/UFRPE 2016 UFRPE – Técnico em Tecnologia da Informação] On linear data structures, analyze the proposals below.

[4] Queue is implemented much more effectively, in a simply linked list, if removals are made at the head of the list, and entries are at the bottom of the list.

comments:

The text was confusing because, in queues, only removals are made at the top of the list and entries are at the bottom of the list. This does not make queuing implementation more efficient. This is the rule that the queue must follow.

But, setting aside the rigor of this interpretation, the examiner took the text for granted.

reactions: right.

[NUCEPE 2018 PC/PI – Perito Criminal – Informática] Regarding the queue-like data structure, consider the insertions and removals of the F queue below:

1. queue (‘yellow’, F) 2. queue (‘white’, F) 3. queue (‘green’, F) 4. queue (‘red’, F) 5. queue (F) ) 6. queue (F) 7. queue (‘blue’, F) 8. queue (unqueue (F), F)

Final results of operations in:

[A] [verde, azul, vermelho].
[B] [branco, azul, amarelo].
[C] [verde, azul].
[D] [amarelo, branco].
[E] [vermelho, azul, verde].

comments:

This question requires the use of the enqueue (enqueue) and dequeue (dequeue) operations:

  • 1. Queue (“yellow”, F):
    • Create a queue with the yellow element;
    • row: yellow (oldest element);
  • 2. Queue (“white”, F):
    • The white element is inserted at the end of the list;
    • Grade: yellow (the oldest element), white;
  • 3. Queue (“green”, F):
    • The green element is inserted at the end of the list;
    • Row: yellow (the oldest element), white, green;
  • 4. Queue (“red”, F):
    • insert the red item at the end of the list;
    • Row: yellow (the oldest element), white, green, red;
  • 5. dequeue (F):
    • removes the oldest component: yellow;
    • Row: white (currently oldest element), green, red;
  • 6. dequeue (F):
    • removes the oldest component: white;
    • queue: green (currently oldest item), red;
  • 7. Queue (“blue”, F):
    • The blue element is inserted at the end of the list;
    • queue: green (currently oldest item), red, blue;
  • 8. Queue (unqueue (F), F):
    • We have a dequeue process inside an enqueue process;
    • removes the oldest element first: green;
    • then enter the removed green item at the end of the list;
    • Row: red (currently oldest element), blue, green.

At the end, the queue contains the following items: red, blue and green.

reactions: the letter e.

[Instituto AOCP 2018 – PRODEB – Analista de TIC II – Construção de Software] During system programming, it is possible to use a structure that uses a methodology called FIFO (First In First Out), where the first input is the first out, where the elements are taken care of sequentially or used as stored.

This structure is called

[A] List.
[B] linked list.
[C] binary tree.
[D] battery.
[E] Row.

comments:

If it follows the FIFO principle, it is a queue.

reactions: the letter e.

[Instituto AOCP 2016 EBSERH – Analista de Tecnologia da Informação – Sistemas Operacionais (Nacional)] In a virtual memory system that uses paging, all page frames can be full when an operation is requested. In the page replacement strategy that replaces the page that has been in the system for the longest time, the structure

[A] FIFO
[B] battery.
[C] LIFO
[D] tree.
[E] scaling.

comments:

When the element in the queue is the longest, it is the element that will be removed first, i.e. FIFO (the first element inserted, the oldest, is the first element to be removed.

Thus, the principle of the structure in the case of the question is FIFO.

reactions: the letter.

[CESGRANRIO 2014 Banco da Amazônia – Técnico Científico – Analise de Sistemas] Consider a queue structure (FIFO system) of integers with two operations: INSERT(n) and REMOVE(). Also keep in mind that representing the state of the queue at any given moment is done by listing the items, so that the first item, left to right, is the oldest item in the queue.
If the queue starts empty, the sequence

insert (2)
insert (3)
Withdraw ( )
insert (1)
Withdraw ( )
insert (4)
insert (5)
Withdraw ( )
Withdraw ( )

It will lead to a queue in the country

[A] 1 2 3 4 5
[B] 2 3 1 4 5
[C] 3 1 4
[D] 4 5
[E] 5

comments:

Another question with enqueue and dequeue operations:

  • Enter (2):
    • Create a queue with item 2;
    • row: 2 (oldest element);
  • Enter (3):
    • insert item 3 at the end of the list;
    • row: 2 (oldest element), 3;
  • Withdraw ( ):
    • removes the oldest element: 2;
    • Row: 3 (currently oldest element);
  • Enter (1):
    • item 1 is inserted at the end of the list;
    • row: 3 (oldest element), 1;
  • Withdraw ( ):
    • removes the oldest element: 3;
    • queue: 1 (currently oldest item);
  • Enter (4):
    • insert item 4 at the end of the list;
    • row: 1 (oldest element), 4;
  • Enter (5):
    • insert item 5 at the end of the list;
    • Row: 1 (oldest element), 4, 5;
  • Withdraw ( ):
    • removes the oldest element: 1;
    • row: 4 (oldest element), 5;
  • Withdraw ( ):
    • removes the oldest element: 4;
    • Grade: 5 (the oldest element).

At the end, the queue contains the following item: 5.

reactions: the letter e.

Then that’s it!
[]Until next time!
_________________________
Professor Rujirao Araujo

Leave a Comment