开源软件名称：

开源软件地址：

开源编程语言：

开源软件介绍：

LAB | JS Advanced Algorithms

Learning Goals

In this exercise, you will be able to:

• Use data structures to organize your application information
• Learn how to model real-life situations and objects into proper data structures
• Use tests to develop your solution.

Data Structures

A data structure is a particular way to organize your data so it can be used efficiently. One or more abstract data types can be implemented and they specify the operations that can be performed over a data structure.

In this exercise, we will implement two different abstract data types that are very common: stacks and queues. Let's take a look at both data structures to understand how they work.

Requirements

• Fork this repo.
• Then clone this repo.
• Visit the "Actions" tab in your fork, and enable workflows.

Submission

• Upon completion, run the following commands:

$ git add .
$ git commit -m "Solved lab"
$ git push origin master

• Create a Pull Request so your TAs can check up your work.

Useful information

Stacks

A stack is a simple data structure that allows adding and removing elements in a particular order. Every time you add a new element, it goes on the top of the stack. The only element that can be removed is the element that was at the top of the stack.

This data structure is also called a LIFO data structure. LIFO stands for "last in, first out", meaning that the last element we put in the stack, is the first element that will go out.

Hint: Think about LIFO data structure as if it were a stack of books. You can put a book on top of the others, and you only remove books from the top of the pile.

Queues

Queues are the other abstract data type we are going to be looking at. They are also referred to as a linear data structure. This means that the first element is inserted from one end called rear, and the deletion of an existing element takes place from the other end called front.

This makes a queue a FIFO ("first in, first out") data structure, which means that the first element inserted, will also be the first element removed.

The process of adding an element into the queue is called enqueue, and the process of removal of an element from the queue is called dequeue.

Hint: Think about a queue as if it was a line in a supermarket. When you arrive, you are the last in the line, and the next person to pay for their groceries is the one that had arrived first.

Instructions

Introduction

The goal of this exercise is to create a visual layout to show how stacks and queues work. Here is the demo and your end goal: demo-stack-queue.

This exercise is split into two parts:

• Logic: where you will be developing the logic behind stack and queue, and you will be guided by tests. When working on logic, you will write your code in the js/stack/stack-data-structure.js and js/queue/queue-data-structure.js;

• Visual: where you will use your DOM manipulation skills to demonstrate how actually stack and queue work. When you come to this part, you will be working on the js/stack/stack-dom.js and js/queue/queue-dom.js.

Tests, tests!

We have created a set of tests to guide you through the abstract data types implementation. After implementing the JavaScript functionality, create a visual layout to show how each data structure works.

Please, open your terminal, change directories into the root of the lab, and run npm install to install the test runner. Next, you can run the npm run test:watch command to run automated tests. Open the resulting lab-solution.html file with the "Live Server" VSCode extension to see the test results.

Iteration 1 - The Stack

The first abstract data structure we are going to build is the Stack. For this iteration, you'll be working in the js/stack/stack-data-structure.js file. The tests you will be using while developing the solution are in the tests/01-stack-data-structure.spec.js file.

To start, we've provided you with a Stack class. Stack has been given a constructor where a stackControl array has been initialized, and a MAX_SIZE property declared. stackControl will be used to store the items inside of our stack, and MAX_SIZE determines the maximum amount of items that can be held by the stack.

Remember, the stack is a LIFO (Last-In-First-Out) structure. That means that, when taking an element out, it should be the last one that had been inserted. In the end, you'll see that a Stack behaves essentially like a JavaScript Array. Our goal is to study how that logic could be implemented from scratch.

We'll also have to pay attention to any possible Stack Overflow (yes, like the website), and Stack Underflow:

• Stack Overflow occurs when we try to add an element into a stack that is already full.
• Stack Underflow occurs when we try to get an element from an empty stack.

Stack method canPush

Add a method called canPush to the Stack class.

When called, canPush should return true if the stack is not full, false if it is full.

Stack method isEmpty

Add a method called isEmpty to the Stack class.

When called, isEmpty should return true if the stack is empty, false if it holds any item.

Stack method push

Add a method called push to the Stack class. It should accept one argument, an item to be added to the end of the stack.

