Last active
August 8, 2019 02:13
-
-
Save luoheng23/29d08d622dc39f7243485b4431318a0a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Quack.c: an array-based implementation of a quack | |
#include <stdio.h> | |
#include <stdlib.h> | |
typedef struct node *Quack; | |
Quack createQuack(void); // create and return Quack | |
Quack destroyQuack(Quack); // remove the Quack | |
void push(int, Quack); // put int on the top of the quack | |
void qush(int, Quack); // put int at the bottom of the quack | |
int pop(Quack); // pop and return the top element on the quack | |
int isEmptyQuack(Quack); // return 1 is Quack is empty, else 0 | |
void makeEmptyQuack(Quack);// remove all the elements on Quack | |
void showQuack(Quack); // print the contents of Quack, from the top down | |
#define HEIGHT 1000 | |
struct node { | |
int array[HEIGHT]; | |
int top; | |
}; | |
Quack createQuack(void) { | |
Quack qs; | |
qs = malloc(sizeof(struct node)); | |
if (qs == NULL) { | |
fprintf (stderr, "createQuack: no memory, aborting\n"); | |
exit(1); // should pass control back to the caller | |
} | |
qs->top = -1; | |
return qs; | |
} | |
void push(int data, Quack qs) { | |
if (qs == NULL) { | |
fprintf(stderr, "push: quack not initialised\n"); | |
} | |
else { | |
if (qs->top >= HEIGHT-1) { | |
fprintf(stderr, "push: quack overflow\n"); | |
} | |
else { | |
++qs->top; | |
qs->array[qs->top] = data; | |
} | |
} | |
return; | |
} | |
void qush(int data, Quack que) { // adds data to the bottom of the array | |
if (que == NULL) { | |
fprintf(stderr, "qush: quack not initialised\n"); | |
} | |
else { | |
if (que->top >= HEIGHT-1) { | |
fprintf(stderr, "qush: quack overflow\n"); | |
} | |
else { | |
++que->top; // next available spot | |
int i; | |
for (i=que->top; i>=1; i--) { | |
que->array[i] = que->array[i-1];// move each element up 1 | |
} | |
que->array[0] = data; | |
} | |
} | |
return; | |
} | |
int pop(Quack qs) { // return top element, or 0 if error | |
int retval = 0; | |
if (qs == NULL) { | |
fprintf(stderr, "pop: quack not initialised\n"); | |
} | |
else { | |
if (isEmptyQuack(qs)) { | |
fprintf(stderr, "pop: quack underflow\n"); | |
} | |
else { | |
retval = qs->array[qs->top]; // top element on stack | |
--qs->top; | |
} | |
} | |
return retval; | |
} | |
void makeEmptyQuack(Quack qs) { | |
if (qs == NULL) { | |
fprintf(stderr, "makeEmptyQuack: quack not initialised\n"); | |
} | |
else { | |
while (!isEmptyQuack(qs)) { | |
pop(qs); | |
} | |
} | |
return; | |
} | |
Quack destroyQuack(Quack qs) { | |
if (qs == NULL) { | |
fprintf(stderr, "destroyQuack: quack not initialised\n"); | |
} | |
free(qs); | |
return qs; | |
} | |
int isEmptyQuack(Quack qs) { | |
int empty = 0; | |
if (qs == NULL) { | |
fprintf(stderr, "isEmptyQuack: quack not initialised\n"); | |
} | |
else { | |
empty = qs->top < 0; | |
} | |
return empty; | |
} | |
void showQuack(Quack qs) { | |
if (qs == NULL) { | |
fprintf(stderr, "showQuack: quack not initialised\n"); | |
} | |
else { | |
printf("Quack: "); | |
if (qs->top < 0) { | |
printf("<< >>\n"); | |
} | |
else { | |
int i; | |
printf("<<"); // start with a << | |
for (i = qs->top; i > 0; --i) { | |
printf("%d, ", qs->array[i]); // print each element | |
} | |
printf("%d>>\n", qs->array[0]); // last element includes a >> | |
} | |
} | |
return; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment