Stacks and Queues for app.codility.com/programmers Explained in Go
Category of Article : Technology | Computers and Software | Algorithms
By: Chrysanthus Date Published: 4 Jul 2025
Stack
The stack container (or stack for short), 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.
Go does not have a stack container (data structure), so the Go slice which is more of a data structure than an array, is used. So, instead of using the pop() method, the Go s[:len(s)-1] scheme is used, where 's' is the slice. When the slice is used as a stack, the append(original_slice, element_to_add) scheme is used instead of the push() method.
Use of s[:len(s)-1] and append(original_slice, element_to_add) schemes for the Stack
The following program pushes at the end, the list of integers,4, 8, 6, 3
one-by-one onto a stack, and then pops them out one-by-one from the top (actually bottom) 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 program is:
package main
import (
"fmt";
)
func main() {
stack := make([]int, 0);
stack = append(stack, 4); stack = append(stack, 8); stack = append(stack, 6); stack = append(stack, 3);
var int1 int = stack[len(stack)-1]; stack = stack[:len(stack)-1];
var int2 int = stack[len(stack)-1]; stack = stack[:len(stack)-1];
var int3 int = stack[len(stack)-1]; stack = stack[:len(stack)-1];
var int4 int = stack[len(stack)-1]; stack = stack[:len(stack)-1];
fmt.Println(int1, int2, int3, int4);
}
The output is: 3, 6, 8, 4
in reverse order, as expected, since it is last-in-first-out. The top() expression (stack[len(stack)-1]) copies out the last (top) element, while the pop() statement (stack = stack[:len(stack)-1]) removes the last (top) element and "throws it away". Note: The push() or top() or pop() method takes O(1) time. The sequence of operations for the whole list takes O(n) time, with pushing or with popping.
Queue
The queue container (or queue for short), is a data structure in which a new element is inserted at the back, but an old element is removed from the front, in order. 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, 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.Go does not have a queue container (data structure), so the Go slice which is more of a data structure than an array, is used. So, instead of using the pop() method, the Go (queue = queue[1:]) statement is used. Since the slice push() method pushes element at the back of the slice, the same (queue = append(queue, 4);) statement is used when the slice is considered as a queue.
Use of queue = append(queue, 4) and queue = queue[1:] schemes for the Queue
The following program pushes the list of integers,4, 8, 6, 3
one-by-one into a queue from the back, and then pops them out one-by-one from the front (top) 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 program is:
package main
import (
"fmt";
)
func main() {
queue := make([]int, 0);
queue = append(queue, 4); queue = append(queue, 8); queue = append(queue, 6); queue = append(queue, 3);
var int1 int = queue[0]; queue = queue[1:];
var int2 int = queue[0]; queue = queue[1:];
var int3 int = queue[0]; queue = queue[1:];
var int4 int = queue[0]; queue = queue[1:];
fmt.Println(int1, int2, int3, int4);
}
The output is:4, 8, 6, 3
in same order, as expected, since it is first-in-first-out. The top() method (queue[0]) copies out the first (top) element, while the pop() method (queue = queue[1:]) removes the first(top) element and "throws it away". Note: The push() or top() or pop() method takes O(1) time. The sequence of operations for the whole list takes O(n) time, with pushing or with popping.
The length function for the Stack and the Queue
The len() function can be used for the stack or queue object (slice). This returns the length of the stack or queue object. The following program illustrates this:
package main
import (
"fmt";
)
func main() {
stack := make([]int, 0);
stack = append(stack, 4); stack = append(stack, 8); stack = append(stack, 6); stack = append(stack, 3);
queue := make([]int, 0);
queue = append(queue, 4); queue = append(queue, 8); queue = append(queue, 6); queue = append(queue, 3);
fmt.Println("The size of the stack is: ", len(stack), " and the size of the queue is: ", len(queue));
}
The output is:The size of the stack is: 4 and the size of the queue is: 4