In this lab, you will learn about the data structures stack and queue, and construct your own ones. Then you’ll use your stack to write a postfix calculator, and use your queue to implement a log file management program.
In this assignment, you’ll be designing a set of functions that other programs can use by including your .h file in them. For example, if somebody want to use your stack implementation, they’ll put assignment6_stack.c in their source directory and include assignment6_stack.h.
Two test files have been provided to you. Passing these test cases does not mean your program is correct. You should construct your own test cases to fully test your program.
Stack is a last in first out (LIFO) abstract data type and linear data structure. It has two fundamental operations push and pop. See image.
In this assignment, your stack should hold double numbers. You can implement it anyway you want, as long as you support the operations listed below:
One implementation is to construct a linked list, each node of the list would have a number and a pointer to the next node.
Queue is a first in first out (FIFO) abstract data type and linear data structure. The first element added to the queue will be the first one to be removed. The basic operations are enqueue and dequeue. See image.
In this assignment, your queue should hold integer values. You can implement it anyway you want, as long as you support the operations list below:
For the queue, you are required to use the linked list design where each node contains an integer number and a pointer to the next node.
Postfix notation is a mathematical notation wherein every operator follows all of its operands. e.g. 3 4 + is the same as 3+4, which results in 7
In this part of assignment 6, you will use the stack you constructed to implement a calculator that takes command in postfix notation and output the proper result. Your calculator should support the basic arithmetic operations (addition, subtraction, multiplication, division).
The input commands will be given as an expression string, each expression represents a set of data and operations that are to be executed separately. Your calculator will be used like this: See image.
The user will pass two parameters into your calculator: an expression and the number of elements in the expression. You can add functions as you like, but you must use your stack to implement the calculator. You should assume that after an expression is fully evaluated, there will only be one number left on the stack, and that is the result.
Hint: the atof function in standard C library parses the C string str interpreting its content as a floating point number and returns its value as a double. On success, the function returns the converted floating point number as a double value. If no valid conversion could be performed, a zero value (0.0) is returned.
Assume that you are given a number of server log files. Each log file contains millions of lines. Each line contains two fields: timestamp and visited_page. Each log file is sorted ascendingly according to timestamp.
You will implement a simple log file manager that tells the user how many log entries are in the past time period. To make this lab easier, we will use long integer as timestamps, and each entry will only contain its timestamp.
Your manager is composed of a queue and a set of functions: A createLogMgr function that takes a time period and returns a pointer to the log manager; an add_to_log function that takes a pointer to the manager, and a timestamp, and returns the number of entries within the time period from the latest timestamp T to T-WINDOW_SIZE.
Here’s how your manager will be tested: See image.