Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
2.4.1 First-In, First-OutA queue is a linear data structure that utilizes a first-in, first-out element insertion and removal policy. First-in, first-out means that the first element added to a queue is the first element removed from a queue. Put another way, things are only removed from the beginning and only added to the end of queues. Queues are used in the real world in many places. Remember from 1.2.1 What are Data Structures and Algorithms we discussed a line at a movie theater as a data structure. This line is really just a queue. People enter the line at the back and leave the line only when they reach the front and buy their tickets. Airplanes waiting to land and take off from an airport also wait in queues. Anywhere a "First Come, First Served" sign is seen, a queue is at work. Queues have many different applications in computer science and software development. A queue can be used to provide a buffer. A buffer provides temporary storage for information that needs to be processed later. Network routers buffer incoming data packets in a queue to give the routers time to process outgoing packets. Operating systems can use a queue to implement a scheduling policy that decides which program to run next. Applications that stream audio and video across the Internet buffer a certain number of packets in a queue to account for temporary slow downs in connection speeds. queue Adapter The Standard Template Library contains adapters that provide a new, but similar interface to an existing container. The queue adapter provides the interface suitable for a queue data structure. It is based, by default, on the deque container. When an object of type queue is used, an object of type deque is actually instantiated, just with an interface more suitable for a queue. Listing 1 illustrates the entire, small interface of the queue adapter. |
2.4.1 Первый вошел, первый вышел (FIFO).Очередь является линейной структурой данных, которая использует схему first-in, first-out. First-in, first-out означает, что первый элемент, добавленный в очередь, является первым элементом, удаляющийся из очереди. Другими словами, элементы могут только удаляться с начала и добавляться только в конец очереди. В 1.2.1 мы обсуждали очередь в кинотеатре как структуру данных. Эта очередь является действительно только очередью. Люди входят в очередь сзади и выходят из нее только, когда они доходят до начала ее и покупают билеты. Самолеты, ожидающие, чтобы приземлиться и взлететь из/в аэропорт также, ожидают своей очереди. Где угодно если наблюдается "First Come, First Served", то можно утверждать - работает очередь. У очередей есть много различных приложений в информатике и разработке программного обеспечения. Queue может использоваться как буфер. Буфер обеспечивает временное хранилище информации, которая должна быть обработана позже. Сетевой буфер маршрутизаторов ставит входящие пакеты данных в очереди, чтобы дать время маршрутизаторам обработать исходящие пакеты. Операционные системы могут использовать очередь, чтобы реализовать политику планирования. Потоковые аудио и видео через Интернет буферизуют определенное число пакетов в очереди, чтобы учесть временные задержки в скоростях соединения. Адаптер queue (очереди) STL содержит адаптеры, которые обеспечивают интерфейс для существующего контейнера. Адаптер queue обеспечивает подходящий интерфейс для структуры данных queue и базируется, по умолчанию, в контейнере deque. Когда объект типа queue использует объект типа deque фактически дистанцируются интерфейсом, более подходящим для очереди. Листинг 1 иллюстрирует интерфейс адаптера queue. |
||||||||||||||
|
|||||||||||||||
|
Only six member functions exist in the queue adapter interface. Methods push and pop insert and remove elements from a queue, and methods front and back provide access to the data stored in the beginning and end of a queue. Similar to the other STL containers we have examined, method size returns the number of elements stored in a queue and method empty returns true if a queue is empty and false if a queue is storing at least one element. Notice from line 4 in the above listing that inclusion of the <queue> library is necessary to use the queue adapter. One thing that the queue adapter lacks is support for iterators. Without iterators, a method to traverse the elements stored in a queue does not exist. Essentially, a queue hides all the elements it stores except for the first and last. If an application requires a queue, but also requires access to the elements stored in the queue, a deque should be used instead. Table 1 shows the member functions of class queue and their deque equivalents.
2.5.1 Last-In, First-Out Stacks Introduced A stack is a linear data structure that provides access to only the most recently added element. In a stack, items can only be added at and removed from one end of the sequence. This amounts to a "Last-in, First-Out" element insertion and removal policy. Put another way, the next item that can be removed from a stack is always the element that was most recently added to the stack. We can always add more elements to a stack, but each time we do, the newly added element becomes the element that can be removed first. A stack of plates or dishes in a kitchen is a real world example of a stack data structure. Consider how one uses a stack of plates. When a plate is needed for dining, one is taken from the top of the stack of plates. It is not a good idea to try to take a plate from the bottom, since this probably would topple the entire stack. When plates are put away, they are placed on top of the stack. Because we only take plates from the top, a plate placed on top of the stack becomes the next plate that we use. Real world examples like the stack of plates make it is easy to think of a stack as a vertical structure. With this mental model in mind, let's step through adding a few elements to an initially empty stack. First we add (typically referred to as "pushing" onto the stack) an element with the value 1. Figure 1 represents our stack with this lone element.
Things become more interesting after we push a second element onto the stack. Figure 2 shows the state of the stack after we add an element with the value 2.
The element shaded in gray is now at the top of the stack. Adding this second element effectively hides the first element since the second element is now the only element that can be removed. Also, it is the only element in the stack whose value we can access. This is an important property of the stack data structure that differs from vectors and deques. In a stack, we have access to the number of elements stored in the data structure, but we do not have access to all the values of the elements. We can "peek" into the stack to return the value of the element that sits at the top. A peek operation performed on the stack in Figure 2 would return the value 2.
Figure 3 shows the stack after we push a third element onto the stack. The element added contains the value 3. If we were to remove an element from the stack (often referred to as "popping" an element), our stack would then look like Figure 2. We have examined how stacks operate and have seen the primary operations associated with stacks. Summarizing, "pushing" adds an element to the top of a stack, "popping" removes the element at the top of a stack, and "peeking" returns the value of the element at the top of a stack. Applications of Stacks An important data structure in Computer Science, stacks have many different applications. These applications range from simple tasks such as reversing the characters in a string to seemingly more complex tasks such as the evaluation of arithmetic expressions or the navigation of mazes. It is important to gain a solid understanding of the concept of a stack since later in this course we encounter many uses of stacks in the context of other data structures and algorithms. 2.5.2 Using the STL stack Adapter The STL stack adapter provides an interface suitable for use as a stack. Listing 1 demonstrates all the member functions of the stack adapter. |
Существуют шесть функций- членов работающих с интерфейсом адаптера queue. Методы push и pop, вставляют и удаляют элементы из очереди, обеспечивают доступ к данным, хранившимся в начале и конце очереди. Подобный другим контейнерам STL, метод size возвращает число элементов, сохраненное в очереди и методе empty возвратившее true, если очередь пуста. И false, если очередь хранит по крайней мере один элемент. В строке 4 в вышеупомянутом перечислении, включена библиотека <queue>, чтобы использовать адаптер queue. Недостатком адаптера queue, является использование iterators. Только посредством iterators адаптер queue может пройти все элементы, сохраненные в queue. По существу, queue скрывает все элементы, которые она хранит за исключением первого и последнего. Если приложение требует queue, но также и требует доступа к элементам, сохраненным в очереди, лучше использовать deque вместо queue. Таблица 1 показывает функции-членов класса queue и их эквиваленты в deque. 2.5.1 Последний вошел, первый вышел Представление стеков Стек является линейной структурой данных, которая обеспечивает доступ к только последнему добавленному элементу. В стеке последовательности элементы могут быть добавлены и удалены только с одного конца. Т.е. политика вставки и удаления элементов - "Last-in, First-Out". Другими словами, следующий элемент, который может быть удален из стека, всегда является элементом, который был последним добавлен в стек. Мы можем добавлять элементы в стек, но каждый раз, когда мы удаляем, всегда удаляем только что добавленный элемент, и только он может быть удален первым. Стопка подносов или тарелок на кухне является примером реального мира структуры данных стека. Рассмотрим, как используются стек подносов. Когда подносы необходимы, все берут их сверху стека. Опасно попытаться взять поднос с нижней части, так как это, вероятно, свалило бы весь стек. Когда подносы складываются, они размещаются сверху стека. Поскольку мы только берем пластины сверху, поднос, помещенный сверху стека, становится тем подносом, который может быть использован. Примеры реального мира как стек подносов позволяют легко представлять стеке как о вертикальной структуре. Давайте рассмотрим процесс добавления нескольких элементов в первоначально пустой стек. Сначала мы добавляем ("pushing") элемент со значением 1. Рисунок 1 представляет наш стек с этим единственным элементом.
Далее, положим второй элемент на стек. Рисунок 2 показывает состояние стека после того, как мы добавили элемент со значением 2.
Элемент, закрашенный в серый цвет теперь сверху стека. Добавление второго элемента полностью скрывает первый элемент, т.к. второй элемент является теперь единственным элементом, который может быть удален. Кроме того, он единственный элемент в стеке, к которому можно получить доступ. Это важное свойство структуры данных стека, которое отличает ее от векторов и двухсторонних очередей. В стеке есть доступ к числу элементов сохраненных в структуре данных, но нет доступ к их значениям. Мы можем "посмотреть" в стек и возвратить значение элемента только находящегося сверху. A peek operation performed, выполняемая на стеке в рисунке 2, возвратила бы значение 2.
Рисунок 3 показывает стек после третьего элемента. Добавленный элемент содержит значение 3. Если мы должны были удалить (popping) элемент из стека, то стек примет вид на рисунок 2. Мы рассмотрели как управлять стеками, увидели и опробовали основные операции, связанные со стеками. Суммирование, "pushing" добавляет элемент к вершине стека, "popping" удаляет элемент наверху стека, и "peeking" возвращает значение элемента находящегося сверху стека. Приложения Стеков Важно: у стеков есть много различных приложений. Эти приложения используются в простых задач, таких как инвертирование символов в строке и в более сложных, в таких как оценка арифметических выражений или навигация лабиринтов. Важно сейчас получить основательное понимание понятия стека т.к. позже в этом курсе, мы встретимся со многим использованием стеков в контексте других структур данных и алгоритмов. 2.5.2 Использование STL stack Adapter Адаптер стека STL обеспечивает интерфейс, подходящий для использования в качестве стека. Листинг 1 демонстрирует все функции-члены адаптера стека. |
||||||||||||||
|
|||||||||||||||
|
Only six member functions exist in the stack adapter interface. Methods push and pop insert and remove elements from a stack respectively, and method top returns a reference to the data stored at the top of the stack. As with the queue adapter, method size returns the number of elements stored in a stack and method empty returns true if a stack is empty and false if a stack is not empty. To use the STL stack adapter in a program, a programmer must include the <stack> library. This is done in line 4 of Listing 1. Listing 2 shows a more practical example of the stack adapter. This listing displays the lines of a text file in reverse order. A stack provides a natural data structure to solve this problem. |
Существуют шесть функций-членов работающих с интерфейсом адаптера стека. Методы push and pop, вставляют и удаляют элементы из стека соответственно, метод top возвращает ссылку на данные, хранившие наверху стека. Как с адаптером queue, метод size возвращает число элементов, сохраненное в стеке и метод empty возвращает true, если стек пуст и false, если стек не пуст. Чтобы использовать адаптер стека STL в программе, программист должен включать библиотеку <stack>. Это показано в строке 4 из Листинг 1. Листинг 2 показывает более практический пример адаптера стека. Это перечисление выводит на экран строки текстового файла в обратном порядке. Стек обеспечивает естественную структуру данных, чтобы решить эту проблему. |
||||||||||||||
|