What is the most efficient way to implement a stack and queue using one array?

1 Why use one array?

You might wonder why you would want to use one array to implement both a stack and a queue, instead of using two separate arrays. One reason is to save memory space, especially if you have limited or fixed-size memory. Another reason is to simplify the code and avoid unnecessary duplication of data. Using one array also allows you to easily switch between the stack and queue operations, depending on your needs.

2 How to use one array?

The basic idea of using one array to implement a stack and a queue is to divide the array into two parts: one for the stack and one for the queue. The stack part uses the end of the array as the top, and the queue part uses the beginning and the end of the array as the front and rear, respectively. To avoid overlapping, you need to keep track of the indexes of the top, front, and rear of the array.

3 Stack operations

To implement the stack operations, you need to use the push, pop, peek, isEmpty, and isFull methods. Push adds an element to the top of the stack, if there is enough space in the array and increment the top index by one. Pop removes and returns the element at the top of the stack, if the stack is not empty. Peek returns the element at the top of the stack without removing it. IsEmpty returns true if the stack is empty and false otherwise. IsFull returns true if the stack is full and false otherwise. The stack is full when the top index is equal to the front index of the queue and empty when the top index is -1.

4 Queue operations

To implement the queue operations, you must use the enqueue(element) method to add an element to the rear of the queue, while incrementing the rear index by one and wrapping it around if it reaches the end of the array. The dequeue() method removes and returns the element at the front of the queue, while incrementing the front index by one and wrapping it around if it reaches the end of the array. The front() method returns the element at the front of the queue without removing it, while isEmpty() returns true if the queue is empty and isFull() returns true if it is full. A queue is full when either its rear index is one less than its front index or when its rear index is at the end of the array and its front index is at its beginning. Conversely, a queue is empty when its front index is equal to its rear index.

5 Code example

Here is a possible code example of how to implement a stack and queue using one array in Java. The array size is 10, and the stack and queue can store up to 5 elements each.

// Define the array and the indexes
int[] array = new int[10];
int top = -1;
int front = 0;
int rear = 0;
// Stack methods
public void push(int element) {
  if (isFull()) {
    System.out.println("Stack is full");
  } else {
    top++;
    array[top] = element;
    System.out.println("Pushed " + element + " to stack");
  }
}
public int pop() {
  if (isEmpty()) {
    System.out.println("Stack is empty");
    return -1;
  } else {
    int element = array[top];
    top--;
    System.out.println("Popped " + element + " from stack");
    return element;
  }
}
public int peek() {
  if (isEmpty()) {
    System.out.println("Stack is empty");
    return -1;
  } else {
    int element = array[top];
    System.out.println("Peeked " + element + " from stack");
    return element;
  }
}
public boolean isEmpty() {
  return top == -1;
}
public boolean isFull() {
  return top == front;
}
// Queue methods
public void enqueue(int element) {
  if (isFull()) {
    System.out.println("Queue is full");
  } else {
    array[rear] = element;
    System.out.println("Enqueued " + element + " to queue");
    rear = (rear + 1) % array.length;
  }
}
public int dequeue() {
  if (isEmpty()) {
    System.out.println("Queue is empty");
    return -1;
  } else {
    int element = array[front];
    System.out.println("Dequeued " + element + " from queue");
    front = (front + 1) % array.length;
    return element;
  }
}
public int front() {
  if (isEmpty()) {
    System.out.println("Queue is empty");
    return -1;
  } else {
    int element = array[front];
    System.out.println("Front of queue is " + element);
    return element;
  }
}
public boolean isEmpty() {
  return front == rear;
}
public boolean isFull() {
  return (rear + 1) % array.length == front;
}        

6 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?