/*
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;
}
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)
#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;
}
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)
#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;
}