Implement Queue/Stack with Array
Prerequisite Knowledge
Before reading this article, you should first learn:
This article guides you through implementing queues and stacks using arrays as an underlying data structure.
Implementing a Stack with an Array
Let's start by implementing a stack with an array. This is straightforward—you use the end of a dynamic array as the top of the stack and call the dynamic array's API. Since adding and removing elements from the end of an array both have a time complexity of , it meets the requirements of a stack.
Note that I am using the ArrayList from the Java standard library here. If you prefer to use the MyArrayList that we implemented earlier, it will work in 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 an Array Serve as the Stack Top?
According to the logic we previously used to implement MyArrayList, it is not feasible. This is because adding or removing elements at the head of an array has a time complexity of , which does not meet the requirements.
However, we can utilize the CycleArray class implemented in the earlier section Circular Array Technique. This data structure allows adding and removing elements at the head with a time complexity of , which aligns with stack requirements.
You can directly use the addFirst and removeFirst methods of CycleArray to implement the stack API, so I won't write it here.
Implementing a Queue with an Array
With the CycleArray class from the earlier section Circular Array, using an array as the underlying data structure to implement a queue should not be difficult. By reusing our CycleArray, you can implement a standard queue. Of course, some programming languages have built-in circular array implementations, which you can search for and use:
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();
}
}