10.4 DataTypes&Structures.abstract_data_types

Question 1

How is a stack implemented?

Answer 1

A stack can be implemented using an array and a set of pointers. The stack has a finite size, and conditions for full and empty states must be handled.

Question 2

What remains constant during stack operations (push and pop)?

Answer 2

The value of the basePointer remains constant during stack operations.

Question 3

What are the declarations to set up a stack in pseudocode?

Answer 3

DECLARE stack ARRAY[1:10] OF INTEGER  
DECLARE topPointer : INTEGER  
DECLARE basePointer : INTEGER  
DECLARE stackful : INTEGER  
basePointer ← 1  
topPointer ← 0  
stackful ← 10

Question 4

What is the pseudocode to push an item onto a stack?

Answer 4

IF topPointer < stackful  
    THEN  
        topPointer ← topPointer + 1  
        stack[topPointer] ← item  
    ELSE  
        OUTPUT "Stack is full, cannot push"  
ENDIF  

Question 5

What is the pseudocode to pop an item from a stack?

Answer 5

IF topPointer = basePointer - 1  
    THEN  
        OUTPUT "Stack is empty, cannot pop"  
    ELSE  
        item ← stack[topPointer]  
        topPointer ← topPointer - 1  
ENDIF 

Question 6

What changes after enqueue and dequeue in a queue?

Answer 6

• rearPointer changes after enqueue.
• frontPointer changes after dequeue.

Question 7

How is a queue implemented and managed?

Answer 7

A queue can be implemented using an array with pointers for front and rear. It is managed as a circular queue to prevent repositioning items when the queue reaches the array’s bounds.

Question 8

What are the declarations to set up a queue in pseudocode?

Answer 8

DECLARE queue ARRAY[1:10] OF INTEGER  
DECLARE rearPointer : INTEGER  
DECLARE frontPointer : INTEGER  
DECLARE queueful : INTEGER  
DECLARE queueLength : INTEGER  
frontPointer ← 1  
rearPointer ← 0  
upperBound ← 10  
queueful ← 10  
queueLength ← 0  

Question 9

What is the pseudocode to enqueue an item into a queue?

Answer 9

IF queueLength < queueful  
    THEN  
        IF rearPointer < upperBound  
            THEN  
                rearPointer ← rearPointer + 1  
            ELSE  
                rearPointer ← 1  
        ENDIF  
        queueLength ← queueLength + 1  
        queue[rearPointer] ← item  
    ELSE  
        OUTPUT "Queue is full, cannot enqueue"  
ENDIF 

Question 10

What is the pseudocode to dequeue an item from a queue?

Answer 10

IF queueLength = 0  
    THEN  
        OUTPUT "Queue is empty, cannot dequeue"  
    ELSE  
        item ← queue[frontPointer]  
        IF frontPointer = upperBound  
            THEN  
                frontPointer ← 1  
            ELSE  
                frontPointer ← frontPointer + 1  
        ENDIF  
        queueLength ← queueLength - 1  
ENDIF

Question 11

How can a linked list be implemented in programming?

Answer 11

A linked list can be implemented using two 1D arrays:

1. One for storing items in the linked list.
2. One for storing pointers to the next item in the list.

Question 12

What must be managed when implementing a linked list in arrays?

Answer 12

• The possibility of the linked list becoming full.
• Empty positions in the array, represented as an empty linked list (the heap).

Question 13

What is the purpose of the heap in a linked list?

Answer 13

The heap is a linked list of all available spaces in the array, used to manage empty positions after items are removed.

Question 14

What is the pseudocode to declare and initialise a linked list?

Answer 14

DECLARE myLinkedList ARRAY[0:11] OF INTEGER  
DECLARE myLinkedListPointers ARRAY[0:11] OF INTEGER  
DECLARE startPointer : INTEGER  
DECLARE heapStartPointer : INTEGER  
DECLARE index : INTEGER  

heapStartPointer ← 0  
startPointer ← –1 // List is empty  

FOR index ← 0 TO 11  
    myLinkedListPointers[index] ← index + 1  
NEXT index  

myLinkedListPointers[11] ← –1 // Final heap pointer set to –1  

Identifier table:
myLinkedList: Linked list to be searched.
myLinkedListPointers: Pointers for the linked list.
startPointer: Start of the linked list.
heapStartPointer: Start of the heap.
index: Pointer to the current element in the linked list.

Question 15

What does the final pointer in the heap signify when initialising a linked list?

Answer 15

It is set to –1 to indicate there are no further links in the heap.