Code:
#include <stdio.h>
#include <string.h>
#define SIZE 256 // Size of the filename and event strings
// Instances of this structure represent a train staion
struct stack
{
struct queue* store; // An array of queues, used to store trains
int top; // Index value of store. Where the top of the stack is
int size; // Size of the array of queues (store)
};
// Instances of this structure represent a train
struct queue
{
int* store; // Array of integers. Used to store the car numbers
int front; // Indicates where the front of the queue is
int back; // Indicates where the back of the queue is
int size; // Size of the store array
};
// Function prototypes! Arranged by type for your convenience!
void push(struct stack* s, struct queue item);
void expand_stack(struct stack* s);
void print_stack(struct stack* s);
void print_queue(struct queue q);
void enqueue(struct queue* q, int data);
void dequeue(struct queue* q);
void expandqueue(struct queue* q);
void welcome_msg();
int is_queue_empty(struct queue* q);
int is_stack_empty(struct stack* s);
struct queue* new_queue(int initsize);
struct stack* new_stack(int initsize);
struct queue* new_top(struct queue top);
struct queue pop(struct stack* s);
int main(void)
{
FILE* fin; // Typical file pointer
char filename[SIZE], event[SIZE]; // The filename and event strings; Retrived from user and file input respectively
struct stack* station; // The station (stack) used throughout the program
struct queue* train; // The train(s) used throughout the program; Represents the newest one to be created
struct queue* toptrain; // The train on the top of our stack of trains
int totnum, num, choice; // Total number of events, number of cars / car number, and while loop condition, respectively
welcome_msg(); // Probably the coolest welcome message ever
do // Will execute program until user chooses to quit!
{
printf("Enter input filename: ");
scanf("%s", &filename);
printf("\n");
fin = fopen("input.txt", "r"); // Reads input file
// Checks first value of the file. This is used to determine how many
// events are scheduled, and also the initial size of the stack
fscanf(fin, "%d", &totnum);
station = new_stack(totnum); // Initialize a new stack; Holds totnum elements
int i; // Loop index
for(i = 0; i < totnum; i ++) // Reads each event in the file; Number of events specified by totnum
{
fscanf(fin, "%s", &event); // Reads the event
if(strcmp(event, "new_train") == 0) // Checks to see if the event is new_train
{
fscanf(fin, "%d", &num); // Scans the number of cars, so we know how big our new queue needs to be
train = new_queue(num); // Initializes our queue; Initially it can hold num elements
int k; // Loop index
for(k = 0; k < num; k++) // Reads in each car number and adds it to the train
{
int qnum;
fscanf(fin, "%d", &qnum);
enqueue(train, qnum); // Adds cars onto train queue; FIFO
}
push(station, *train); // Pushes our new queue (train) onto the stack
printf("ADDED TRAIN: ");
print_queue(*train); // Prints a representation of the current queue
printf("\n");
print_stack(station); // Prints a representation of the current stack
}
else if(strcmp(event, "train_departs") == 0) // If a train departs...
{
if(is_stack_empty(station)) // Checks to see if stack is empty; That is, no trains can depart
{
printf("The station is EMPTY! No train departed!\n\n");
}
else
{
printf("Train departed: ");
print_queue(pop(station)); // Pops the stack; Prints the train that departed
printf("\n");
print_stack(station);
}
}
else if(strcmp(event, "add_car") == 0) // If a car is to be added...
{
if(is_stack_empty(station)) // An empty station means no trains to add cars to!
printf("The station is empty! No trains to add cars to!\n");
else
{
fscanf(fin, "%d", &num);
printf("ADD CAR: %d\n", num);
// Initializes our top train; Pop returns the queue at the top, so it is copied to
// toptrain, enqueded with the car specified, and re-pushed onto the stack as toptrain
toptrain = new_top((pop(station)));
enqueue(toptrain, num);
push(station, *toptrain);
print_stack(station);
}
}
else if(strcmp(event, "remove_car") == 0) // If a car is to removed...
{
if(is_stack_empty(station)) // An empty station means no trains to remove cars from!
printf("The station is empty! No trains to remove cars from!\n");
else
{
int dnum; // The number of the car to be removed
// Once again, pop returns the queue at the top of the stack, so we pop, copy
// the top queue to toptrain, dequeue toptrain, and push it back onto the stack
toptrain = new_top((pop(station)));
dnum = toptrain->store[toptrain->front];
printf("REMOVING CAR: %d\n", dnum);
dequeue(toptrain);
push(station, *toptrain);
print_stack(station);
}
}
}
fclose(fin);
free(train->store);
free(train);
free(toptrain->store);
free(toptrain);
free(station->store);
free(station);
printf("Load another file? (1 = yes || 0 = no): ");
scanf("%d", &choice);
printf("\n");
while(choice != 1) // Shall we go again?
{
if(choice == 0)
break;
else
{
printf("Invalid selection! Please choose again!\n");
printf("Load another file? (1 = yes || 0 = no): ");
scanf("%d", &choice);
printf("\n");
}
}
}while(choice != 0);
printf("Train station abandoned! Goodbye!\n");
system("PAUSE"); // Pauses the shell (WINDOWS ONLY)
return 0;
}
// Typical stack expansion function. Makes our store array bigger. This is here because
// store could get filled. Specifically, this function doubles the size of the store array.
void expand_stack(struct stack* s)
{
struct queue* oldstore = s->store; // Pointer to our store array of queues
s->store = calloc(s->size * 2, sizeof(struct queue)); // Doubles the size, essentially
int i; // Loop index; Copies the store array to our new, double sized one.
for(i = 0; i < s->size; i++)
{
s->store[i] = oldstore[i];
}
s->size *= 2;
free(oldstore);
}
// Standard stack constructor. Initsize is the size of the store array.
struct stack* new_stack(int initsize)
{
struct stack* s;
s = malloc(sizeof(struct stack)); // Allocate memory
s->store = calloc(initsize, sizeof(struct queue)); // Create our store array
s->top = 0;
s->size = initsize; // Size is same as array
return s;
}
// Pushes data onto the top of the stack; LIFO; The data is a queue (train)
void push(struct stack* s, struct queue item)
{
if(s->top == s->size) // If we run out of space in the array, we need to expand
expand_stack(s);
s->store[s->top] = item; // Top of the array becomes our item. Top is increased
s->top++;
}
// Standard stack pop. Removes the item on the top of the stack and returns it;
struct queue pop(struct stack* s)
{
s->top--;
return s->store[s->top];
}
// Returns 1 if the stack is empty.
int is_stack_empty(struct stack* s)
{
return s->top == 0;
}
// Prints a current representation of the stack
void print_stack(struct stack* s)
{
if(is_stack_empty(s))
{
printf("The station is EMPTY!\n\n");
return;
}
printf("Station current state: ");
int i; // Loop index
for(i = 0; i < s->top; i++)
{
print_queue(s->store[i]); // Prints each train within the stack
printf(" ");
}
printf("\n\n");
}
// Standard queue initialization. Basically the same as new_stack. Initisize is
// the size of the store array
struct queue* new_queue(int initsize)
{
struct queue* q;
q = malloc(sizeof(struct queue)); // Make some space
q->store = calloc(initsize, sizeof(int)); // Store array is initsize big
q->front = 0;
q->back = 0;
q->size = initsize;
return q;
}
// Works similar to expandstack and for the same reasons. The store array could
// become full, thus it needs to be expanded. This also doubles the size of the array.
void expandqueue(struct queue* q)
{
int* oldstore = q->store;
q->store = calloc(q->size * 2, sizeof(int)); // The new, double-sized store array
int i; // Loop index
for(i = 0; i < q->size; i++)
{
q->store[i] = oldstore[(i+q->front) % q->size]; // Copies data to new array. Allows for an odd number of spaces
}
q->front = 0;
q->back = q->size;
q->size = q->size * 2; // Twice the size. This makes sure size value supports the actual size
free(oldstore);
}
// Technially, this does not check if the queue (train) is empty, but works under the same
// principle. What it does is check to see if the queue has only one object. This is because
// you can't have a train with 0 cars. To check if the queue is truely empty, just remove the
// -1 from q->back.
int is_queue_empty(struct queue* q)
{
return q->front == q->back-1;
}
// Adds data to the back of the queue. If its full, it calls expandqueue to make
// it bigger.
void enqueue(struct queue* q, int data)
{
q->store[q->back] = data; // Object at the back becomes our data
q->back = (q->back + 1) % q->size; // Move the back up one position. Also makes sure we don't exceed the size of the array
if(q->front == q->back) // Is it full? If so, double the size
{
expandqueue(q);
}
}
// Removes the item at the front of the queue.
void dequeue(struct queue* q)
{
if(is_queue_empty(q) == 1) // Is our queue "empty" (according to Bob)? If so, theres nothing to dequeue
{
printf("ERROR! Car not removed because there is only ONE car left on the train!\n");
return;
}
else
{
q->front = (q->front + 1) % q->size; // Removes item from the front. Makes sure we don't exceed the size of array.
return;
}
}
// Prints out a representation of the train. Prints each value in the queue at the time its called.
void print_queue(struct queue q)
{
int i;
printf("[ ");
for(i = q.front; i < q.back; i++)
printf("%d ", q.store[i]);
printf("]");
}
// Exactally the same as new_queue, but this is used when pop returns a queue, and not a pointer.
// Function is used when we need to create and edit the train currently at the top of the stack.
// For a more detailed explanation, see function new_queue
struct queue* new_top(struct queue top)
{
struct queue* q;
q = malloc(sizeof(struct queue));
q->store = calloc(top.size, sizeof(int));
q->front = top.front;
q->back = top.back;
q->size = top.size;
int i;
for(i = top.front; i < top.back; i++)
{
q->store[i] = top.store[i];
}
return q;
}
// By far the coolest welcome message ever
void welcome_msg()
{
printf(" (@@@) (@@@@@) \n");
printf(" (@@) (@@@@@@@) (@@@@@@@) \n");
printf(" (@@@@@@@) (@@@@@) (@@@@@@@@@@@) \n");
printf(" (@@@) (@@@@@@@) (@@@@@@) (@@@)\n");
printf(" (@@@@@@) (@@@@@@) (@) \n");
printf(" (@@@) (@@@@) (@@) \n");
printf(" (@@) (@@@) \n");
printf(" .-. \n");
printf(" ] [ .-. _ .-----. \n");
printf(" .\" \"\"\"\" \"\"\"\"\"\" \"\"\"\"| .--` \n");
printf(" (:--:--:--:--:--:--:--:-| [___ .------------------------. \n");
printf(" |C&O : : : : : : [_9_] |'='|.----------------------.| \n");
printf(" /|.___________________________|___|'--.___.--.___.--.___.-'| \n");
printf(" / ||_.--.______.--.______.--._ |---\\'--\\-.-/==\\-.-/==\\-.-/-'/-- \n");
printf(" /__;^=(==)======(==)======(==)=^~^^^ ^^^^(-)^^^^(-)^^^^(-)^^^ \n");
printf("~~~^~~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~\n");
printf(" Welcome to Bob's Train Station! \n\n");
}
