Linked Stacks and Queues

Linked Stacks

Stacks can be implemented using a linked list. The Push operation is implemented by inserting element at the beginning of the list. Pop operation, on the other hand is implemented by deleting the node from the beginning (the header/top node).

struct Node{

int data;

struct Node *next;

};

struct Stack* CreateStack() {

return NULL;

}

void Push (struct Stack **top, int data) {

struct Stack *temp;

temp = malloc(sizeof(struct Stack));

if (!temp) return NULL;

temp -> data = data;

temp -> next = *top;

*top = temp;

}

int isEmptyStack(struct Stack *top) {

return top == NULL;

}

int Pop(struct Stack **top) {

int data;

struct Stack *temp;

if(isEmptyStack(top)) return INT_MIN;

temp = *top;

*top = *top -> next;

data = temp -> data;

free(temp);

return data;

}

int Top(struct Stack *top) {

if(isEmptyStack(top)) return INT_MIN;

return top -> next -> data;

}

void deleteStack(struct Stack **top) {

struct Stack *temp, *p;

p = *top;

while (p -> next) {

temp = p - > next;

p -> next = temp -> next;

free(temp);

}

free(p);

}

Linked Queues

Queues can be implemented using linked lists. The Enqueue operation is implemented by inserting element at the end of the list. Dequeue operation, on the other side is implemented by deleting an element from the beginning of the list.

struct Node {

int data;

struct Node* next;

};

struct Queue {

struct Node *front;

struct Node *rear;

};

struct Queue *createQueue() {

struct Queue *Q;

struct Node *temp;

Q = malloc(sizeof(struct Queue));

if(!Q) return NULL;

temp = malloc(sizeof(struct Node));

Q -> front = Q -> rear = NULL;

return Q;

}

int isEmpty(struct Queue *Q) {

// if the condition is true then 1, else 0 is returned

return (Q -> front == NULL);

}

void enqueue(struct Queue *Q, int data) {

struct Node *newNode;

newNode = malloc(sizeof(struct Node));

if(!newNode) return NULL;

newNode -> data = data;

newNode -> next = NULL;

Q -> rear -> next = newNode;

Q -> rear = newNode;

if(Q -> front == NULL)

Q -> front = Q -> rear;

}

int dequeue(struct Queue *Q) {

int data = 0;

struct Node *temp;

if(isEmptyQueue(Q)) {

printf("Queue is empty");

return 0;

}

else {

temp = Q -> front;

data = Q -> front -> data;

Q -> front = Q -> front -> next;

free(temp);

}

return data;

}

void deleteQueue(struct Queue *Q) {

struct Node *temp;

while(Q) {

temp = Q;

Q = Q -> next;

free(temp);

}

free(Q);

}

References:

1. Karumanchi, N. "Data Structures and Algorithms Made Easy"

2. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

3. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”