12.5.2.1 describe the operation of stack and queue data structures
Definition
Data Structure is a particular way of organising data in programs.
I. Queue
A queue is an 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 number of items in it.
Can only add to the back and remove from the front.
A real-life example of this would be queuing to pay at the supermarket. The first person in the queue is the first person to be served. And if you join the queue last you will be served last (no pushing!).
Other examples are traffic lights and call center phone systems that use queues to hold people calling them in order.
Application of queue
Print queue. If several documents were sent to print, the one 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 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
Queue operation
php
Queue content
Return value
queue.isEmpty()
if (count($queue) == 0)
[]
True
queue.enQueue()
$queue[] = 3;
$queue[] = 5;
$queue[] = 12;
[3]
[3, 5]
[3, 5, 12]
queue.isEmpty()
if (count($queue) == 0)
[3, 5, 12]
False
queue.deQueue()
array_shift($queue);
[5, 12]
3
queue.enQueue()
$queue[] = 4;
[5, 12, 4]
II. 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 order 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:
Web browsers use stacks to manage the navigation history of visited web pages. When a user navigates to a new page, the URL of the current page is pushed onto a stack. This allows users to navigate back to previous pages using the browser's back button, which pops URLs off the stack.
Graphics software, such as image editors or drawing applications, often implement undo and redofunctionality using stacks. Each action performed by the user, such as drawing a line or applying a filter, is pushed onto a stack. The user can then undo or redo actions by popping them off the undo stack and pushing them onto the redo stack, and vice versa.
Function calls and recursion. In programming languages, function calls and recursion heavily rely on stacks. When a function is called, its parameters and return address are pushed onto the call stack. As functions return, they are popped off the stack, allowing the program to resume execution from the calling function. Recursion, in particular, relies on the stack to manage the nested function calls.
Performing reverse Polish calculations and expression conversion(Infix to Postfix, Postfix to Prefix, etc)
Parsing. During parsing, a stack is used to keep track of the current state of the parsing process and to store intermediate results.
TCP/IP stack. Each layer of the TCP/IP stack interacts with the layer above and below it, similar to how elements are pushed onto and popped off a 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
Stack operation
php
Stack content
Return value
stack.isEmpty()
if (count($stack) == 0)
[]
True
stack.push()
array_push($stack, 3);
array_push($stack, 5);
[3]
[3, 5]
stack.isEmpty()
if (count($stack) == 0)
[3, 5]
False
stack.peek()
$stack[count($stack)-1]
[3, 5]
5
stack.pop()
array_pop($stack);
[3]
5
Questions:
Define a Queue data structure and explain its fundamental properties.
Define a Stack data structure and explain its fundamental properties.
How does a Queue differ from a Stack?
How is a Queue implemented using arrays? What are the advantages and disadvantages of this implementation?
Discuss the implementation of a Stack using linked lists. What are the advantages and disadvantages of this implementation compared to the array-based implementation?
Can you describe a real-world scenario where a Queue data structure would be useful?
Discuss the applications of Stacks in computer science and software engineering.
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. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.
Входные данные
В единственной строке записано выражение в постфиксной записи, содержащее цифры и операции +, -, *. Числа и операции разделяются пробелами. В конце строки может быть произвольное количество пробелов.
Выходные данные
Необходимо вывести значение записанного выражения.
