Starting from:
$30
CS211-Assignment 1 Stack,Queue and Doubly Linked List Solved
The objective of this assignment is to implement Stack (Task 1), Queue (Task 2), and Doubly linked list (Task 3). Please read this document carefully before start coding.
Command-line arguments
Your program should receive two command line arguments: a file name followed by a number. For example, ‘./a.out input.txt 1000’ will be a typical execution of your program.
Input file
The input file will be a text file where each line will start with either of the four symbols: ‘+’, ‘-’, ‘?’, ‘!’. Here, ‘+’ stands for PUSH/ENQUEUE/INSERT, ‘-’ stands for POP/DEQUEUE/DELETE, ‘?’ stands for SEARCH, and ‘!’ stands for display. Additionally, ‘+’, ‘?’, and ‘-’ are followed by a positive integer, which is the argument for that particular operation. Note that the number followed by ‘-’ should be ignored for Task 1 (Stack) and Task 2 (Queue), as it is not relevant.
The content of an example input file is given below.
+ 10
+ 24
+ 1
!
- 24
- 1
? 10
? 9
!
Task 1 (Stack;)
Implement a Stack using arrays. The size of the Stack (the number of elements that can be stored in the Stack) is given by the second command-line argument.
Output: The output of this task should be in a file named ‘stack.txt’. For every line of input file there should be a corresponding line in the output file.
● If there is a line with ‘+ y’ then your program should PUSH (if possible) the number ‘y’ into the Stack and then print ‘pushed y’ or ‘overflow’ (whichever is applicable) to the output file.
● If there is a line with ‘-’ in the input file then your program should POP (if possible) an element from the Stack and print ‘popped y’ or ‘underflow’ (whichever is applicable) into the output file.
● A line with ‘? y’ should cause your program to check if y is there in the Stack and print “found y” or “not found y” accordingly into the output file.
● A line with ‘!’ should cause your program to print (last-in first) the content of the Stack into the output file.
For example, the stack.txt should contain the following lines when your program is invoked with the given input and stack-size 5:
pushed 10 pushed 24 pushed 1 1 24 10 popped 1 popped 24 found 10 not found 9
10
Task 2 (Queue;)
Implement a Queue using arrays. The size of the Queue (the number of elements that can be stored in the Queue) is given by the second command-line argument.
Output: The output of this task should be in a file named ‘queue.txt’. For every line of input file there should be a corresponding line in the output file.
● If there is a line with ‘+ y’ then your program should ENQUEUE (if possible) the number ‘y’ into the Queue and then print ‘enqueued y’ or ‘overflow’ (whichever is applicable) to the output file.
● If there is a line with ‘-’ in the input file then your program should DEQUEUE (if possible) an element from the Queue and print ‘dequeued y’ or ‘underflow’ (whichever is applicable) into the output file.
● A line with ‘? y’ should cause your program to check if y is there in the Queue and print “found y” or “not found y” accordingly into the output file.
● A line with ‘!’ should cause your program to display (first-in first) the content of the Queue.
For example, the queue.txt should contain the following lines when invoked with the given input and second command-line argument 5:
enqueued 10 enqueued 24 enqueued 1 10 24 1
dequeued 10 dequeued 24 not found 10 not found 9
1
Task 3 (Doubly Linked List, ):
Implement a Doubly Linked List (DLL). There is no size limit for the DLL. So, the second command-line argument is ignored for this task.
Output: The output of this task should be in a file named ‘dll.txt’. For every line of input file there should be a corresponding line in the output file.
● If there is a line with ‘+ y’ then your program should INSERT the number ‘y’ into the DLL and then print ‘inserted y’ to the output file.
● If there is a line with ‘- y’ in the input file then your program should DELETE (if possible) the first occurrence (while searching from list head) of y from the DLL and print ‘deleted y’ or ‘cannot delete y’ (whichever is applicable) into the output file.
● A line with ‘? y’ should cause your program to check if y is there in the DLL and print “found y” or “not found y” accordingly.
● A line with ‘!’ should cause your program to display (last-in first) the content of the DLL.
For example, the dll.txt should contain the following lines when invoked with the given input:
inserted 10 inserted 24 inserted 1 1 24 10 deleted 24 deleted 1 found 10 not found 9
10
Command-line arguments
Your program should receive two command line arguments: a file name followed by a number. For example, ‘./a.out input.txt 1000’ will be a typical execution of your program.
Input file
The input file will be a text file where each line will start with either of the four symbols: ‘+’, ‘-’, ‘?’, ‘!’. Here, ‘+’ stands for PUSH/ENQUEUE/INSERT, ‘-’ stands for POP/DEQUEUE/DELETE, ‘?’ stands for SEARCH, and ‘!’ stands for display. Additionally, ‘+’, ‘?’, and ‘-’ are followed by a positive integer, which is the argument for that particular operation. Note that the number followed by ‘-’ should be ignored for Task 1 (Stack) and Task 2 (Queue), as it is not relevant.
The content of an example input file is given below.
+ 10
+ 24
+ 1
!
- 24
- 1
? 10
? 9
!
Task 1 (Stack;)
Implement a Stack using arrays. The size of the Stack (the number of elements that can be stored in the Stack) is given by the second command-line argument.
Output: The output of this task should be in a file named ‘stack.txt’. For every line of input file there should be a corresponding line in the output file.
● If there is a line with ‘+ y’ then your program should PUSH (if possible) the number ‘y’ into the Stack and then print ‘pushed y’ or ‘overflow’ (whichever is applicable) to the output file.
● If there is a line with ‘-’ in the input file then your program should POP (if possible) an element from the Stack and print ‘popped y’ or ‘underflow’ (whichever is applicable) into the output file.
● A line with ‘? y’ should cause your program to check if y is there in the Stack and print “found y” or “not found y” accordingly into the output file.
● A line with ‘!’ should cause your program to print (last-in first) the content of the Stack into the output file.
For example, the stack.txt should contain the following lines when your program is invoked with the given input and stack-size 5:
pushed 10 pushed 24 pushed 1 1 24 10 popped 1 popped 24 found 10 not found 9
10
Task 2 (Queue;)
Implement a Queue using arrays. The size of the Queue (the number of elements that can be stored in the Queue) is given by the second command-line argument.
Output: The output of this task should be in a file named ‘queue.txt’. For every line of input file there should be a corresponding line in the output file.
● If there is a line with ‘+ y’ then your program should ENQUEUE (if possible) the number ‘y’ into the Queue and then print ‘enqueued y’ or ‘overflow’ (whichever is applicable) to the output file.
● If there is a line with ‘-’ in the input file then your program should DEQUEUE (if possible) an element from the Queue and print ‘dequeued y’ or ‘underflow’ (whichever is applicable) into the output file.
● A line with ‘? y’ should cause your program to check if y is there in the Queue and print “found y” or “not found y” accordingly into the output file.
● A line with ‘!’ should cause your program to display (first-in first) the content of the Queue.
For example, the queue.txt should contain the following lines when invoked with the given input and second command-line argument 5:
enqueued 10 enqueued 24 enqueued 1 10 24 1
dequeued 10 dequeued 24 not found 10 not found 9
1
Task 3 (Doubly Linked List, ):
Implement a Doubly Linked List (DLL). There is no size limit for the DLL. So, the second command-line argument is ignored for this task.
Output: The output of this task should be in a file named ‘dll.txt’. For every line of input file there should be a corresponding line in the output file.
● If there is a line with ‘+ y’ then your program should INSERT the number ‘y’ into the DLL and then print ‘inserted y’ to the output file.
● If there is a line with ‘- y’ in the input file then your program should DELETE (if possible) the first occurrence (while searching from list head) of y from the DLL and print ‘deleted y’ or ‘cannot delete y’ (whichever is applicable) into the output file.
● A line with ‘? y’ should cause your program to check if y is there in the DLL and print “found y” or “not found y” accordingly.
● A line with ‘!’ should cause your program to display (last-in first) the content of the DLL.
For example, the dll.txt should contain the following lines when invoked with the given input:
inserted 10 inserted 24 inserted 1 1 24 10 deleted 24 deleted 1 found 10 not found 9
10
1 file (97.9KB)
