topic: data structures, queues and stacks

Question 1

what is a queue

Answer 1

a linear data structur that follows the First-In-First-Out (FIFO) principle, where the first element added is the first one to be removed

Question 2

how do you add and remove from a queue

Answer 2

items are enqueued at the back of the queue (added)
dequeued from the front (this removes and returns that item)

Question 3

How are stacks implemented in code?(3)

Answer 3

• Using a procedural approach
• Using built in functionality from libraries(reusable programming components) - Use the built in stack class provided by your programming language’s standard libraries or from an external library
• Using an object oriented approach

Question 4

Write pseudocode to declare an array of size 10 and a stack pointer initially of 0.
Write a push procedure

Answer 4

array stackItems[10]
stackPointer = 0
procedure push(item)
if stackPointer == 10 then
print (“Stack is full!”)
else
stackItems[stackPointer] = item
stackPointer++
end if
end procedure

Question 5

Write pseudocode to declare an array of size 10 and a stack pointer initially of 0
Write a pop function

Answer 5

array stackItems[10]
stackPointer = 0
function pop()
if stackPointer == 0 then
print (“Stack is empty!”)
return null
else
stackPointer- -
return stackItems[stackPointer]
end if
end function

Question 6

what are 5 features of stacks

Answer 6

1. stacks are like a stack of plates, the last item put on, is the first one to be removed (last in first out – LIFO)
2. in procedural languages, a stack uses a single pointer to the top of the stack.
3. you can add items (push) and remove items (pop) to/from stacks.
4. stacks can be used for - Back/Forward button on browsers, PC value is added to stack before an Interrupt Service Routine is invoked, recursion (a routine that calls itself), undo operations.
5. stacks can be implemented using arrays or lists

Question 7

Using pseudocode, write an algorithm that allows the user to enter a name which is then pushed onto a stack data structure, checking first that the data structure is not full
use the variable wNames and 2 others

Answer 7

new = input(“enter a name : “)
if top <=5 then
    top = top + 1
    wNames[top] = new
end if

Question 8

A user enters whole numbers into a computer program. Each number entered is placed onto a
stack. The stack is created using an array with a maximum of 20 elements.
The function addItem is written but is incomplete.
Complete the function, addItem.

function addItem (number)
if top == …………………………………… then
return false
else
numStack[……………………………………] = ………………………………
top = …………………………………… + 1
…………………………………………………………………………
endif
endfunction

Answer 8

function addItem (number)
if top = ‘20’ then
return false
else
numStack[‘top’] = ‘number’
top = ‘top’ + 1
‘return true’
endif
endfunction

Question 9

A stack, in shared memory, is being used to pass a single variable length ASCII string
between two sub-systems. The string is placed in the stack one character at a time in reverse
order with the last byte holding the number of characters pushed i.e the text “SILVER” would
be held in the stack as:

6 Top
S
I
L
V
E
R

Use pseudocode to write a procedure that will take a text string passed to it and push it to the
stack in the format defined above. You may assume any given input will fit in the stack.

Answer 9

procedure passToStack(passString)
stringLen = passString.Length()
if stringLen == 0 then
stack[0]=0
else
stackPtr = 0
stringPtr = stringLen - 1
for i = 1 TO stringLen
stack[stackPtr] =
passString[stringPtr]
stackPtr = stackPtr + 1
stringPtr = stringPtr -1
next i
stack[stackPtr] = stringLen
endif
endprocedure

Question 10

The enqueue method:
* takes as a parameter the item to insert in the queue
* checks if the queue is full
* reports an error and returns false if the queue is full
* does the following if the queue is not full:
o adds the item to the array at the tail position and adjusts the pointer(s)
o returns true
The attribute numItems stores the number of items currently in the queue.
Write an algorithm, using pseudocode or program code, for the enqueue method.

Answer 10

public function enqueue(newItem : items) : boolean
if numItems = 10 then
print(“Error: The queue is full”)
return false
else
theItems[tail] = newItem
if tail = 9 then
tail = 0
else
tail += 1
endif
numItems += 1
return true
endif
endfunction

Question 11

Write a programming statement to declare an instance of itemQueue called myItems

Answer 11

myItems = (new) itemQueue()

Question 12

Write a procedure, insertItems(), to ask the user to input the data for an item. The
item is then added to the queue myItems. The user is continually asked to input data
items until the queue is full.

Answer 12

procedure insertItems()
newItem : Items
itemCount = myItems.getnumItems()
while itemCount < 10
newItem.itemName = input(“Enter the item name”)
newItem.cost = input(“Enter the item cost”)
newItem.dateArrival = input(“Enter the date of arrival”)
newItem.transferred = input(“Has it been transferred?”)
myItems.enqueue(newItem)
itemCount = itemCount + 1
endwhile
myItems.setnumItems(itemCount)
endprocedure

Question 13

When the main program ends, the items and the queue no longer exist.
Describe how Kamran could amend the program to make sure the items and queue still
exist and are used the next time the program is run.

Answer 13

• Store the items and queue to an external file (when the program closes)
• Load the items and queue from the file when it starts

Question 14

go to question 7c using this link
https://drive.google.com/file/d/16ne5XXRiSE2PsB07MlbFH9y5UY8Qvyoh/view

Answer 14

how did u do
answers:
https://drive.google.com/file/d/1BdwZeoZdx9yhCFE8o8EeYy_0UDSwFSh8/view