Answered: 1. Create a generic stack and queue…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

(my question and explanation is in one of the images)

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<assert.h>

typedef struct {

void* arr;

int totalSize;

int front;

int rear;

int elemSize;

void(*freefunc)(void*);

}queue;

void queueConstruct(queue* q, int elemSize, void(*freefunc)(void*)) {

q->elemSize = elemSize;

q->freefunc = freefunc;

q->totalSize = 5;

q->arr = malloc(q->totalSize * q->elemSize);

assert(q->arr != NULL);

q->front = -1;

q->rear = -1;

}

void queueDestruct(queue* q) {

if (q->freefunc != NULL) {

for (int i = 0; i < q->rear + 1; i++) {

q->freefunc((char*)q->arr + i * q->elemSize);

}

free(q->arr);

}

void freeString(void* pos) {

free(*(char**)pos);

}

void enqueue(queue* q, void* val) {

if (q->rear == q->totalSize - 1) {

q->totalSize *= 2;

q->arr = realloc(q->arr, q->totalSize * q->elemSize);

assert(q->arr != NULL);

}

q->rear++;

void* posiQueue = (char*)q->arr + q->rear * q->elemSize;

memcpy(posiQueue, val, q->elemSize);

}

int isEmpty(queue* q) {

return q->front == q->rear;

}

void dequeue(queue* q) {

assert(!isEmpty(q));

q->front++;

}

void frontQueue(queue* q, void* copy) {

assert(!isEmpty(q));

void* source = (char*)q->arr + (q->front + 1) * q->elemSize;

memcpy(copy, source, q->elemSize);

}

//Stack

typedef struct {

void* arr;

int elemSize;

int usedLength;

int totalLength;

void(*freefunc)(void*);

}stack;

void stackConstruct(stack* s, int elemSize, void(*freefunc)(void*)) {

s->freefunc = freefunc;

s->elemSize = elemSize;

s->usedLength = 0;

s->totalLength = 10;

s->arr = malloc(10 * s->elemSize);

assert(s->arr != NULL);

}

void stackDestruct(stack* s) {

if (s->freefunc != NULL) {

for (int i = 0; i < s->usedLength; i++)

s->freefunc((char*)s->arr + i * s->elemSize);

}

free(s->arr);

}

void freeStringStack(void* pos) {

free(*(char**)pos);

}

void push(stack* s, void* val) {

if (s->usedLength == s->totalLength) {

s->totalLength *= 2;

s->arr = realloc(s->arr, s->totalLength * s->elemSize);

assert(s->arr != NULL);

}

void* posStack = (char*)s->arr + s->usedLength * s->elemSize;

memcpy(posStack, val, s->elemSize);

s->usedLength++;

}

void top(stack* s, void* copy) {

assert(s->usedLength > 0);

void* source = (char*)s->arr + (s->usedLength - 1) * s->elemSize;

memcpy(copy, source, s->elemSize);

}

void pop(stack* s) {

assert(s->usedLength > 0);

s->usedLength--;

}

int isEmptyStack(stack* s) {

return s->usedLength == 0;

}

int main() {

queue q;

queueConstruct(&q, sizeof(int), NULL);

int visited[10] = { 0 };

//ABC

int graphFigure[10][10] = { {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 1, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 0, 1, 1},

// DEFG

{1, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 1, 1, 1, 0, 0} , {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 1, 0, 0, 1, 0, 0},

// HIJ

{0, 1, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}

};

/*int graphFigure[10][10] = { {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, {1,0,1, 0, 1, 0, 0}, {1,1,0, 1,

0, 0, 0},

{0,0,1, 0, 0, 0, 0}, {0,1,0, 0, 0, 1, 0} , { 0,1,1, 0, 1, 0, 1 }, { 0,0,0, 0,

0, 1, 0 }

};

int i = 0;

char c = 'A';

printf("%c ", c);

visited[i] = 1;

enqueue(&q, &i);

while (!isEmpty(&q)) {

int node;

frontQueue(&q, &node);

dequeue(&q);

for (int j = 0; j < 10; j++) {

if (graphFigure[node][j] == 1 && visited[j] == 0) {

switch (j){

case 0: c = 'A';

break;

case 1: c = 'B';

break;

case 2: c = 'C';

break;

case 3: c = 'D';

break;

case 4: c = 'E';

break;

case 5: c = 'F';

break;

case 6: c = 'G';

break;

case 7: c = 'H';

break;

case 8: c = 'I';

break;

case 9: c = 'J';

break;

default: c = 'd';

break;

}

printf("%c ", c);

visited[j] = 1;

enqueue(&q, &j);

}

printf("\n");

queueDestruct(&q);

printf("\n\n");

stack s;

stackConstruct(&s, sizeof(int), NULL);

int visited1[10] = { 0 };

//ABC

int graphFigure1[10][10] = { {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 1, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 0, 1, 1},

// DEFG

{1, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 1, 1, 1, 0, 0} , {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 1, 0, 0, 1, 0, 0},

// HIJ

{0, 1, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}

};

int i1 = 0;

char c1 = 'A';

printf("%c ", c1);

visited1[i] = 1;

push(&s, &i1);

while (!isEmptyStack(&s)) {

int node;

top(&s, &node);

pop(&s);

for (int j = 0; j < 10; j++) {

if (graphFigure1[node][j] == 1 && visited1[j] == 0) {

switch (j) {

case 0: c1 = 'A';

break;

case 1: c1 = 'B';

break;

case 2: c1 = 'C';

break;

case 3: c1 = 'D';

break;

case 4: c1 = 'E';

break;

case 5: c1 = 'F';

break;

case 6: c1 = 'G';

break;

case 7: c1 = 'H';

break;

case 8: c1 = 'I';

break;

case 9: c1 = 'J';

break;

default: c1 = 'd';

break;

}

printf("%c ", c1);

visited[j] = 1;

push(&s, &j);

}

printf("\n");

stackDestruct(&s);

return 0;

}

I am working on this question from the image. I do not know if the generic queue and depth first search
part of my assignment is outputting the correct order of elements based off of the diagram from the
problem, and something is wrong with the stack and breadth first search part of my code because it
keeps endlessly outputting and repeating the elements from the diagram in the image. Let me know
what is wrong with my stack code. My teacher used the graphfigure 10 by 10 array to show the
elements in the diagram and their relation to each other, with each set of 10 0's and 1s representing a
letter in the array, and the individual 1's and 0's showing that they are connected or not connected to
said letter. For example, the set of numbers in the element for B are {1, 0, 1, 0, 1, 0, 0, 1, 0, 0), meaning
that B is connected to A, C, E, and H as in the diagram in the picture. Here is my code for this problem, (I
am working in C language).

1. Create a generic stack and queue respectively. Write code in C.
2. In the following graph (Write code in C)
D
A
I
E
H
F
G
(i) Traverse using Depth First Search algorithm on the generic stack you have created. Start with vertex
A.
(ii)) Traverse using Breadth First Search algorithm on the generic queue you have created. Start with
vertex A.

Expert Solution

Step 1: Scope of the Question

The scope of the question is to provide a complete explanation and implementation of generic stack and queue data structures in the C programming language. The question asks for code examples, explanations, and a step-by-step breakdown of how to create these data structures using linked lists for flexibility. It also covers demonstrating the usage of these data structures by pushing and popping elements in the stack and enqueuing and dequeuing elements in the queue, including different data types.

The question is specifically focused on the following aspects:

Implementing a generic stack data structure in C.
2. Implementing a generic queue data structure in C.
3. Providing code examples for creating and using these data structures.
4. Offering a step-by-step explanation of the code.

Generic Stack:

A stack is a data structure that follows the last-in-first-out (LIFO) principle, meaning the most recently added element is the first to be removed.
A generic stack allows elements of any data type to be pushed onto the stack and popped off the stack without the need to specify the data type in advance.
Generic stacks are useful for a wide range of applications, such as managing function call states, parsing expressions, and reversing sequences of data.

Generic Queue:

A queue is a data structure that follows the first-in-first-out (FIFO) principle, meaning the first element added is the first to be removed.
A generic queue allows elements of any data type to be enqueued (added to the back of the queue) and dequeued (removed from the front of the queue) without requiring prior knowledge of the data type.
Generic queues are commonly used in scenarios like task scheduling, order processing, and managing data flows where the order of processing is critical.

Both generic stack and queue data structures are highly versatile and enable programmers to work with various data types in a consistent and reusable way, simplifying code and making it adaptable to different use cases. This flexibility is particularly valuable in programming languages that support generics or templates, as it allows developers to create highly adaptable and reusable code.

Note:

"Since you have posted a multiple questions , we will provide the solution only to the first question as per our Q&A guidelines. Please repost the remaining questions separately."

Step by step

Solved in 6 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

1. Create a generic stack and queue respectively. Write code in C.