Stack and Queue

Executive Summary

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.

Purpose

• Introduce data structures stack and queue
• Apply stack and queue to solve real world problems

Deliverables

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.

Part1

• ass6_stack.h
• ass6_stack.c
• ass6_queue.h
• ass6_queue.c

Part2

• ass6_calculator.h
• ass6_calculator.c
• ass6_logMgr.h
• ass6_logMgr.c

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.

• ass6_calculator_test.c
• ass6_logMgr_test.c

Stack

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:

• initialize: create a new stack and return a pointer to the new stack
  • e.g. Stack* my_stack = initialize_stk();
• size: return the number of elements on the specified stack
  • e.g. size(my_stack);
• push: add an element to the specified stack
  • e.g. push(my_stack, 1.5);
• pop: return and remove the last element added to the specified stack
  • e.g. double result = pop(my_stack);
• peek: simply return the last element added to the specified stack
  • e.g. double result = peek(my_stack);
• search: search the specified stack and return the position of the target, if not found, return NULL
  • e.g. int position = search(my_stack, 1.5);
• printStack: print all the elements on the specified stack
  • e.g. if the stack is like this: See image.

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

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:

• initialize: create a new queue and return a pointer to the new queue
  • e.g. Queue* my_Q = initialize_q();
• enqueue: add an element to the back of the specified queue
  • e.g. enqueue(my_Q, 3);
• dequeue: return and remove the front element in the specified queue
  • e.g. int result = dequeue(my_Q);
• insert: insert an element at a specified location; return 1 if success, 0 otherwise
  • e.g. insert(my_Q, 3, 0); //the front-most element is now 3
  • e.g. insert(my_Q, 18, 2); //the third element is now 18
• printQueue: print all the elements in the queue
  • e.g. if the queue is like this: See image.

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 Calculator

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.

Simple Log File Manager

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.

Implementation Notes

• You should use the struct declaration provided in the header files. They can potentially make your life easier.
• You should safeguard your data structures. Popping an empty stack and dequeueing an empty queue should not be allowed. You can insert element to the front and back of the queue, but “inserting to position 5” on a queue of size 2 does not make sense and should not be allowed.
• Your stack and queue are expected to grow very large, so arrange your design accordingly. All the operations should finish within a reasonable time period.
• Since you’ll be calling malloc to allocate memory, you must call free when the memory you allocated is no longer in use. Your program should not cause any memory leak.
• Wrap all your data in structs, no global variables allowed.