Implement Queue/Stack with Array
Prerequisite Knowledge
Before reading this article, you should first learn:
This article will show you how to use arrays as the underlying data structure to implement queues and stacks.
Implementing a Stack with an Array
Let's first use an array to implement a stack. This is easy. You can treat the end of the dynamic array as the top of the stack, and just call the dynamic array's API. Adding or removing elements from the end of an array has time complexity , which fits the stack's requirements.
Here, I use Java's standard ArrayList. If you want to use the MyArrayList we implemented earlier, it works the same way:
// use array as the underlying data structure to implement stack
public class MyArrayStack<E> {
private ArrayList<E> list = new ArrayList<>();
// add element to the top of the stack, time complexity O(1)
public void push(E e) {
list.add(e);
}
// pop element from the top of the stack, time complexity O(1)
public E pop() {
return list.remove(list.size() - 1);
}
// peek the top element of the stack, time complexity O(1)
public E peek() {
return list.get(list.size() - 1);
}
// return the number of elements in the stack, time complexity O(1)
public int size() {
return list.size();
}
}// Implement stack using array as underlying data structure
#include <vector>
template<typename E>
class MyArrayStack {
private:
std::vector<E> list;
public:
// Push element onto stack, time complexity O(1)
void push(const E& e) {
list.push_back(e);
}
// Pop element from stack, time complexity O(1)
E pop() {
E topElement = list.back();
list.pop_back();
return topElement;
}
// Peek at top element, time complexity O(1)
E peek() const {
return list.back();
}
// Return the number of elements in stack, time complexity O(1)
int size() const {
return list.size();
}
};# Implement stack using array as the underlying data structure
class MyArrayStack:
def __init__(self):
self.list = []
# Add element to the top of the stack, time complexity O(1)
def push(self, e):
self.list.append(e)
# Pop element from the top of the stack, time complexity O(1)
def pop(self):
return self.list.pop()
# Peek at the top element of the stack, time complexity O(1)
def peek(self):
return self.list[-1]
# Return the number of elements in the stack, time complexity O(1)
def size(self):
return len(self.list)import "fmt"
// MyArrayStack uses a slice as the underlying data structure to implement a stack
type MyArrayStack[T any] struct {
list []T
}
// Add an element to the top of the stack, time complexity O(1)
func (s *MyArrayStack[T]) Push(e T) {
s.list = append(s.list, e)
}
// Pop an element from the top of the stack, time complexity O(1)
func (s *MyArrayStack[T]) Pop() T {
if len(s.list) == 0 {
var zero T
return zero
}
e := s.list[len(s.list)-1]
s.list = s.list[:len(s.list)-1]
return e
}
// View the top element of the stack, time complexity O(1)
func (s *MyArrayStack[T]) Peek() T {
if len(s.list) == 0 {
var zero T
return zero
}
return s.list[len(s.list)-1]
}
// Return the number of elements in the stack, time complexity O(1)
func (s *MyArrayStack[T]) Size() int {
return len(s.list)
}// Implement stack using array as the underlying data structure
class MyArrayStack {
constructor() {
this.list = [];
}
// Add element to the top of the stack, time complexity O(1)
push(e) {
this.list.push(e);
}
// Pop element from the top of the stack, time complexity O(1)
pop() {
return this.list.pop();
}
// Peek the top element of the stack, time complexity O(1)
peek() {
return this.list[this.list.length - 1];
}
// Return the number of elements in the stack, time complexity O(1)
size() {
return this.list.length;
}
}Can the head of the array be used as the stack top?
With the way we implemented MyArrayList before, it's not possible. Adding or removing elements at the head of an array has time complexity , which does not fit the stack's requirements.
But you can use the CycleArray class introduced in Circular Array Technique. In this data structure, adding or removing elements at the head has time complexity , which fits the stack's requirements.
Just call CycleArray's addFirst and removeFirst methods to implement the stack API. I won't write the code here.
Implementing a Queue with an Array
With the CycleArray class from Circular Array Technique, it is not hard to use an array to implement a queue. Just reuse the CycleArray we made, and you can get a standard queue. Some programming languages also have built-in circular array implementations. You can also look for and use them:
public class MyArrayQueue<E> {
private CycleArray<E> arr;
public MyArrayQueue() {
arr = new CycleArray<>();
}
public void push(E t) {
arr.addLast(t);
}
public E pop() {
return arr.removeFirst();
}
public E peek() {
return arr.getFirst();
}
public int size() {
return arr.size();
}
}#include <iostream>
#include <deque>
template <typename E>
class MyArrayQueue {
private:
CycleArray<E> arr;
public:
MyArrayQueue() {
arr = CycleArray<E>();
}
void push(E t) {
arr.addLast(t);
}
E pop() {
return arr.removeFirst();
}
E peek() {
return arr.getFirst();
}
int size() {
return arr.size();
}
};class MyArrayQueue:
def __init__(self):
self.arr = CycleArray()
def push(self, t):
self.arr.add_last(t)
def pop(self):
return self.arr.remove_first()
def peek(self):
return self.arr.get_first()
def size(self):
return self.arr.size()type MyArrayQueue[E any] struct {
arr *CycleArray[E]
}
func NewMyArrayQueue[E any]() *MyArrayQueue[E] {
return &MyArrayQueue[E]{
arr: NewCycleArray[E](),
}
}
func (q *MyArrayQueue[E]) Push(t E) {
q.arr.AddLast(t)
}
func (q *MyArrayQueue[E]) Pop() E {
return q.arr.RemoveFirst()
}
func (q *MyArrayQueue[E]) Peek() E {
return q.arr.GetFirst()
}
func (q *MyArrayQueue[E]) Size() int {
return q.arr.Size()
}class MyArrayQueue {
constructor() {
this.arr = new CycleArray();
}
push(t) {
this.arr.addLast(t);
}
pop() {
return this.arr.removeFirst();
}
peek() {
return this.arr.getFirst();
}
size() {
return this.arr.size();
}
}