Creating and Using Stack and Queue in C for app.codility.com/programmers
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 3 Jul 2025
Stack
The stack, is a data structure in which the insertion of a new element takes place at the top, and the deletion (removal) of an element, also takes place from the top. The idea of the stack can be illustrated by plates stacked on top of one another. Each new plate is placed on top of the stack of plates (operation push), and plates can only be taken off the top of the stack (operation pop). This is a Last-In-First-Out (LIFO) data structure. An additional method for this tutorial is top(). The top() method reads out (reads and returns) the element at the top (effectively reading and returning the last element). The top is actually the end of the stack (and not the front, while the front is the bottom).There is an attribute for the stack, called size. It returns the length (number of elements) for the stack.
Creating a Stack
The basic structure of the stack is a C struct. It has the size attribute that will be initialized to 0 in the main() function. It has the method declarations. Each element is also a struct, consisting of a fundamental data type and a pointer that points to the previous element. The fundamental data type used in this tutorial is an integer. If the previous element does not exist, then the pointer is a null pointer (assigned the value of 0).A new element is obtained from free store, using dynamic memory techniques.
The Stack Element and Stack Declarations
The first part of the program is:#include <stdio.h>Read through the code if that is not already done. The stdio.h header is included in the program, in order to access free store.
#include <stdlib.h>
struct Element {
int value;
struct Element *previous;
};
struct Stack {
int size;
struct Element *back;
int (*top)();
void (*push)(int);
void (*pop)();
} stack;
"Stack" is a general purpose stack, while "stack" is a particular object stack.
Stack Method (function) Definitions
The definitions of the Stack methods are as follows: int top() {
if (stack.size > 0) //stack has at least 1 element
return stack.back->value; //use -> to obtain value from a pointer
else
printf("Error: No element to remove from stack!\n");
}
void push(int inte) {
struct Element *element = malloc(sizeof(struct Element)); //declaring and creating the object, element
if (element != 0) { //check whether allocation of memory element was successful
element->value = inte;
if (stack.size == 0) { //first element
element->previous = 0;
stack.back = element;
stack.size = stack.size + 1; //add 1 to size
}
else {
element->previous = stack.back; //previous points to previous element
stack.back = element; //stack points to new element
stack.size = stack.size + 1; //add 1 to size
}
}
else {
printf("Error: New element could not be created!\n");
exit(1);
}
}
void pop() {
if (stack.size > 0) { //stack has at least 1 element
struct Element *lastElement = stack.back;
stack.back = lastElement->previous; //point to previous element
free(lastElement); //free last (top) element from memory
stack.size = stack.size - 1; //subtract 1 from size
}
else {
printf("Error: No element to remove from stack!\n");
exit(1);
}
}Read through the code (and comments) if that is not already done. These definitions go below the above part of the program.The C main() Function for the Program
The main() function for the program so far is:int main(int argc, char **argv)The first part of the main() function assigns 0 (initializing) to the size attribute of the stack, and connects (assigns) the function definitions to the function (method) declarations of the stack (somewhat initializing).
{
//Assigning stack attributes and methods (functions)
stack.size = 0;
stack.top = top;
stack.push = push;
stack.pop = pop;
/*
The code to serve the user goes here.
*/
return 0;
}
Use of push() and pop() methods for the Stack
The following code pushes the list of integers,4, 8, 6, 3
one-by-one into the stack, and then pops them out one-by-one from the top of the stack. The stack begins with the number 4 and then ends with the number 3. So, in the popping operations, 3 will be sent out first. The code in the C main() function is:
int main(int argc, char **argv)The output is:
{
//Assigning stack attributes and methods (functions)
stack.size = 0;
stack.top = top;
stack.push = push;
stack.pop = pop;
//user code begins
stack.push(4); stack.push(8); stack.push(6); stack.push(3);
int int1 = stack.top(); stack.pop();
int int2 = stack.top(); stack.pop();
int int3 = stack.top(); stack.pop();
int int4 = stack.top(); stack.pop();
printf("%i, ", int1); printf("%i, ", int2); printf("%i, ", int3); printf("%i, ", int4); printf("\n");
//user code begins
return 0;
}
3, 6, 8, 4,
in reverse order, as expected, since it is last-in-first-out. The top() method copies out the last (top) element, while the pop() method removes the last (top) element and throws it away. pop() returns void. push() also returns void. Note the use of the dot operator, between the name, stack and the method, push() or top() or pop().
Note as well: The push() or top() or pop() method takes O(1) time. Though the push() method looks long, only a short code segment is executed each time. The sequence of operations for the whole list takes O(n) time, with pushing or with popping.
Illustrating the Use of the Size of the stack
For this tutorial, a stack has the size attribute. This returns the length of the stack object. The following program illustrates this (only main() function is provided):int main(int argc, char **argv)
{
//Assigning stack attributes and methods (functions)
stack.size = 0;
stack.top = top;
stack.push = push;
stack.pop = pop;
//user code begins
stack.push(4); stack.push(8); stack.push(6); stack.push(3);
printf("The size of the stack is: %i\n", stack.size);
//user code begins
return 0;
}
The output is
The size of the stack is: 4
Queue
The queue is a data structure in which a new element is inserted at the back, but the oldest element is removed from the front. The idea of the queue can be illustrated by a line of customers at a grocery store. New people join the back of the queue (push operation) and the next person to be served (and leave), is the one in front (pop operation), of the line (queue). After serving, he/she goes away. This is a First-In-First-Out (FIFO) data structure.More people can be served and leave than more people enter at the back. More people can enter at the back than more people leave at the front.
If the queue is to be compared to the stack, then the bottom is the front. So, instead of the top() method that reads out (reads and returns) the last element at the top, there is the front() method that reads and returns the first element at the bottom. Each Element struct now has a previous and next attribute; and each Queue struct has a back and front (actually first) attribute.
Creating a Queue
The basic structure of the queue is a C struct. It has the size attribute that will be initialized to 0 in the main() function. It has the method declarations. Each element is also a struct, consisting of a fundamental data type and two pointers that point to the next and previous elements. The fundamental data type used in this tutorial is an integer. If the next element does not exist, then the pointer is a null pointer (assigned the value of 0). If the previous element does not exist, then the pointer is also a null pointer (assigned the value of 0).A new element is obtained from free store, using dynamic memory techniques.
The Queue Element and Queue Declarations
The first part of the program is:
#include <stdio.h>Read through the code if that is not already done. The stdio.h header is included in the program, in order to access free store.
#include <stdlib.h>
struct Element {
int value;
struct Element *next;
struct Element *previous;
};
struct Queue {
int size;
struct Element *first;
struct Element *back;
int (*front)();
void (*push)(int);
void (*pop)();
} queue;
"Queue" is a general purpose queue, while "queue" is a particular object queue.
Queue Method (function) Definitions
The definitions of the Queue methods are as follows: int front() {
if (queue.size > 0) //queue has at least 1 element
return queue.first->value; //use -> to obtain value from a pointer
else
printf("Error: No element to remove from queue!\n");
}
void push(int inte) {
struct Element *element = malloc(sizeof(struct Element)); //declaring and creating the object, element
if (element != 0) { //check whether allocation of memory element was successful
element->value = inte;
if (queue.size == 0) { //first element
element->next = 0;
element->previous = 0;
queue.first = element;
queue.back = element;
queue.size = queue.size + 1; //add 1 to size
}
else {
element->next = queue.back; //next points to next element
struct Element *lastButOneElement = queue.back; //new last-But-One-Element
lastButOneElement->previous = element;
element->previous = 0; //new last element at the back
queue.back = element;
queue.size = queue.size + 1; //add 1 to size
}
}
else {
printf("Error: New element could not be created!\n");
exit(1);
}
}
void pop() {
if (queue.size > 0) { //queue has at least 1 element
struct Element *firstElement = queue.first;
queue.first = firstElement->previous; //point to previous element
free(firstElement); //free first (top) element from memory
queue.size = queue.size - 1; //subtract 1 from size
}
else {
printf("Error: No element to remove from queue!\n");
exit(1);
}
}
Read through the code (and comments) if that is not already done. These definitions go below the above part of the program.
The C main() Function for the Program
The main() function for the Queue program so far is:int main(int argc, char **argv)
{
//Assigning queue attributes and methods (functions)
queue.size = 0;
queue.front = front;
queue.push = push;
queue.pop = pop;
/*
The code to serve the user goes here.
*/
return 0;
}
Use of push() and pop() methods for the Queue
The following program pushes the list of integers,4, 8, 6, 3
one-by-one into a queue, and then pops them out one-by-one from top (front) of the queue. The queue begins with the number 4 and then ends with the number 3. So, in the popping operations, 4 will be sent out first. The code in the C main() function is:
int main(int argc, char **argv)The output is:
{
//Assigning queue attributes and methods (functions)
queue.size = 0;
queue.front = front;
queue.push = push;
queue.pop = pop;
//user code begins
queue.push(4); queue.push(8); queue.push(6); queue.push(3);
int int1 = queue.front(); queue.pop();
int int2 = queue.front(); queue.pop();
int int3 = queue.front(); queue.pop();
int int4 = queue.front(); queue.pop();
printf("%i, ", int1); printf("%i, ", int2); printf("%i, ", int3); printf("%i, ", int4); printf("\n");
//user code begins
return 0;
}
4, 8, 6, 3,
in same order, as expected, since it is first-in-first-out. The front() method copies out the first (top) element, while the pop() method removes the first (front) element and throws it. pop() returns void. push() also returns void. Note the use of the dot operator, between the name, queue and the method, push() or front() or pop().
Note as well: The push() or front() or pop() method takes O(1) time. Though the push() method looks long, only a short code segment is executed each time. The sequence of operations for the whole list takes O(n) time, with pushing or with popping.
Illustrating the Use of the Size of the queue
For this tutorial, a queue has the size attribute. This returns the length of the queue object. The following program illustrates this (only main() function is provided):int main(int argc, char **argv)The output is
{
//Assigning queue attributes and methods (functions)
queue.size = 0;
queue.front = front;
queue.push = push;
queue.pop = pop;
//user code begins
queue.push(4); queue.push(8); queue.push(6); queue.push(3);
printf("The size of the queue is: %i\n", queue.size);
//user code begins
return 0;
}
The size of the queue is: 4