Ch 3: Stacks and Queues

Question 1

Stacks and Queues:
Important Data Structures

Answer 1

• Stack
• Queue
• Array
• Multi-Stack
• Priority Queue

Question 2

Stacks and Queues:
Important Concepts/Operations

Answer 2

• FIFO Ordering
• LIFO Ordering
• Implementing a Stack with an Array
• Implementing a Queue with Stacks
• Sorting Stacks

Question 3

Stack:
Basic Description

Answer 3

• Data is stored as a “stack”, similar to a physical stack of dinner plates
• Uses Last-In, First Out (LIFO) ordering
• The most recently added item is the first removed
• Allows constant-time adds and removes, but linear-time access to nth item

Question 4

Stack:
Defining Operations

Answer 4

• pop()
• push(item)
• peek()
• isEmpty()

Question 5

Stack Operations:
pop()

Answer 5

Removes and returns the top item from the stack

Question 6

Stack Operations:
push( item)

Answer 6

Adds an item to the top of the stack

Question 7

Stack Operations:
peek()

Answer 7

Returns, but does not remove, the top item of the stack

Question 8

Stack Operations:
isEmpty()

Answer 8

Returns true iff the stack is empty

Question 9

Stacks:
Time Complexity

Answer 9

• O(i) time to access the ith item
• Need to pop everything above it
• O(1) time for adding and removing items

Question 10

Uses for Stacks

Answer 10

• Storing temporary data for recursive algorithms, allows going “backward” by popping items off on the way back ‘up”
• Implementing recursive algorithms iteratively

Question 11

Stack Implementation:
Basic Structure

Answer 11

public class MyStack<T> {

    private static class StackNode<T> {
        private T data;
        private StackNode<T> next;
        public StackNode(T data){};
    }

    private StackNode<T> top;

    public T pop(){}
    public void push(T item){}
    public T peek(){}
    public boolean isEmpty(){}
}

Question 12

Stack Implementation:
pop() method

Answer 12

public T pop() {

    if (top == null)
        throw new EmptyStackException();
    
    T item = top.data;
    top = top.next;
    return item;
}

Question 13

Stack Implementation:
push() method

Answer 13

public void push(T item) {

    StackNode<T> node = new StackNode<T>(item);
    node.next = top;
    top = node;
}

Question 14

Stack Implementation:
peek() method

Answer 14

public T peek() {

if (top == null)
        throw new EmptyStackException();
    
    return top.data;
}

Question 15

Stack Implementation:
isEmpty() method

Answer 15

public boolean isEmpty() {
        return top == null;
}

Question 16

Queue:
Basic Description

Answer 16

• Similar to a line or queue at a store
• Items are removed in the same order that they are added
• First In, First Out (FIFO) ordering

Question 17

Queue:
Defining Operations

Answer 17

• add(item)
• remove()
• peek()
• isEmpty()

Question 18

Queue Operations:
add(item) method

Answer 18

Adds an item to the end of the list

Question 19

Queue Operations:
remove()

Answer 19

Removes and returns the first item in the list

Question 20

Queue Operations:
peek()

Answer 20

Returns, but does not remove, the first item in the queue

Question 21

Queue Operations:
isEmpty()

Answer 21

Returns true if the queue is empty, false if it contains items

Question 22

Queue:
Basic Structure

Answer 22

public class MyQueue<T> {
    
    private static class QueueNode<T> {
        private T data;
        private QueueNode<T> next;

        public QueueNode(T data){ this.data = data;}
    }
    
    private QueueNode<T> first;
    private QueueNode<T> last;
		
    public void add(T item){}
    public T remove(){}
    public T peek(){}
    public boolean isEmpty(){}
}

Question 23

Queue:
Common Uses

Answer 23

• Breadth-First Search: Stores a list of nodes that need to be processed in order
• Implementing a cache
• Processing requests, data, events, etc in the order received

Question 24

Queue Implementation:
add(T item)

Answer 24

public void add(T item) {
    
    QueueNode<T> node = new QueueNode<T>(item);
    
    if (last != null) last.next = node;
    last = node;
    if (first == null) first = last;
}

Question 25

Queue Implementation:
remove()

Answer 25

public T remove() {
  
    if (first == null) 
        throw new NoSuchElementException();
    
    T data = first.data;
    first = first.next;
    if (first == null) last = null;
		
    return data;
}

Question 26

Queue Implementation:
peek()

Answer 26

public T peek() {

    if (first == null)
		throw new NoSuchElementException();
		
    return first.data;
}

Question 27

Queue Implementation:
isEmpty()

Answer 27

public boolean isEmpty() {
    return first == null;
}