Implement Queue/Stack with Array
In this article, we will use arrays as the basic data structure to implement stacks and queues.
Implementing Stack Using Array
Let's first use an array to implement a stack. This is simple. Treat the end of the dynamic array as the top of the stack, then just call the dynamic array's API. Adding or removing elements at the end of an array takes time, which fits the stack's requirements.
Here I use the standard library's dynamic array. If you want to use the MyArrayList we made before, it works the same way:
// use array as the underlying data structure to implement stack
public class MyArrayStack<E> {
private ArrayList<E> arr = new ArrayList<>();
// add element to the top of the stack, time complexity O(1)
public void push(E e) {
arr.add(e);
}
// pop element from the top of the stack, time complexity O(1)
public E pop() {
return arr.remove(arr.size() - 1);
}
// peek the top element of the stack, time complexity O(1)
public E peek() {
return arr.get(arr.size() - 1);
}
// return the number of elements in the stack, time complexity O(1)
public int size() {
return arr.size();
}
}// Implement stack using array as underlying data structure
#include <vector>
template<typename E>
class MyArrayStack {
private:
std::vector<E> arr;
public:
// Push element onto stack, time complexity O(1)
void push(const E& e) {
arr.push_back(e);
}
// Pop element from stack, time complexity O(1)
E pop() {
E topElement = arr.back();
arr.pop_back();
return topElement;
}
// Peek at top element, time complexity O(1)
E peek() const {
return arr.back();
}
// Return the number of elements in stack, time complexity O(1)
int size() const {
return arr.size();
}
};# Implement stack using array as the underlying data structure
class MyArrayStack:
def __init__(self):
self.arr = []
# Add element to the top of the stack, time complexity O(1)
def push(self, e):
self.arr.append(e)
# Pop element from the top of the stack, time complexity O(1)
def pop(self):
return self.arr.pop()
# Peek at the top element of the stack, time complexity O(1)
def peek(self):
return self.arr[-1]
# Return the number of elements in the stack, time complexity O(1)
def size(self):
return len(self.arr)import "fmt"
// MyArrayStack uses a slice as the underlying data structure to implement a stack
type MyArrayStack[T any] struct {
arr []T
}
// Add an element to the top of the stack, time complexity O(1)
func (s *MyArrayStack[T]) Push(e T) {
s.arr = append(s.arr, e)
}
// Pop an element from the top of the stack, time complexity O(1)
func (s *MyArrayStack[T]) Pop() T {
if len(s.arr) == 0 {
var zero T
return zero
}
e := s.arr[len(s.arr)-1]
s.arr = s.arr[:len(s.arr)-1]
return e
}
// View the top element of the stack, time complexity O(1)
func (s *MyArrayStack[T]) Peek() T {
if len(s.arr) == 0 {
var zero T
return zero
}
return s.arr[len(s.arr)-1]
}
// Return the number of elements in the stack, time complexity O(1)
func (s *MyArrayStack[T]) Size() int {
return len(s.arr)
}// Implement stack using array as the underlying data structure
class MyArrayStack {
constructor() {
this.arr = [];
}
// Add element to the top of the stack, time complexity O(1)
push(e) {
this.arr.push(e);
}
// Pop element from the top of the stack, time complexity O(1)
pop() {
return this.arr.pop();
}
// Peek the top element of the stack, time complexity O(1)
peek() {
return this.arr[this.arr.length - 1];
}
// Return the number of elements in the stack, time complexity O(1)
size() {
return this.arr.length;
}
}Can We Use the Head of the Array as the Stack Top?
According to the way we implemented MyArrayList before, it's not possible. Adding or removing elements at the head of an array takes time, which is not good for a stack.
But we can use the CycleArray class from Circular Array Technique. In this data structure, adding and removing elements at the head takes time, which fits the stack's needs.
You can use the addFirst and removeFirst methods of CycleArray to make stack APIs. I won't write the code here.
Implementing Queue Using Array
With the CycleArray class from Circular Array Technique, using an array to build a queue is simple. Just use the CycleArray we wrote before, and you can get a standard queue. Of course, some programming languages also have built-in circular arrays, feel free to use them as well:
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();
}
}