DSABook – Practice questions: lists, stacks and queues

4.11 Practice questions: lists, stacks and queues

4.11.1 Stack and Queue summary questions

Here are some general practice questions about stacks and queues.

Which value of a stack is accessible?

The top item
The front item
The root
The bottom item
The rear item
The highest-valued item
The lowest-valued item

Stacks do not care about the relative order of the values for the items it stores.
A stack gives access only to the last item that was inserted.
This is called the “top” item.

It is an error to pop data from a(n) _______ stack.

Empty
Full
Initialized
Array-based
Linked

“Pop” means to remove.
When can we not remove anything?

In the linked implementation of a queue, a new item would be added:

At the rear
At the head
At the current position
After all other entries that are greater than the new entry
After all other entries that are smaller than the new entry

We don’t care about value order in a queue.
In a queue, we always add at the rear.

The following sequence of operations is performed on a queue:

enqueue(1), enqueue(2), dequeue, enqueue(1), enqueue(2), dequeue, dequeue, dequeue, enqueue(2), dequeue

The values will be output in this order:

1,2,1,2,2
1,2,1,1,2
2,2,1,1,2
2,2,1,2,2
2,1,2,2,1
2,1,2,2,2

Trace the operations, one by one.

One difference between a queue and a stack is:

Queues use two ends of the structure; stacks use only one
Queues require linked lists, but stacks do not
Stacks require linked lists, but queues do not
Stacks use two ends of the structure, queues use only one

Stacks and queues can both be implemented using a linked structure.
The key difference is which end(s) the two stuctures access for insert and remove operations.

If the characters ‘D’, ‘C’, ‘B’, ‘A’ are placed in a stack (in that order), and then removed one at a time, in what order will they be removed?

ABCD
ABDC
DCAB
DCBA

Items come off of a stack in the opposite order from how they went in.

Queue behavior is typically referred to as:

First-In, First-Out
Last-In, First-Out
First Come, First Served
Just-in-Time

In a queue, we remove the one that came in first.

It is an error to dequeue data from a(n) _______ queue.

Empty
Full
Array-based
Linked

“Dequeue” means to remove. When can we not remove from a queue?-

Which value of a queue is accessible?

The front item
The top item
The root
The bottom item
The rear item
The highest-valued item
The lowest-valued item

In a queue, we remove from (access) the front (and insert at the rear).

The Stack is best characterized as:

Last-In, First-Out
First-In, First-Out
First come, First Served
Just-in-Time

The queue is called “First-in, First-out”
The stack is called “Last-in, First-out”

In the linked implementation of a queue, a new item would be added to the:

Rear
Front
Current position
None of these

In any queue implementation, we always add to the rear.

If the characters ‘D’, ‘C’, ‘B’, ‘A’ are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?

DCBA
ABCD
ABDC
DCAB

Items are removed from a queue in the same order as they arrived.

Stack A has entries a, b, c (in that order with a on top), while Stack B is initially empty. When an entry is popped out of stack A, it can be printed immediately or pushed to stack B. When an entry is popped out of stack B, it can only be printed. Which of the following permutations of a, b, c is not possible to print?

c a b
b a c
b c a
a b c

We can manage to get “c” to print first.
But to do so requires putting “a” and then “b” into stack B.-
Which then means that they must come out of B and be printed in reverse order.

The following sequence of operations is performed on a stack:

push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop

The values will be output in this order:

2,2,1,1,2
1,2,1,2,2
1,2,2,1,2
2,2,1,2,2
2,1,2,2,1
2,1,2,2,2

Trace the series of operations onto a stack.

4.11.2 List summary questions

Here are some general practice questions about various data structures in this chapter.

The term “LIFO” is associated with which data structure?

Stack
List
Queue
All of these
None of these

LIFO means “Last-in, First-out”.

Which of the following is not a linear data structure?

These are all linear data structures
Queue
Array-based list
Linked list
Stack

We studied all of these data structures in this chapter.

Which data structure would be used to implement recursion?

Stack
Queue
Array-based list
Linked list
Tree

When unwinding from recursion, we say that you “pop” the recursive “stack”.

Which data structure allows insertion only at the top, and deletion only at the top?

Stack
Queue
Array-based list
Linked list
Tree

We use the term “top” with only one of these data structures.
We add and remove at the “top” with the stack.

Which data structure allows insertion only at the back, and removing only from the front?

Queue
Stack
Array-based list
Linked list
Tree

We did not cover trees in this chapter.
Lists do not restrict where inserts and removes take place.

The terms “enqueue” and “dequeue” are associated with which data structure?

Queue
Stack
Array
List
All of these
None of these

What does “enqueue” and “dequeue” mean?

The terms “add/insert” and “delete” are traditionally associated with which data structure(s)?

List
Stack
Queue
All of these
None of these

Stacks and Queues have special terminology that is used instead of the more general “insert” and “delete”.

The term “FIFO” is associated with which data structure?

Queue
List
Stack
Freelist
All of these
None of these

FIFO means “first-in, first-out”

Which of the following is not a linear data structure?

Tree
Queue
Array-based list
Linked list
Stack
These are all linear data structures

Which is the one data structure not covered in this chapter?

The terms “push” and “pop” are associated with which data structure?

Stack
Queue
Array
List
All of these
None of these

“Push” and “pop” are special terminology associated with one of these data structures.
You push items onto a stack, and pull them off.