When push is called, you should first check whether the stack can take any items. To do so, you can call the stack's canPush method.

If the value returned by canPush is true, you should add the item to the stackControl array available in the stack.

If the value returned is false, we have a case of "Stack Overflow". Stack Overflow occurs when we try to add an element into a stack that is already full. This operation shouldn't be allowed. As such, instead of adding the item the the stackControl array, throw an error with the message 'STACK_OVERFLOW'.

throw new Error('STACK_OVERFLOW');

Stack method pop

Add a method called pop to the Stack class. pop will be used to remove the last element in the stack.

When pop is called, you should first check whether the stack holds any items. To do so, you can call the stack's isEmpty method.

If the value returned by isEmpty is false, you should remove the last item of the stackControl array.

If the value returned by isEmpty is true, we have a case of "Stack Underflow". Stack Underflow occurs when we try to remove an item from an empty stack. This operation shouldn't be allowed. As such, we should throw an error with the message 'STACK_UNDERFLOW'.

Stack method display

Lastly, let's add a method called display to the Stack class. The method should simply return the list of items stored in the stack.

Iteration 2 - The Queue

The second abstract data type we are going to build is the Queue. For this iteration, you'll be working in the js/queue/queue-data-structure.js file. The tests you will be using while developing the solution are in the tests/02-queue-data-structure.spec.js file.

Queue has been given a constructor where a queueControl array has been initialized, and a MAX_SIZE property declared. queueControl will be used to store the items inside of our queue, and MAX_SIZE determines the maximum amount of items that can be held by the queue.

Remember that queue is a FIFO (First-In-First-Out) structure. That means that, when taking an element out, it should be the first one that had been inserted.

You have to add the right methods to add (enqueue()) elements to the structure, and it also should have the necessary methods to remove (dequeue()) elements from it in the same order we added them.

Similar to the edge scenarios we had to cover for the Stack data structure, we'll have to be aware of Queue Overflow and Queue Underflow.

• Queue Overflow occurs when we try to add an element into a queue that is already full.
• Queue Underflow occurs when we try to get an element from an empty queue.

Queue method canEnqueue

Add a method called canEnqueue to the Queue class.

When called, canEnqueue should return true if the queue is not full, false if it is full.

Queue method isEmpty

Add a method called isEmpty to the Queue class.

When called, isEmpty should return true if the queue is empty, false if it holds any item.

Queue method enqueue

Add a method called enqueue to the Queue class. It should accept one argument, an item to be added to the end of the queue.

When enqueue is called, you should first check whether the queue can take any items. To do so, you can call the queue's canEnqueue method.

If the value returned by canEnqueue is true, you should add the item to the queueControl array available in the queue.

If the value returned is false, we have a case of "Queue Overflow". Queue Overflow occurs when we try to add an element into a queue that is already full. This operation shouldn't be allowed. As such, instead of adding the item the the queueControl array, throw an error with the message 'QUEUE_OVERFLOW'.

throw new Error('QUEUE_OVERFLOW');

Queue method dequeue

Add a method called dequeue to the Queue class. dequeue will be used to remove the first element in the queue. This is the main differentiating point between a Stack and a Queue.

When dequeue is called, you should first check whether the queue holds any items. To do so, you can call the queue's isEmpty method.

If the value returned by isEmpty is false, you should remove the first item of the queueControl array.

If the value returned by isEmpty is true, we have a case of "Queue Underflow". Queue Underflow occurs when we try to remove an item from an empty queue. This operation shouldn't be allowed. As such, we should throw an error with the message 'QUEUE_UNDERFLOW'.

Queue method display

Lastly, let's add a method called display to the Queue class. The method should simply return the list of items stored in the queue.

Iteration 3 - Visualizing our data structures

And let's go to the visuals! Once you have created the full functionality, let's create a visual representation to see how these stacks and queues work.

We already provided you with full HTML code in the index.html. Also, we gave you a head start in the js/stack/stack-dom.js and js/queue/queue-dom.js.

Most of the bare-bones are already implemented, and the interface is self-explanatory. Make it work to the best of your ability.

Happy coding! ❤️

Extra Resources

• Data Structures
• Stacks
• Queues