Lecture Data structures and other objects using C++ - Chapter 8: Using a queue. This chapter introduces the queue data type. Several example applications of queues are given in that chapter. This presentation describes the queue operations and two ways to implement a queue. | Chapter 8 introduces the queue data type. Several example applications of queues are given in that chapter. This presentation describes the queue operations and two ways to implement a queue. Using a Queue Data Structures and Other Objects Using C++ This lecture introduces queues. The presentation also shows two common ways of implementing a queue of integers. The Queue Operations A queue is like a line of people waiting for a bank teller. The queue has a front and a rear. $ $ Front Rear When you think of a computer science queue, you can imagine a line of people waiting for a teller in a bank. The line has a front (the next person to be served) and a rear (the last person to arrive. The Queue Operations New people must enter the queue at the rear. The C++ queue class calls this a push, although it is usually called an enqueue operation. $ $ Front Rear Don’t ask me why the C++ STL used the name push. It only confuses matters with a stack. In any case, when a new item enters a queue, it does so at the rear. The Queue Operations When an item is taken from the queue, it always comes from the front. The C++ queue calls this a pop, although it is usually called a dequeue operation. $ $ Front Rear When an item is removed from a queue, the removal occurs at the front. The Queue Class The C++ standard template library has a queue template class. The template parameter is the type of the items that can be put in the queue. template class queue { public: queue( ); void push(const Item& entry); void pop( ); bool empty( ) const; Item front( ) const; }; These are the four most common queue operations. The empty function tells you whether the queue has any items at the moment. The front operation returns the item at the front of the queue (without removing it from the queue). Array Implementation A queue can be implemented with an array, as shown here. For example, this queue contains the integers 4 (at the front), 8 and 6 (at the rear). [ 0 ] [1] [ 2 ] [ 3 | Chapter 8 introduces the queue data type. Several example applications of queues are given in that chapter. This presentation describes the queue operations and two ways to implement a queue. Using a Queue Data Structures and Other Objects Using C++ This lecture introduces queues. The presentation also shows two common ways of implementing a queue of integers. The Queue Operations A queue is like a line of people waiting for a bank teller. The queue has a front and a rear. $ $ Front Rear When you think of a computer science queue, you can imagine a line of people waiting for a teller in a bank. The line has a front (the next person to be served) and a rear (the last person to arrive. The Queue Operations New people must enter the queue at the rear. The C++ queue class calls this a push, although it is usually called an enqueue operation. $ $ Front Rear Don’t ask me why the C++ STL used the name push. It only confuses matters with a stack. In any case, when a new item enters a queue, .
