Data Steuctures - Lists : Stacks and Queues 2

민겸·2023년 3월 21일
0

Schoolworks

목록 보기
2/5

Hw1-1

  • Implement a ring buffer with an array of 5
    elements that uses buffer overflow.
  • Test the program using the sequence of
    inserts and deletes

Source Code

/*
Implement a ring buffer with an array of 5
elements that uses buffer overflow.

Circluar queue using ring buffer (array)

Test the program using the sequence of inserts and deletes
*/
#include<stdio.h>

int main() {
	int queue[5];
	int front = -1, rear = -1;
	int choice = 0;
	int item = 0;
	
	while (choice != 4) {
		printf("\nㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ\n");
		printf(" 1. Insert an element into the queue \n");
		printf(" 2. Delete an element from the queue \n");
		printf(" 3. Display all elements of the queue \n");
		printf(" 4. Exit \n");
		printf("Enter your choice: ");
		scanf("%d", &choice);

		switch (choice) {
		case 1:
			if ((front == 0 && rear == 4) || (front == rear + 1)) {
				printf("Queue is full \n");
			}
			else {
				if (front == -1) {
					front = 0;
				}
				rear = (rear + 1) % 5;
				printf("Enter the element to be inserted: ");
				scanf("%d", &item);
				queue[rear] = item;
			}
			break;
		case 2:
			if (front == -1) {
				printf("Queue is empty \n");
			}
			else {
				item = queue[front];
				printf("Element deleted from queue is: %d \n", item);
				if (front == rear) {
					front = -1;
					rear = -1;
				}
				else {
					front = (front + 1) % 5;
				}
			}
			break;
		case 3:
			if (front == -1) {
				printf("Queue is empty \n");
				break;
			}
			else {
				printf("Queue elements are: \n");
				if (front <= rear) {
					for (int i = front; i <= rear; i++) {
						printf("%d ", queue[i]);
					}
					printf("\n");
					break;
				}
				else {
					for (int i = front; i < 5; i++) {
						printf("%d ", queue[i]);
					}
					for (int i = 0; i <= rear; i++) {
						printf("%d ", queue[i]);
					}
					printf("\n");
					break;
				}
			}
		default:
			printf("Invalid choice \n");
			break;
		}
	}

	return 0;
}


Hw1-2

  • Implement and Test a Stack Program, Using a
    Singly Linked List.

  • The order of insert and delete is the same.
    Outputs the current stack or queue contents for each insert or delete)

Source Code

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 10

struct Node
{
	int data;
	struct Node* link;
};

struct Node* top = NULL; // top is empty initially
int n_nodes = 0; // a variable to store number of nodes in stack

int stack_full() {
	if (n_nodes == MAX_SIZE) {
		return 1;
	}
	else {
		return 0;
	}
}

int stack_empty() {
	if (n_nodes == 0) {
		return 1;
	}
	else {
		return 0;
	}
}

void print_stack() {
	struct Node* temp = top;
	printf("\nStack: ");
	while (temp != NULL) {
		printf("%d ", temp->data);
		temp = temp->link;
	}
	printf("\n");
}

void push(int x) {
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
	// test if memory is failed
	if (temp == NULL) {
		printf("Memory allocation is failed.\n");
		exit(1);
	}
	temp->data = x;
	temp->link = top;
	top = temp;
	n_nodes++;
}

int pop() {
	// free a deleted (disconnected) node
	struct Node* temp = top;
	if (top == NULL) {
		printf("Stack is empty.\n");
		exit(1);
	}
	top = top->link;
	int x = temp->data;
	free(temp);
	n_nodes--;
	
	return x;
}

// helper function: run a series of pushes
// input arguments: int arr[] <- an array from which input values are taken
// input arguments: int num <- total number of elements to push
void run_pushes(int arr[], int num) {
	for (int i = 0; i < num; i++) {
		printf("push (%d)", arr[i]);

		if (!stack_full()) {
			push(arr[i]);
		}
		else {
			printf("\nStack full!");
			print_stack();
			break;
		}
		print_stack();
	}
}

// helper function: run a series of pops
// input argument: int num <- total number of elements to pop
void run_pops(int num) {
	for (int i = 0; i < num; i++) {
		printf("pop() ");
		if (!stack_empty()) { // if stack is not empty (!1 = 0)
			printf("-> %d", pop());
		}
		else {
			printf("Stack empty!");
			print_stack();
			break;
		}
		print_stack();
	}
}

int main() {
	int numbers[] = { 3, 9, 4, 5, 2, 1, 6, 8, 7, 5, 8 };
	
	print_stack();
	run_pushes(numbers, 5);
	run_pops(3);
	run_pushes(numbers, 10);
	run_pops(11);
	
	return 0;
}


Hw1-3

  • Implement and Test a Queue Program, Using
    a Singly Linked List.

  • The order of insert and delete is the same.
    Outputs the current stack or queue contents for each insert or delete)

Source Code

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 10

struct Node
{
    int data;
    struct Node* link;
};

struct Node* front = NULL; // front is empty initially
struct Node* rear = NULL; // rear is empty initially
int n_nodes = 0; // a variable to store number of nodes in queue

int queue_full() {
	if (n_nodes == MAX_SIZE) {
		return 1;
	}
	else {
		return 0;
	}
}
int queue_empty() {
	if (n_nodes == 0) {
		return 1;
	}
	else {
		return 0;
	}
}

void enqueue(int x) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    // test if memory is failed
    if (temp == NULL) {
        printf("Memory allocation is failed.\n");
        exit(1);
    }
	temp->data = x;
	temp->link = NULL;
	if (front == NULL && rear == NULL) {
		front = rear = temp;
		return;
	}
	rear->link = temp;
	rear = temp;
	n_nodes++;
}

int dequeue() {
    // free a deleted (disconnected) node
	struct Node* temp = front;
	if (front == NULL) {
		printf("Queue is empty\n");
		return -1;
	}
	if (front == rear) {
		front = rear = NULL;
	}
	else {
		front = front->link;
		
	}
	int x = temp->data;
	free(temp);
	n_nodes--;
	
	return x;
}

// helper function: traverse queue from front to rear and print elements
void print_queue() {
	struct Node* temp = front;
	printf("\nQueue: ");
	while (temp != NULL) {
		printf("%d ", temp->data);
		temp = temp->link;
	}
	printf("\n");
}

// helper function: run a series of enqueues
// input arguments: int arr[] <- an array from which input values are taken
// input arguments: int num <- total number of elements to push

void run_enqueues(int arr[], int num) {
	for (int i = 0; i < num; i++) {
		printf("enqueue(%d)", arr[i]);
		if (!queue_full()) {
			enqueue(arr[i]);
		}
		else {
			printf("\nqueue full!");
			print_queue();
			break;
		}
		print_queue();
	}
}

// helper function: run a series of pops
// input argument: int num <- total number of elements to pop
void run_dequeues(int num) {
	int value;
	for (int i = 0; i < num; i++) {
		printf("dequeue() ");
		if (!queue_empty()) {
			value = dequeue();
			printf("-> %d , ", value);
		}
		else {
			printf("queue empty! ");
			front = rear = NULL;
			print_queue();
			break;
		}
		print_queue();
	}
}

int main() {
	int numbers[] = { 3, 9, 4, 5, 2, 1, 6, 8, 7, 5, 8 };

	print_queue();
	run_enqueues(numbers, 5);
	run_dequeues(3);
	run_enqueues(numbers, 10);
	run_dequeues(11);
	run_enqueues(numbers, 11);

	return 0;
}


0개의 댓글