12.5.2.1 describe the operation of stack and queue data structures

Data structures: Queue and Stack

Data Structure is particular way of organising data in programs. 

Queue

A queue is a abstract data structure that operates on a first-in-first-out basis.

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

• Print queue. If several documents were sent to print, then the one that was sent first will be printed first. Until the first document is printed, the second will not start printing.
• Keyboard Buffer - The letters on the screen appear in the order in which you press them.
• Handling of interrupts in real-time systems. 

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:

• enQueue(item) - Add a new item to the rear of the queue
• deQueue() - Remove the front item from the queue and return it
• isEmpty() - Test to see whether the queue is empty
• is Full - Test to see whether the queue is full

Stack

A stack is a Last In, First Out (LIFO) data structure.

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

• The simplest application of a stack is to reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack.
• When you use the Back button in your web browser, you will be taken back through the previous pages that you looked at, in reverse orderas their URLs are removed from the stack and reloaded.
• When you use the Undo button in a word processing package, the last operation you carried out is popped from the stack and undone.

Stacks have several uses:

• Reversing queues
• CPU task scheduling
• Performing Reverse Polish Calculations
• Holding return addresses and system states for recursive function calls
• Parsing
• Expression Conversion(Infix to Postfix, Postfix to Prefix etc)
• TCP/IP stack

Operations on a stack

The following operations are required to implement a stack:

• push(item) - adds a new item to the top of the stack
• pop() - removes and returns the top item from the stack
• peek() - returns the top item from the stack but does not remove it
• isEmpty() - tests to see whether the stack is empty, and returns a Boolean value
• isFull() - tests to see whether the stack is full, and returns a Boolean value

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: