Stacks and Queues

Question 1

Stack

Answer 1

a data structure that mimics a list where items are added and removed from the top.

Question 2

Pointer

Answer 2

will be used to store the address of the top of the stack

Question 3

What 4 things are stacks used for?

Answer 3

Holding temporary instructions
For holding during an interrupt
Function/Subroutine Calls
Recursive algorithms hold previous results

Question 4

Stack underflow

Answer 4

When there is nothing to pop out of the stack

Question 5

Stack overflow

Answer 5

When you try pushing too much onto a stack that is already full

Question 6

Queue

Answer 6

a data structure that mimics a list where items are added to the rear and removed from the front. It operates using a First In First Out (FIFO) Model

Question 7

Start pointer

Answer 7

Stores the address of the front of the queue

Question 8

Rear Pointer

Answer 8

Stores the address of the rear of the queue

Question 9

Linked List

Answer 9

a dynamic data structure that store item in nodes

Question 10

Node

Answer 10

Part of a linked list that has a pointer which points to the address of the next node

Question 11

What do you do to add a new node at the end of a linked list?

Answer 11

Set the pointer of the last node to the new node.

Question 12

What do you do to insert a new node between existing nodes?

Answer 12

Pointer of previous node is amended to point to new node, and the new nodes pointer points to the next node in list

Question 13

What do you do to delete a node from a linked list?

Answer 13

Pointer of previous node before deleted item will change to point to the next item in the list

Question 14

Traversing lists

Answer 14

Each node is visited and the pointer followed to the address of the next node

Question 15

Single (linked list)

Answer 15

Nodes have a data item as well as a pointer to the next field, the last node contains a NULL pointer

Question 16

Circular (linked list)

Answer 16

When the last node will point to the first node in the list

Question 17

Double/Doubly (linked list)

Answer 17

When each node will have a pointer to the next and previous nodes

Question 18

Name 2 advantages of linked lists over arrays

Answer 18

Much more efficient in terms of memory and processor usage

Inserting/Deleting only require pointers to be changed

Question 19

Name 3 disadvantages of linked lists over arrays

Answer 19

Cannot index a node, have to traverse
Requires storing of additional pointers
Nodes may not be stored contiguously