Queue data structure

10 Key excerpts on "Queue data structure"

• 

  No longer available |Learn more

  Data Structures and Program Design Using Java

  A Self-Teaching Introduction

  • D. Malhotra, N. Malhotra(Authors)
  • 2020(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  5

  QUEUES

  5.1  Introduction

  A queue is an important data structure which is widely used in many computer applications. A queue can be visualized with many examples from our day-to-day life with which we are already familiar. A very simple illustration of a queue is a line of people standing outside to enter a movie theatre. The first person standing in the line will enter the movie theatre first. Similarly, there are many daily life examples in which we can see the queue being implemented. Hence, we observe that whenever we talk about a queue, we see that that the element at the first position will be served first. Thus, a queue can be described as a FIFO (first in, first out) data structure; that is, the element which is inserted first will be the first one to be taken out. Now, let us discuss more about queues in detail.

  5.2  Definition of a Queue

  A queue is a linear collection of data elements in which the element inserted first will be the element taken out first (i.e., a queue is a FIFO data structure).A queue is an abstract data structure, somewhat similar to stacks. Unlike stacks, a queue is open on both ends. A queue is a linear data structure in which the first element is inserted on one end called the REAR end (also called the tail end), and the deletion of the element takes place from the other end called the FRONT end (also called the head).One end is always used to insert data and the other end is used to remove data.

  Queues can be implemented by using arrays or linked lists. We will discuss the implementation of queues using arrays and linked lists in this section.  

  Practical Application

  • A real-life example of a queue is people moving on an escalator. The people who got on the escalator first will be the first ones to step off of it.
  • Another illustration of a queue is a line of people standing at the bus stop waiting for the bus. Therefore, the first person standing in the line will get into the bus first.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Data Structures and Program Design Using Python

  A Self-Teaching Introduction

  • D. Malhotra, N. Malhotra, Dheeraj Malhotra, Neha Malhotra(Authors)
  • 2020(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  CHAPTER 5

  QUEUES

  5.1 INTRODUCTION

  A queue is an important data structure that is widely used in many computer applications. A queue can be visualized with many examples from everyday life. A very simple illustration of a queue is a line of people standing outside a movie theater. The first person standing in the line will enter the movie theatre first. We observe that whenever we talk about a queue, we see that that the element in the first position is served first. Thus, a queue can be described as a FIFO (First-In, First-Out) data structure; that is, the element that is inserted first will be the first one to be taken out.

  5.2 DEFINITION OF A QUEUE

  A queue is a linear collection of data elements in which the element inserted first is the element taken out first (i.e., a queue is a FIFO data structure). A queue is an abstract data structure, somewhat similar to stacks. Unlike stacks, a queue is open on both ends. A queue is a linear data structure in which the first element is inserted on one end, called the REAR end (also called the tail end), and the deletion of the element takes place from the other end, called the FRONT end (also called the head). One end is always used to insert data and the other end is used to remove data.

  Queues can be implemented by using arrays or linked lists. We discuss the implementation of queues using arrays and linked lists in this section.

  Practical Application:

  ● A real-life example of a queue is people moving on an escalator. The people who got on the escalator first will be the first ones to step off of it.

  ● Another illustration of a queue is a line of people standing at the bus stop waiting for the bus. Therefore, the first person standing in the line will get into the bus first.

  5.3 IMPLEMENTATION OF A QUEUE

  Queues can be implemented using two data structures:

  1. arrays/lists

  2. linked lists

  5.3.1 Implementation of Queues Using Arrays

  Queues can be easily implemented using arrays. Initially, the front end (head) and the rear end (tail) of the queue point at the first position or location of the array. As we insert new elements into the queue, the rear keeps on incrementing, always pointing to the position where the next element will be inserted, while the front remains in the first position.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Data Structures and Program Design Using C++

  • D. Malhotra, N. Malhotra(Authors)
  • 2019(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  5

  QUEUES

  In This Chapter

  • Introduction

  • Definition of a queue

  • Implementation of a queue

  • Operations on queues

  • Types of queues

  • Applications of queues

  • Summary

  • Exercises

  5.1Introduction

  A queue is an important data structure which is widely used in many computer applications. A queue can be visualized with many examples from our day-to-day life with which we are already familiar. A very simple illustration of queue is a line of people standing outside to enter a movie theater. The first person standing in the line will enter the movie theater first. Similarly, there are many daily life examples in which we can see the queue being implemented. Hence, we observe that whenever we talk about a queue, we see that that the element at the first position will be served first. Thus, a queue can be described as a FIFO (first in, first out) data structure; that is, the element which is inserted first will be the first one to be taken out. Now, let us discuss more about queues in detail.

  5.2Definition of a Queue

  A queue is a linear collection of data elements in which the element inserted first will be the element taken out first (i.e., a queue is a FIFO data structure). A queue is an abstract data structure, somewhat similar to stacks. Unlike stacks, a queue is open on both ends.

  A queue is a linear data structure in which the first element is inserted on one end called the REAR end (also called the tail end), and the deletion of the element takes place from the other end called the FRONT end (also called the head)

  . One end is always used to insert data and the other end is used to remove data.

  Queues can be implemented by using arrays or linked lists. We will discuss the implementation of queues using arrays and linked lists in this section.

  Practical Application: •A real-life example of a queue is people moving on an escalator. The people who got on the escalator first will be the first ones to step off of it.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  A Textbook of Data Structures and Algorithms, Volume 1

  Mastering Linear Data Structures

  • G. A. Vijayalakshmi Pai(Author)
  • 2022(Publication Date)
  • Wiley-ISTE

    (Publisher)

  5 Queues In this chapter, we discuss the Queue data structure, its operations and its variants, namely, circular queues, priority queues and deques. The application of the data structure is demonstrated on the problem of job scheduling in a time-sharing system environment. 5.1. Introduction A queue is a linear list in which all insertions are made at one end of the list known as the rear or tail of the queue, and all deletions are made at the other end known as the front or head of the queue. An insertion operation is also referred to as enqueuing a queue, and a deletion operation is referred to as dequeuing a queue. Figure 5.1 illustrates a queue and its functionality. Here, Q is a queue of three elements a, b, and c (Figure 5.1(a)). When an element d is to join the queue, it is inserted at the rear end of the queue (Figure 5.1(b)), and when an element is to be deleted, the element at the front end of the queue, namely, a, is deleted automatically (Figure 5.1(c)). Thus, a Queue data structure obeys the principle of First In First Out (FIFO) or First Come First Served (FCFS). Many examples of queues occur in everyday life. Figure 5.2(a) illustrates a queue of customers waiting to be served by a clerk at the booking counter, and Figure 5.2(b) illustrates a trail of components moving down an assembly line to be processed by a robot at the end of the line. The FIFO principle of insertion at the rear end of the queue when a new client arrives or when a new component is added, and deletion at the front end of the queue when the service of the client or processing of the component is complete, is evident. 102 A Textbook of Data Structures and Algorithms 1 Figure 5.1. A queue and its functionality 5.2. Operations on queues The Queue data structure supports two operations, namely, i) insertion or addition of elements to a queue; ii) deletion or removal of elements from a queue.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures And Algorithms

  • Shi-kuo Chang(Author)
  • 2003(Publication Date)
  • World Scientific

    (Publisher)

  103 104 A. Guercio 6.2. The Concept of Queue The concept of line explains very clearly the concept of a queue. Have you ever been in line in a bank or in a super market? That line is a queue. When you enter the line you put yourself at the end of the line, the tail and the person who is at the front of the line, the head is the next who will be served as soon as the cashier is available. The person will exit the queue and will be served. The next person who will enter the line will put himself behind you and so on. In the meanwhile the queue is served and the next person at the head of the line will exit the queue and will be served. While the queue is served, you will move towards the head of the line since each person that is served will be removed from the head of the queue. You will be, then, in the middle of the line waiting patiently for all the persons in front of you to be served and will exit the line one by one in the order they entered the queue. Finally you will reach the head of the line and you will exit the queue and be served. The behavior of this line is said a first-in-first-out (FIFO) behavior, that is the person that is removed from the line is the one that entered earliest the line. This behavior is very useful, in any case the order of arrival has to be maintained. Example of queues can be seen in the everyday life, but are common in computing applications as well. For example, processes or threads may be scheduled to run on the CPU in FIFO order. These processes may be stored by the operating system using a Queue data structure. I/O requests are queued for service on a disk in a multi-user time-shared server. The I/O requests have to be served in a FIFO order. Messages are queued in a buffer in a client-server communication while waiting for the server to be available to receive the message. Summarizing, let us consider a finite set of data of type T, a queue is an abstract data type which exhibits a first-in-first-out behavior (Fig. 6.1).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Programming with C++

  • Kyla McMullen, Elizabeth Matthews, June Jamrich Parsons, , Kyla McMullen, Kyla McMullen, Elizabeth Matthews, June Jamrich Parsons(Authors)
  • 2021(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Asynchronous data transfer. Data that cannot always flow freely may be held in a buffer and then released. Keyboards include buffers that store keypresses until they can be handled by a software application. Print spool- ers hold character data until a printer is ready to receive it. Flood fill algorithms. Games such as Go and Minesweeper use queues to determine which squares are cleared. In Paint software, a queue controls the bucket tool that fills connected, similarly colored areas with a specified new color. See Figure 20-13. Figure 20-13 Flood fill algorithms are based on queues First come, first served. Applications that control commercial phone systems place callers on hold and connect them to agents on a first come, first served basis. Print queues hold a series of documents and print them out in the order that they were received. Traversal algorithms. Queues are used to follow a path through a hierarchical structure called a tree. Shortest path. A queue is a key part of the solution to mapping problems such as the classic Chess Knight Problem to find the minimum number of steps taken by the Knight to move from point A to point B on a chess- board. See Figure 20-14. Copyright 2022 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. PROGRAMMING WITH C++ 364 Code a Queue (20.2.7, 20.2.8) Although most programming languages provide a variety of built-in functionality for queues, you have the most control if you create a linked list and provide it with methods for enqueueing and dequeuing.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Fundamentals of Python

  Data Structures

  • Kenneth Lambert(Author)
  • 2018(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  A queue thus supports a first-in first-out (FIFO) protocol. Queues are omnipresent in everyday life and occur in any situation where people or things are lined up for service or processing on a first-come, first-served basis. Checkout lines in stores, highway tollbooth lines, and airport baggage check-in lines are familiar examples of queues. Queues have two fundamental operations: add, which adds an item to the rear of a queue, and pop, which removes an item from the front. Figure 8-1 shows a queue as it might appear at various stages in its lifetime. In the figure, the queue’s front is on the left, and its rear is on the right. Initially, the queue is empty. Then an item called a is added. Next, three more items called b, c, and d are added, after which an item is popped, and so forth. Figure 8-1 The states in the lifetime of a queue Copyright 2019 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 207 The Queue Interface and Its Use Related to queues is a collection called a priority queue. In a queue, the item popped, or served next, is always the item that has been waiting the longest. But in some circum- stances, this restriction is too rigid, and it’s preferable to combine the idea of waiting with a notion of priority. In a priority queue, higher-priority items are popped before those of lower priority, and items of equal priority are popped in FIFO order. Consider, for example, the manner in which passengers board an aircraft. The first-class passengers line up and board first, and the lower-priority coach-class passengers line up and board second.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  C++ Programming

  From Problem Analysis to Program Design

  • D. Malik(Author)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 1278 | Chapter 18: Stacks and Queues queues are an effective way to implement a FIFO system, queues are important data structures for use in computer simulations. This section examines computer simulations in which queues are the basic data structure. These simulations model the behavior of systems, called queuing systems, in which queues of objects are waiting to be served by various servers. In other words, a queuing system consists of servers and queues of objects waiting to be served. We deal with a variety of queuing systems on a daily basis. For example, a grocery store and a banking system are both queuing systems. Furthermore, when you send a print request to a networked printer that is shared by many people, your print request goes in a queue. Print requests that arrived before your print request are usually completed before yours. Thus, the printer acts as the server when a queue of documents is waiting to be printed. Designing a Queuing System In this section, we describe a queuing system that can be used in a variety of applications, such as a bank, grocery store, movie theater, printer, or a mainframe environment in which several people are trying to use the same processors to execute their programs. To describe a queuing system, we use the term server for the object that provides the service. For example, in a bank, a teller is a server; in a grocery store or movie theater, a cashier is a server. We will call the object receiving the service the customer, and the service time—the time it takes to serve a customer—the transaction time. Because a queuing system consists of servers and a queue of waiting objects, we will model a system that consists of a list of servers and a waiting queue holding the customers to be served. The customer at the front of the queue waits for the next available server.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Objects, Abstraction, Data Structures and Design

  Using C++

  • Elliot B. Koffman, Paul A. T. Wolfgang(Authors)
  • 2012(Publication Date)
  • Wiley

    (Publisher)

  C h a p t e r O b j e c t i v e s ◆ To learn how to represent a waiting line (queue) and how to use the functions in the Queue ADT for insertion ( push), for removal ( pop), and for accessing the element at the front ( front) ◆ To understand how to implement the Queue ADT using a single-linked list, a circular array, and a double-linked list ◆ To understand how to simulate the operation of a physical system that has one or more waiting lines using queues and random number generators ◆ To introduce the standard library deque class 357 Queues and Deques C h a p t e r 6 I n this chapter we study an abstract data type, the queue, that is widely used, like the stack, but differs from it in one important way. A stack is a LIFO (last-in, first-out) list, because the last element pushed onto a stack will be the first ele- ment popped off. A queue, on the other hand, is a FIFO (first-in, first-out) list, because the first element inserted in the queue will be the first element removed. You will learn how to use a queue to store items (for example, customers) that will be accessed on a first-come, first-served basis. We will also show you how to implement queues. You will also learn how to use simulation to estimate the amount of time customers will spend waiting in a queue. You will also learn about an abstract data type, the deque, that combines the features of a stack and a queue. We will also show you how to implement a deque. 6.1 The Queue Abstract Data Type The easiest way to visualize a queue is to think of a line of customers waiting for service, as shown in Figure 6.1. Usually, the next person to be served is the one who has been waiting the longest, and latecomers are added to the end of the line. The Queue ADT gets its name from the fact that such a waiting line is called a queue in English-speaking countries other than the United States. A Queue of Customers A queue of three customers waiting to buy concert tickets is shown in Figure 6.2.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Open Data Structures

  • Pat Morin(Author)
  • 2013(Publication Date)
  • AU Press

    (Publisher)

  The Queue ’s queue-ing discipline decides which element should be removed. There are many possible queueing disciplines, the most common of which include FIFO, priority, and LIFO. A FIFO (first-in-first-out) Queue , which is illustrated in Figure 1.1 , re-moves items in the same order they were added, much in the same way a queue (or line-up) works when checking out at a cash register in a gro-cery store. This is the most common kind of Queue so the qualifier FIFO is often omitted. In other texts, the add ( x ) and remove () operations on a FIFO Queue are often called enqueue ( x ) and dequeue (), respectively. A priority Queue , illustrated in Figure 1.2 , always removes the small-est element from the Queue , breaking ties arbitrarily. This is similar to the way in which patients are triaged in a hospital emergency room. As pa-tients arrive they are evaluated and then placed in a waiting room. When a doctor becomes available he or she first treats the patient with the most life-threatening condition. The remove ( x ) operation on a priority Queue is usually called deleteMin () in other texts. A very common queueing discipline is the LIFO (last-in-first-out) dis-cipline, illustrated in Figure 1.3 . In a LIFO Queue , the most recently added element is the next one removed. This is best visualized in terms of a stack of plates; plates are placed on the top of the stack and also 5 §1.2 Introduction 16 add ( x ) remove ()/ deleteMin () x 6 13 3 Figure 1.2: A priority Queue . ··· remove ()/ pop () add ( x )/ push ( x ) x Figure 1.3: A stack. removed from the top of the stack. This structure is so common that it gets its own name: Stack . Often, when discussing a Stack , the names of add ( x ) and remove () are changed to push ( x ) and pop (); this is to avoid confusing the LIFO and FIFO queueing disciplines. A Deque is a generalization of both the FIFO Queue and LIFO Queue ( Stack ). A Deque represents a sequence of elements, with a front and a back.

  Sign up to read

  Learn more about book