Stacks & queues

A program is designed to use a stack data structure.

The current contents of part of the stack and its current pointer value are shown:

pointer = 2

Show the contents of the stack and its pointer value after the data items "t" and "s" are inserted in the order given.

The stack is stored using a 0-based 1-dimensional array called theStack with 20 elements.

The function push() stores its parameter into the next space in the stack if it is not full. The function returns true if it is successfully stored and returns false if the stack is full.

Complete the function push() using pseudocode or program code.

A pointer value of-1 indicates that the stack is empty.

The function pop() returns the next element in the stack. If the stack is empty it returns "false". The function updates the pointer value when appropriate.

Write the function pop() using pseudocode or program code.

A program is designed to reverse a set of data using the stack.

The main program takes 10 characters separately as input from the user and uses the function push() to insert these into the stack.

Once all 10 characters have been inserted into the stack, the program then uses the function pop() to output all 10 characters from the stack.

Write the main program to achieve this using pseudocode or program code.

State the purpose of headPointer and tailPointer in the queue shown in Fig. 4.

The queue is used to store ID numbers of jobs that a program needs to process. Some jobs will be given a priority which means they need to be processed first.

Explain why this queue is not a suitable data structure for this program.

The contents of a stack are stored in the 1-dimensional array called numbers.

topStack stores the index of the next free space in the stack.

The array is declared with space for 100 elements.

The function pop() returns the next item from the stack and updates the appropriate pointers.

Describe the steps in the function pop().

The function push() inserts its parameter called dataValue onto the stack and updates the appropriate pointers.

Complete the function push() using pseudocode or program code.

Write an algorithm, using pseudocode or program code, to call the function push() with the value 15 and output a message saying "Added" if the value was successfully inserted onto the stack or "Not Added" if the stack is full.

Sundip writes an algorithm to carry out addition and subtraction. The algorithm will use an initially empty stack with the identifier numbers and will take input from the user.

The action the algorithm takes depends on the value input by the user. These actions are listed in

Complete the pseudocode here to implement Sundip’s algorithm.

Complete the following table to give the output from this algorithm when the following set of inputs are entered by the user. The letters will complete an action stated in Fig. 2

If the user enters 4 2 S A E, the algorithm will not work correctly.

Explain what problem this input data will cause and why the problem occurs.

A stack is one data structure that is available for Sundip to use. She could also use a queue, list, linked list, array or tuple.

Describe one difference between a stack and a queue.

Describe one difference between an array and a list.

State how a tuple is different to a list.

Describe how the second item in a linked list would be accessed using pointer values.

A computer uses a stack data structure, implemented using an array, to store numbers entered by the user.

The array is zero based and has 100 locations.

State the purpose of pointerValue.

The stack is programmed as an object using object-oriented programming. The design for the class, its attributes and methods are shown:

The method pop() returns the next value in the stack, or –1 if the stack is empty.

Complete the pseudocode method pop().

The method push() accepts an integer as a parameter and adds it to the top of the stack unless the stack is already full.

If the push is successful the method returns true.

If the push is unsuccessful due to the stack being full the method returns false.

Write the method push() using either pseudocode or program code.

The main program initialises a new object of type stack with the identifier mathsStack

Write pseudocode or program code to declare the object.

The main program needs to:

• take numbers as input from the user

• push them onto the stack mathsStack until the stack is full

• output an appropriate message if the stack is full.

Complete the pseudocode algorithm to meet these requirements.

The main program also needs to:

• remove one item from the stack at a time and add this to a total

• output the total every time an item is removed

• stop removing items when either the stack is empty, or 20 items have been removed.

Write pseudocode or program code to meet these requirements.

The program is amended to include the use of several queue data structures.

Describe how an array can be used to implement a queue data structure.

* Discuss the use of object-oriented programming and procedural programming to create and manipulate the queue data structures.

You should include the following in your answer:

• the features of object-oriented programming

• the features of procedural programming

• the benefits of using object-oriented instead of procedural programming when creating several queue structures.

A business uses an array with the identifier wNames to store workers’ names. A variable with the identifier top is used to store the index of the last element to be added to the array, which is also the element which will next be removed.

State the name of the type of data structure described above.

Using pseudocode, write an algorithm that allows the user to enter a name which is then pushed onto the data structure above, checking first that the data structure is not full.

The same workers’ names are stored in a binary search tree which is ordered alphabetically.

Kirstie is set as the root node, with Martyn, Louise, Alex and Anna added one by one.

Complete the tree diagram above to show where Martyn, Louise, Alex and Anna would

be added to this binary search tree.

Describe the process of using the binary search tree above to search for the name “Zoe”.

Compare the efficiency of a binary search tree to a linked list when searching for data.

Compare the efficiency of a binary search tree to a hash table when searching for data.

An object oriented system is implemented to organise further information about each worker’s attendance. Classes, objects, methods and attributes are used in this system.

State the meaning of each of the following terms:

Object........

Method........

Attribute........

Each worker has a name and an attendance figure which can be between 0 and 100.

Write a definition for a fully encapsulated customer class, providing both get and set methods for all attributes. You do not have to write code for the constructor method.

Lucas writes a program that makes use of a circular queue. The queue stores the data entered into the program. An array is used to represent the queue.

The program needs two pointers to access and manipulate the data in the queue.

State the purpose of the two pointers and give an appropriate identifier for each.

Pointer 1 purpose........

Pointer 1 identifier........

Pointer 2 purpose........

Pointer 2 identifier........

Lucas wants a procedure, enqueue(), that will add the parameter it is passed to the queue.

