Stacks and Queues

Question 1

stack

Answer 1

• data structure similar to a list with access restricted to only 1 end.
• It stores elements in a LIFO order.
• thought of as vertical data structures
• 2 functions
  1. push()
  2. pop()

Question 2

LIFO

Answer 2

Last In First Out

Question 3

standard stack initiation

Answer 3

class Stack {
    constructor() {
        this.top = null;
    }

Question 4

push()

Answer 4

places data onto the top of a stack

Question 5

pop()

Answer 5

removes data from the top of the stack

Question 6

standard push()

Answer 6

push(data) {
        /* If the stack is empty, then the node will be the
           top of the stack */
        if (this.top === null) {
            this.top = new _Node(data, null);
            return this.top;
        }

    /* If the stack already has something, 
       then create a new node,
       add data to the new node, and
       have the pointer point to the top */
    const node = new _Node(data, this.top);
    this.top = node;
}

Question 7

standard pop()

Answer 7

pop() {
        /* In order to remove the top of the stack, you have to point
           the pointer to the next item and that next item becomes the
           top of the stack */
        const node = this.top;
        this.top = node.next;
        return node.data;
    }

Question 8

queue

Answer 8

data structure that models a FIFO operation
2 functions:
1. enqueue(data)
2. dequeue()

Question 9

FIFO

Answer 9

First In First Out

Question 10

standard queue initiation

Answer 10

class Queue {
    constructor() {
        this.first = null;
        this.last = null;
    }

Question 11

enqueue(data)

Answer 11

adds data to a queue (insertion)

Question 12

dequeue()

Answer 12

removes the oldest data added to a queue (deletion)

Question 13

standard enqueue

Answer 13

enqueue(data) {
            const node = new _Node(data);

        if (this.first === null) {
            this.first = node;
        }

            if (this.last) {
                this.last.next = node;
            }
            //make the new node the last item on the queue
            this.last = node;
        }

Question 14

standard dequeue

Answer 14

dequeue() {
            //if the queue is empty, there is nothing to return
           if (this.first === null) {
               return;
           }
           const node = this.first;
           this.first = this.first.next;
            //if this is the last item in the queue
           if (node === this.last) {
               this.last = null;
           }
           return node.value;
       }