We already know about basic data types such as int, double, and char; as well as
ID: 3804390 • Letter: W
Question
We already know about basic data types such as int, double, and char; as well as data structures such as C strings and arrays, but there are more advanced data structures frequently employed in programing to do common tasks, the most common of which are given names. Three of the most extensively used ones are the linked list, stack, and queue. For this program we will be implementing a stack data structure and running a simple test with it. The most versatile of stacks are implemented with the underlying data structure being a linked list but for simple purposes it is perfectly acceptable to implement a stack with an array as the data structure and since we do not have all the material to construct a linked list an array will have to do. This is a fairly challenging problem as normally assigned in a CS class which is why it typically occurs in a later class, but we have simplified it considerably and will be providing skeleton code for you to use. Instead of the malloc() function call to allocate memory as learned in the lab over dynamic memory it is imperative that you use the realloc() function instead. The following links to information about stack data structures and the relloc() function call may be useful for you: 1. This link is to the Wikipedia page about a stack data structure in general you will find it useful if you need help visualizing how a stack actually works https://en.wikipedia.org/wiki/Stack_(abstract_data_type) 2. This link is to an online reference manual about functions in C it also provides an example to see how to use the realloc() function call http://en.cppreference.com/w/c/memory/realloc 3. This link is to another online reference that in my opinion is a little easier to read and understand, it also covers the C++ language in addition to C but this function is the same in both language so it is not an issue, it provides yet another example of how to use the realloc() function call http://www.cplusplus.com/ reference/cstdlib/realloc/ Implement these functions: void push(int item); void pop(int *item); void print_stack(); Finally sum assumptions you may make for the purposes of this problem on this assignment only. You may assume that if pop is called that there is already a value inside the array to pop out, meaning there will be NO calls to pop from an empty array. 7 Here is an example of the program output (I omitted menu after the first printing to save space). 1: Push Operation 2: Pop Operation 3: Print Stack 4: Exit Program 1 Enter number to push: 1 1 Enter number to push: 2 1 Enter number to push: 3 3 Printing stack: 1 2 3 2 Number poped is: 3 3 Printing stack: 1 2 4
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
//global variables
//plz comment on code
//This is a pointer to a memory address that will serve as the starting location of the dynamically created array, it needs to be initilized to NULL for realloc to work the first time.
int counter = 0;
//int array[5];
int array[100];
//This is your typical SIZE variable used to denote the size of the array, it will be increased or decremented with push and pop respectivly. It is initilized to 0 because the array has no elements to begin with.
int top = -1;
//This variable is the location of the top of our stack or in simplilar terms the element we want to treat as the first element in the array. It starts at -1 so that it can be 0 when we have a 1 element size array after the first push operation.
//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
//Function prototypes
void push(int item);
//The purpose of this function is to insert a new value into the stack, it takes one integer by value and operates on the global stack array. You will need to increase the size of the array and dynamically reallocate the size of the array based onthe new size variable as well as change the top of the stack position with the top variable.
void pop(int *item);
//The purpose of this function is to remove an item from the stack, it takes one integer by refrence and operates on the global stack array. You will need to access the top of the array and get the value to return by refrence and decrement the top and counter global variables before rellocating the dynamic array with the realloc function call based on the new size.
void print_stack();
//This function simply loops throug the array with a standard for loop until counter which is being used as a size variable, it takes no arguments since the array is global and returns nothing, it simply uses printf to print the array out for testing purposes.
//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
int main()
{
int return_value = 0;
//This variable serves as a holder for the value returned via a pop operation.
int choice = -1;
//This variable serves as a holder for user choice in the menu.
while(1) //infinate loop to handle menu operations
{
printf("1: Push Operation ");
printf("2: Pop Operation ");
printf("3: Print Stack ");
printf("4: Exit Program ");
scanf("%d", &choice);
//Simple menu with scanf choice to prompt user for desired operation
if(choice == 1) //push operation
{
int pushNum = -1;
//Value to prompt user for to be used in push operation.
printf("Enter number to push: ");
scanf("%d", &pushNum);
//array=(int *)malloc(sizeof(int));
push(pushNum);
}
else if(choice == 2) //Pop operation
{
int popNum = -1;
//variable to store the value recieved from the pop operation.
pop(&popNum);
printf("Number poped is: %d ", popNum);
}
else if(choice == 3)//print operation
{
printf("Printing stack: ");
print_stack();
}
else if(choice == 4)//Exit program here
{
//free(array);
return 0;
}
else //error handler
{
printf("Invalid Selection ");
}
}
}
//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
void push(int item)
{
top = top + 1;
array[top]=item;
}
//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
void pop(int *item)
{
int num;
if(top==-1)
{
printf ("Stack is Empty ");
}
else
{
num=array[top];
top--;
*item=num;
}
}
//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
void print_stack()
{ int i;
if (top == -1)
{
printf ("Stack is empty ");
return;
}
else
{
printf (" The content of the stack is ");
for (i = top; i > 0; i--)
{
printf ("%d ", array[i]);
}
printf("%d",array[0]);
}
printf (" ");
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.