Describe the steps the procedure enqueue() will follow when adding new items to the queue.

A printer buffer is a storage area that holds the data, known as jobs, that are to be printed by a printer.

A simulation of the printer buffer uses a queue data structure to store jobs that are waiting to be printed. The queue is not circular.

The printer buffer is represented as a zero-indexed 1D array with the identifier buffer.

Fig. 2 shows the current contents of the queue buffer and its pointers.

State the purpose of the pointers queueHead and queueTail.

The array, buffer and pointer values are declared with global scope.

The function dequeue returns null if the array is empty, and the contents of the next element if not empty. The queue is not circular.

Write an algorithm, using pseudocode or program code, for the function dequeue()

The function enqueue returns-1 if there is no space at the end of the queue to add data, and returns 1 if the parameter was added to buffer. The array buffer contains a maximum of 100 elements.

Write an algorithm, using pseudocode or program code, for the function enqueue()

In the main program of the simulation the user is asked whether they want to add an item to the queue or remove an item.

If they choose to add an item they have to input the job name, and the function enqueue is called.

If they choose to remove an item, the function dequeue is called and the job name is output.

Appropriate messages are output if either action cannot be run because the queue is either empty or full.

Write, using pseudocode or program code, an algorithm for the main program of the simulation.

The queue is changed to make it a circular queue.

Describe how the functions enqueue and dequeue will need to be changed to allow buffer to work as a circular queue.

Some print jobs can have different priorities. The higher the priority the sooner the job needs to be printed.

Describe how the program could be changed to deal with different priorities.

A computer program stores data input on a stack named dataItems. The stack has two sub-programs to add and remove data items from the stack. The stack is implemented as a 1D array, dataArray.

The current contents of dataItems are shown:

The main program asks a user to push or pop an item from the stack. If the user chooses ‘push’, the data item is added to the stack. If the user chooses “pop”, the next item is removed from the stack, multiplied by 3 and output.

The main program is shown:

Before the sub-programs, push() and pop(), can add or remove items from the stack, a selection statement is used to decide if each action is possible.

Describe the decision that needs to be made in each sub-program and how this impacts the next process.

The algorithm does not work when the user enters "PUSH" or "Push". The algorithm needs to be changed in order to accept these inputs.

Identify the line number to be changed and state the change that should be made.

The stack is implemented as a 1D array, dataArray.

Describe how a 1D array can be set up and used to push and pop items as a stack.

As an array, the data in dataArray is sorted and then searched for a specific value.

The data in dataArray is sorted into ascending order using an insertion sort.

The current contents of dataArray are shown:

Show the steps of an insertion sort on the current contents of the array dataArray.

The array dataArray can now be searched using a binary search.

Describe the stages of a binary search on an array of size n.

The array has 50 items.

The function, searchItem(), performs a linear search for a data item.

Rewrite the function using a while loop.

Kamran is writing a program to manipulate the data for a set of items.

For each item, the program needs to store:

• Item name (e.g. Box)

• Cost (e.g. 22.58)

• Date of arrival (e.g. 1/5/2018)

• Transferred (e.g. true)

The items are added to a queue for processing.

The queue is defined as a class, itemQueue.

The head attribute points to the first element in the queue. The tail attribute points to the next available space in the queue. The numItems attribute states how many items are currently in the queue.

The data about the items can be stored using either a record structure, or as objects of a class.

Explain the similarities and differences between a record and a class.

Kamran chooses to use a record structure to store the data about the items.

Record structures may be declared using the following syntax:

Complete the pseudocode to declare a record called items.

New records may be created using the following syntax:

Write a programming statement to create a new item, using the identifier ‘box1’, with the item name “Box”, the cost 22.58, date of arrival 1/5/2018 and transferred true.

The array, theItems, stores the items in the queue. When the tail of the queue exceeds the last element in the array, it adds a new item to the first element if it is vacant.

For example, in the following queue, the next item to be added would be placed at index 0.

Define the term ‘queue’.

The attributes in itemQueue are all declared as private.

Explain how a private attribute improves the integrity of the data.

The constructor method creates a new instance of itemQueue and sets the head, tail and numItems attributes to 0.

Write an algorithm, using pseudocode or program code, for the constructor including the initialisation for all attributes.

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.

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

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.

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.

* Kamran wants to expand the program to allow it to handle up to 100,000,000 items and to allow him to search for data about items. Kamran is worried that the increase in the number of items will cause a decrease in the performance of the program. He decides to investigate the benefits of caching and concurrent processing.

Evaluate the use of caching and concurrent processing in this scenario and make a recommendation to Kamran.

An encryption routine reads a line of text from a file, reverses the order of the characters in the string and subtracts 10 from the ASCII value of each letter, then saves the new string into the same file.

The program is split into sub-procedures. Three sub-procedures are described as follows:

• Read string from file

• Push each character of the string onto a stack

• Read and encrypt each character message

Identify one further sub-procedure that could be used in the program.

Describe two advantages of splitting the problem into sub-procedures.

A function, readMessage:

• takes the file name as a parameter

• reads and returns the line of text

Complete the pseudocode algorithm for readMessage:

A function, push, can be used to add a character to a stack. For example:

theStack.push("H")

places the character H onto the stack, theStack.

A procedure, pushToStack, takes a string as a parameter and pushes each character of the message onto the stack, messageStack.

Complete the procedure below.

Add comments to explain how your code works.

procedure pushToStack(message)

endprocedure

Describe the steps that the program would have to take in order to encrypt the characters stored in the stack, and save them in a single variable.