12.5.2.1 describe the operation of stack and queue data structures Data structures: Queue and Stack
Queue
A queue is First In, First Out (FIFO) data structure. New elements may only be added to the end of a queue, and elements may only be retrieved from the front of a queue. The size of the queue depends on the numbers of items in it. Can only add to back and remove from front. A real life example of this would be queuing to pay at the supermarket, . The first person into the queue is the first person to be served. And if you join the queue last you are going to be served last (no pushing!). Other examples, traffic lights, call center phone systems use queues to hold people calling them in order. Application of queue
Advantage: Fast to implement, simple code Disadvantages: Removing items from the front of the queue can be slow Operation on a queue The following queue operations are needed:
Stack
This means that, like a stack of plates in a cafeteria, items are added to the top and removed from the top. Application of stacks
Stacks have several uses:
Operations on a stack The following operations are required to implement a stack:
Questions: Exercises: Ex. 1 Fill the list items of Queue (without spaces) Ex. 2 Fill the list items of Stack (without spaces) Ex. 3 Задача. Правильная скобочная последовательность. Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна определить, является ли данная скобочная последовательность правильной. Пустая последовательность явлется правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная. Входные данные В единственной строке записана скобочная последовательность, содержащая не более 100000 скобок. Выходные данные Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no. Пример Входные данные: ()[] Выходные данные: yes Ex. 4 Задача. Постфиксная запись В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает привычное нам (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения. Входные данные В единственной строке записано выражение в постфиксной записи, содержащее цифры и операции +, -, *. Числа и операции разделяются пробелами. В конце строки может быть произвольное количество пробелов. Выходные данные Необходимо вывести значение записанного выражения. Пример Входные данные: 8 9 + 1 7 - * Выходные данные: -102 Exam questions:
| |||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||
Просмотров: 60 | | |
Всего комментариев: 0 | |
|
|