Here we will implement some basic data structure without using STL in C++ and JAVA language.
Like: Stack,Queue,Priority Queue,Hash,Tree,Graph and Linked List.
1. Stack: A stack is a container of objects that are inserted(push) and removed (pop) according to the last-in-first-out(LIFO) principle.
[Problem]
Insert(Push) the given N (2 <=N <=100) numbers in order into a stack, then pop each and print on the screen.
[Input]
The first input line contains the number of test cases,T.
The next line contains the number of data input.
Then,integer data will be listed.
[Output]
For each given test case,print each stack.
Input OUTPUT
2 //Test case #1 5 4 3 2 1
5 //Data size #2 1 2 3 4 5
1 2 3 4 5
5
5 4 3 2 1
Source Code
2. Queue:
A queue is a container of objects that are inserted and removed according to first-in-first-out(FIFO) principle.
[Problem]
Enqueue the given N (2 <=N <=100) numbers in order into a queue, then dequeue each and print on the screen.
[Input]
The first input line contains the number of test cases,T.
The next line contains the number of data input.
Then,integer data will be listed.
[Output]
For each given test case,print each queue.
Input OUTPUT
2 //Test case #1 1 2 3 4 5
5 //Data size #2 5 4 3 2 1
1 2 3 4 5
5
5 4 3 2 1
Source code
3. Hash:
A hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values.
Hash table uses a hash function to compute an index searching into an array of buckets or slots.
[problem]
Store the given N key and data pairs into a hash table, then print each data matching to Q key inputs. * Key : Max 64 chars * Data : Max 128 chars
[Input]
The first input line contains the number of test cases, T.
The next line contains the number of keys and data pairs, N (1<= N <= 4096).
For the following N lines, key and data will be given.
Then the number of keys to search, Q (1 <= Q <= 4096) is given.
[Output]
For each given test case, print the data matching to the given keys.
INPUT OUTPUT
=========================== ==========================
2 // Number of Test cases T #1
8 // Number of input data N Charm
Attract Charm //key data Amaze
Gather Collect not find
Fundamental Essential #2
Abundant Plentiful not find
Achieve Accomplish Stand
Assign Allocate Flaw
Surprise Amaze Tremendous
Assess Estimate not find
3 // Number of data to search Q
Attract
Surprise
education
10
Bear
Stand
Famous
Noted
Characteristic
Attribute
Decrease
Diminish
Defect
Flaw
Depict
Describe
Eager
Avid
Flourish
Thrive
Huge
Tremendous
Important
Crucial
5
treasure
Bear
Defect
Huge
hydrogen
Source Code
4. Priority Queue :
A priority Queue is a data structure where each element has a "priority" associated with it.
In a priority queue, an element with high priority is served before an element with low priority.
[problem]
Store the given N (2 <= N <= 100) numbers into a priority queue, then print from the highest to the
lowest priority in order (assuming that there is no error in the input).
[Input]
The first input line contains the number of test cases, T.
The next line contains the number of data input.
Then, the integer data will be listed.
Lower number has a higher priority.
[Output]
For each given test case, print the numbers in priority order.
INPUT OUTPUT
============= ===================
2 //number of Test cases #1 1 8 10 13 17 38 49 55 56 92
10 //number of Input #2 1 4 5 7 13 14 21 22 22 35 50 99 100
10 49 38 17 56 92 8 1 13 55 //Input Data
13
4 22 50 13 5 1 22 35 21 7 99 100 14
Source Code :
5. Link List :
Linked list is a linear collection of data elements pointing to the next node by means of a pointer.
It is a data structure consisting of a group of nodes which together represent a sequence.
[Problem]
Insert the given N integers to a linked list.
Print the remainder after
1. removing the first number pointed
2. removing next->next recursively
1 // remove the first number pointed 2 3 4 5 2 // pointer moved to 2, remove next->next 4 3 4 5 2 3 5 // pointer moved to 5, remove next->next 3 2 5 // pointer moved to 5, remove next->next 5 2 // remainder
[Input]
The first input line contains the number of test cases, T.
The second line contains the number of input, N (2 <= N <= 100).
On the next line, N data will be given.
[Output]
For each given test case, print the remainder
INPUT OUTPUT
============= ===================
2 //number of Test cases #1 2
5 //number of Input #2 5
1 2 3 4 5 //Input Data
6
1 2 3 4 5 6
Source Code :
6. Tree
[problem]
Construct a tree with the given input and traverse the tree in preorder.
Then, print the visited node numbers.
[Input]
The first input line contains the number of total test cases, T.
The next line contains the number of total nodes, N and the number of edges, E.
On the following line, the edges will be given.
The edges consist of two vertices which are always given in the order “parent-child”.
For instance, 1 2 refers to the edge connecting vertex 1 and vertex 2: 1 stands for parent, 2 for child.
Parent can have two children nodes at most.
The number of nodes can be up to 10000.
[Output]
Traverse the tree in preorder, then print the visited node numbers.
INPUT
=============
3 // number of total Test cases
13 12 // N: number of Nodes, E: number of Edges
1 2 1 3 2 4 3 5 3 6 4 7 7 12 5 9 5 8 6 11 6 10 11 13 // Edge Information (“Parent-Child” order)
10 9
1 2 1 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
50 49
31 7 2 17 27 32 14 30 1 21 45 26 44 27 39 11 26 3 48 6 3 44 2 49 42 13 48 8 23 33 11 10 8 42 41 31 17 4 8 22 25 23 21 41 28 25 13 16 46 2 31 35 42 19 32 18 27 50 45 15 28 20 46 28 44 40 40 5 15 48 9 34 1 46 17 29 35 36 21 45 14 37 23 14 6 39 11 9 19 24 26 47 16 38 40 12 47 43
OUTPUT
===============================
#1
1 2 4 7 12 3 5 9 8 6 11 13 10
#2
1 2 3 4 5 6 7 8 9 10
#3
1 21 41 31 7 35 36 45 26 3 44 27 32 18 50 40 5 12 47 43 15 48 6 39 11 10 9 34 8 42 13 16 38 19 24 22 46 2 17 4 29 49 28 25 23 33 14 30 37 20
Source:
7. Graph:
A graph is a data structure which is a pictorial representation of a set of objects where pairs of objects are connected by links.
[problem]
Print the vertices that are adjacent to the given vertex in query.
[Input]
The first line contains the number of vertices V, the number of edges E and the number of queries Q.
From the second line on, the edge information (number of linked vertices pairs) will be given in ascending order.
On the next line, queries given as vertex numbers (asking for the adjacent vertices) will be given.
Also, edges do not overlap.
Print on each line the adjacent vertices of the given vertex. (2<=V<=100, 1<=E<=1000)
[Output] For each given vertex, print adjacent vertexes.
INPUT
=============
2 // number of Test cases
6 7 3 // number of vertices, edges, queries
0 1 // Edge Information 0 - 1
0 2 0 3 1 2 1 4 3 4 4 5
0 // Query: Vertex Number
2
4
9 10 3
0 1
0 2
0 6
1 3
1 4
1 7
2 4
4 5
6 7
7 8
0
1
7
OUTPUT
===============================
#1
1 2 3 // adjacent vertices of vertex 0
0 1 // adjacent vertices of vertex 2
1 3 5 // adjacent vertices of vertex 4
#2
1 2 6
0 3 4 7
1 6 8
Source
Like: Stack,Queue,Priority Queue,Hash,Tree,Graph and Linked List.
1. Stack: A stack is a container of objects that are inserted(push) and removed (pop) according to the last-in-first-out(LIFO) principle.
[Problem]
Insert(Push) the given N (2 <=N <=100) numbers in order into a stack, then pop each and print on the screen.
[Input]
The first input line contains the number of test cases,T.
The next line contains the number of data input.
Then,integer data will be listed.
[Output]
For each given test case,print each stack.
Input OUTPUT
2 //Test case #1 5 4 3 2 1
5 //Data size #2 1 2 3 4 5
1 2 3 4 5
5
5 4 3 2 1
Source Code
2. Queue:
A queue is a container of objects that are inserted and removed according to first-in-first-out(FIFO) principle.
[Problem]
Enqueue the given N (2 <=N <=100) numbers in order into a queue, then dequeue each and print on the screen.
[Input]
The first input line contains the number of test cases,T.
The next line contains the number of data input.
Then,integer data will be listed.
[Output]
For each given test case,print each queue.
Input OUTPUT
2 //Test case #1 1 2 3 4 5
5 //Data size #2 5 4 3 2 1
1 2 3 4 5
5
5 4 3 2 1
Source code
3. Hash:
A hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values.
Hash table uses a hash function to compute an index searching into an array of buckets or slots.
[problem]
Store the given N key and data pairs into a hash table, then print each data matching to Q key inputs. * Key : Max 64 chars * Data : Max 128 chars
[Input]
The first input line contains the number of test cases, T.
The next line contains the number of keys and data pairs, N (1<= N <= 4096).
For the following N lines, key and data will be given.
Then the number of keys to search, Q (1 <= Q <= 4096) is given.
[Output]
For each given test case, print the data matching to the given keys.
INPUT OUTPUT
=========================== ==========================
2 // Number of Test cases T #1
8 // Number of input data N Charm
Attract Charm //key data Amaze
Gather Collect not find
Fundamental Essential #2
Abundant Plentiful not find
Achieve Accomplish Stand
Assign Allocate Flaw
Surprise Amaze Tremendous
Assess Estimate not find
3 // Number of data to search Q
Attract
Surprise
education
10
Bear
Stand
Famous
Noted
Characteristic
Attribute
Decrease
Diminish
Defect
Flaw
Depict
Describe
Eager
Avid
Flourish
Thrive
Huge
Tremendous
Important
Crucial
5
treasure
Bear
Defect
Huge
hydrogen
Source Code
4. Priority Queue :
A priority Queue is a data structure where each element has a "priority" associated with it.
In a priority queue, an element with high priority is served before an element with low priority.
[problem]
Store the given N (2 <= N <= 100) numbers into a priority queue, then print from the highest to the
lowest priority in order (assuming that there is no error in the input).
[Input]
The first input line contains the number of test cases, T.
The next line contains the number of data input.
Then, the integer data will be listed.
Lower number has a higher priority.
[Output]
For each given test case, print the numbers in priority order.
INPUT OUTPUT
============= ===================
2 //number of Test cases #1 1 8 10 13 17 38 49 55 56 92
10 //number of Input #2 1 4 5 7 13 14 21 22 22 35 50 99 100
10 49 38 17 56 92 8 1 13 55 //Input Data
13
4 22 50 13 5 1 22 35 21 7 99 100 14
Source Code :
5. Link List :
Linked list is a linear collection of data elements pointing to the next node by means of a pointer.
It is a data structure consisting of a group of nodes which together represent a sequence.
[Problem]
Insert the given N integers to a linked list.
Print the remainder after
1. removing the first number pointed
2. removing next->next recursively
1 // remove the first number pointed 2 3 4 5 2 // pointer moved to 2, remove next->next 4 3 4 5 2 3 5 // pointer moved to 5, remove next->next 3 2 5 // pointer moved to 5, remove next->next 5 2 // remainder
[Input]
The first input line contains the number of test cases, T.
The second line contains the number of input, N (2 <= N <= 100).
On the next line, N data will be given.
[Output]
For each given test case, print the remainder
INPUT OUTPUT
============= ===================
2 //number of Test cases #1 2
5 //number of Input #2 5
1 2 3 4 5 //Input Data
6
1 2 3 4 5 6
Source Code :
6. Tree
[problem]
Construct a tree with the given input and traverse the tree in preorder.
Then, print the visited node numbers.
[Input]
The first input line contains the number of total test cases, T.
The next line contains the number of total nodes, N and the number of edges, E.
On the following line, the edges will be given.
The edges consist of two vertices which are always given in the order “parent-child”.
For instance, 1 2 refers to the edge connecting vertex 1 and vertex 2: 1 stands for parent, 2 for child.
Parent can have two children nodes at most.
The number of nodes can be up to 10000.
[Output]
Traverse the tree in preorder, then print the visited node numbers.
INPUT
=============
3 // number of total Test cases
13 12 // N: number of Nodes, E: number of Edges
1 2 1 3 2 4 3 5 3 6 4 7 7 12 5 9 5 8 6 11 6 10 11 13 // Edge Information (“Parent-Child” order)
10 9
1 2 1 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
50 49
31 7 2 17 27 32 14 30 1 21 45 26 44 27 39 11 26 3 48 6 3 44 2 49 42 13 48 8 23 33 11 10 8 42 41 31 17 4 8 22 25 23 21 41 28 25 13 16 46 2 31 35 42 19 32 18 27 50 45 15 28 20 46 28 44 40 40 5 15 48 9 34 1 46 17 29 35 36 21 45 14 37 23 14 6 39 11 9 19 24 26 47 16 38 40 12 47 43
OUTPUT
===============================
#1
1 2 4 7 12 3 5 9 8 6 11 13 10
#2
1 2 3 4 5 6 7 8 9 10
#3
1 21 41 31 7 35 36 45 26 3 44 27 32 18 50 40 5 12 47 43 15 48 6 39 11 10 9 34 8 42 13 16 38 19 24 22 46 2 17 4 29 49 28 25 23 33 14 30 37 20
Source:
7. Graph:
A graph is a data structure which is a pictorial representation of a set of objects where pairs of objects are connected by links.
[problem]
Print the vertices that are adjacent to the given vertex in query.
[Input]
The first line contains the number of vertices V, the number of edges E and the number of queries Q.
From the second line on, the edge information (number of linked vertices pairs) will be given in ascending order.
On the next line, queries given as vertex numbers (asking for the adjacent vertices) will be given.
Also, edges do not overlap.
Print on each line the adjacent vertices of the given vertex. (2<=V<=100, 1<=E<=1000)
[Output] For each given vertex, print adjacent vertexes.
INPUT
=============
2 // number of Test cases
6 7 3 // number of vertices, edges, queries
0 1 // Edge Information 0 - 1
0 2 0 3 1 2 1 4 3 4 4 5
0 // Query: Vertex Number
2
4
9 10 3
0 1
0 2
0 6
1 3
1 4
1 7
2 4
4 5
6 7
7 8
0
1
7
OUTPUT
===============================
#1
1 2 3 // adjacent vertices of vertex 0
0 1 // adjacent vertices of vertex 2
1 3 5 // adjacent vertices of vertex 4
#2
1 2 6
0 3 4 7
1 6 8
Source
