1. Deque
- Due date: 11:59pm, 10/11/2024
- TA: Sihyeon Roh (sihyeonroh@snu.ac.kr)
Goals
-
Get familiar with C++ programming by implementing simple data structures like (expandable) arrays and linked lists.
-
Get to know how unit testing works and how the rest of the assignments will be graded.
-
Write a simple algorithm on top of the data structures that you wrote. Learn how to separate the interfaces (deque) from the implementations (array or linked list).
Preparation
Install build system(cmake) and dependent library(catch2)
sudo apt-get install cmake catch2 -y
Download the handout tarball, 01-deque.tar.gz and then decompress it. The following commands show how you download the tarball using wget and then decompress it using the command tar.
$ cd ~
$ wget https://compsec.snu.ac.kr/class/data-structure/files/01-deque.tar.gz
...
$ tar -xvf ./01-deque.tar.gz
01-deque/
01-deque/prepare-submit.sh
01-deque/CMakeLists.txt
01-deque/include/
01-deque/tests/
01-deque/examples/
01-deque/palindrome/
01-deque/palindrome/CMakeLists.txt
01-deque/palindrome/include/
01-deque/palindrome/include/palindrome.hpp
01-deque/examples/CMakeLists.txt
01-deque/examples/main.cpp
01-deque/tests/CMakeLists.txt
01-deque/tests/deque_test.cpp
01-deque/tests/palindrome_test.cpp
01-deque/include/deque.hpp
$ cd 01-deque
$ ls -1
CMakeLists.txt
examples
include
palindrome
prepare-submit.sh
tests
Table of contents
Deque API
According to cppreference.com:
std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end.
Here are the common interfaces for a deque defined in deque.hpp:
void push_front(const T&): Add an item to the frontvoid push_back(const T&): Add an item to the backstd::optional<T> remove_front(): Remove an item (if exists) from the frontstd::optional<T> remove_back(): Remove an item (if exists) from the backbool empty(): Returntrueif a deque has no elementsize_t size(): Return the number of items in the dequeT& operator[](size_t i): Get the reference to thei-th item. You should be able to modify the value of the item with the returned reference.
These APIs don't impose any restrictions to the underlying implementation. In the following, we dive into specific deque implementations, namely with arrays and linked lists.
std::optional<T> return type is used to represent a value that may or may not
be present.
It is added to C++17 and has been widely adopted by different languages.
If you are not familiar with this, you can simply assign a value of T to store
a value, or assign std::nullopt to represent that there is no value.
Just like nullptr, it can be tested whether it has a value, using if (!opt).
If a value exists, that value can be retrieved with value() method.
For further information, please refer to
here.
Array Deque Implementation
An array deque stores the items in a circular queue. If you push an item to
the front, you place the item at the index pointed by front and decrease
the front (don't forget to take the modulus). For example, say you are given
an array deque:
size: 3
capapciry: 8
front: 3
back: 6
arr: ---------+
|
v
+---+---+---+---+---+---+---+---+
| | | | | 2 | 3 | 4 | |
+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7
If you call push_front(5), the result will be:
size: 3 -> 4
capapciry: 8
front: 3 -> 2
back: 6
arr: -----+
|
v
+---+---+---+---+---+---+---+---+
| | | | 5 | 2 | 3 | 4 | |
+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7
push_back() can be implemented in a way similar to push_front(). How about
remove_[front/back]()? Just do the reverse and keep everything looks reasonable.
Wait! What if the buffer is full? Especially when front == back? In
that case, you should double the size of your buffer and copy the items
in your original buffer. (In C++, it is often more faster to move items
than simply copying them. But we won't go in to too much details. It is just
okay to copy them for now.)
If you look at the code, you will find out that the type of arr is
std::unique_ptr<T[]>. For those who haven't seen this smart
pointer before, it is used to represent an exclusive ownership over an
object, which avoids to have an explicit (and easy-to-forget)
destructor. In particular, a unique pointer instructs the compiler
that it is the only owner of that object, so the object is destroyed
automatically once the unique pointer is gone from the scope. Methods
like std::make_unique or .reset() will come in handy when you
initialize an object or update a unique pointer, respectively. For
further information, please refer to this
link).
Getting started
In deque.hpp, there are several member functions of ArrayDeque, whose body
is left as TODO. Your job is to implement all of them and pass all the tests
that are provided by tests/deque_tests.cpp. These test cases (and probably
some more private test cases) will be used to grade your submissions. (See
submissions and grading for further information.)
Linked-List Deque Implementation
Another deque implementation that we will implement uses a linked list, especially, a doubly-linked and circular one. The linked list is widely used to store data which dynamically grow or shrink. In the linked list, each node in a list hold pointers to its successor (i.e., a next node) and its predecessor (i.e., a previous node).
To make writing the code more easier and clear, we have the deque create a
dummy node, when initialized. This dummy node is pointed by the sentinel
pointer. Initially, the successor and the predecessor pointer of this dummy node
both points to itself:
size: 0
sentinel: --+
|
v
+---+
+====>| / |=====+
| +---| |<--+ |
| | +---+ | |
| +-----------+ |
+===============+
==>: next
-->: prev
Every time you push an item to this list, you will have make sentinel->next
or sentinel->prev to point a new node, and update the relevant pointers of
neighboring nodes.
For example, given a list deque like this:
size: 3
sentinel: --+
|
v
+---+ +---+ +---+ +---+
+====>| / |==>| 2 |==>| 3 |==>| 4 |====+
| +---| |<--| |<--| |<--| |<-+ |
| | +---+ +---+ +---+ +---+ | |
| +----------------------------------+ |
+======================================+
==>: next
-->: prev
After you push_back(5):
size: 3 -> 4
sentinel: --+
|
v
+---+ +---+ +---+ +---+ +---+
+====>| / |==>| 2 |==>| 3 |==>| 4 |==>| 5 |====+
| +---| |<--| |<--| |<--| |<--| |<-+ |
| | +---+ +---+ +---+ +---+ +---+ | |
| +------------------------------------------+ |
+==============================================+
==>: next
-->: prev
Well, good C++ programmers would use shared_ptr and weak_ptr (both
of which are different types of smart pointers and are used to
represent sharing of the objects) for next, prev and sentinel,
but we won't force you to use it for this assignment (we may in
upcoming assignments? stay tuned!)
Be careful and don't forget to deallocate these nodes in the destructor.
Getting started
In deque.hpp, there are several member functions of ListDeque, whose body
is left as TODO. Your job is to implement all of them and pass all the tests
that are provided by tests/deque_tests.cpp. These test cases (and probably
some more private test cases) will be used to grade your submissions. (See
submissions and grading for further information.)
Application: Palindrome
By far we described how to build deques in two ways---using an array or a linked-list. The deque is a powerful primitive to build either a stack or a queue, and many interesting applications can be implemented based on these. In the rest of this homework, we will implement a simple algorithm which makes a use of a stack: the palindrome tester.
From the Wikipedia:
A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam, racecar.
You simply push each character in a string to a stack, and later pop them to make a string. If two string matches? Then it is a palindrome!
The palindrome tester should be implemented in palindrome/include/palindrome.hpp.
Submission and Grading
Testing your own programs
In 01-deque directory, you run the following commands to compile your own
implementation.
$ pwd
/xxx/xxx/xxx/01-deque
$ mkdir build
$ cd build
$ cmake ../
$ make
$ ls tests/deque_test
./test/deque_test
$ ./tests/deque_test
[...]
$ ./tests/palindrome_test
[...]
If you've all done correctly, the output will look like:
===============================================================================
All tests passed (XX assertions in XX test cases)
and you are ready to submit!
Submission
Prepare your submission by executing the script, prepare-submit.sh. It creates a compressed tar ball, assign1.tar.gz using your deque.hpp and palindrome.hpp.
$ bash prepare-submit.sh
[*] Remove tar file...
[*] Compress files...
a ./include/deque.hpp
a ./palindrome/include/palindrome.hpp
[*] Successfully Compressed!
[*] Done! You are ready to submit
Option 1: Download from the Remote Server Container
If you are using the container on the kayle server, you can transfer the assign1.tar.gz file to your local computer using the scp command:
Open your local terminal (e.g., PowerShell, Bash, etc.)
$ scp -P <port> compsec@kayle.snu.ac.kr:~/01-deque/assign1.tar.gz ./
compsec@kayle.snu.ac.kr's password:
assign1.tar.gz 100% 273 36.8KB/s 00:00
$ ls
assign1.tar.gz
<port>: This is the SSH port used to connect to the container.
Option 2: Download from Your Local Machine’s Container
If you are running the container on your own local machine, use the following scp command to copy the file from the container:
Open your local terminal (e.g., PowerShell, Bash, etc.)
$ scp -P 22222 compsec@localhost:~/01-deque/assign1.tar.gz ./
compsec@localhost's password:
assign1.tar.gz 100% 273 36.8KB/s 00:00
$ ls
assign1.tar.gz
Finally, once you have the assign1.tar.gz file on your local machine, upload it to the eTL.