HelloKoding

Practical coding guides

Stack and Queue Data Structure

In this article, you will learn about stack and queue data structures and theirs implementation examples

Stack Data Structure

Stack is a linear data structure consisting of a collection of similar data type items in LIFO (Last In First Out) order

Basic operations

  • push adds an item onto the stack
  • pop removes last pushed item from the stack
  • peek returns the last item pushed onto the stack
  • isEmpty returns true if no more items can be popped
  • isFull returns true if no more items can be pushed
  • size returns the number of items on the stack

You can implement a stack with either a linked list or an array (static or dynamic). The following gives you an implementation example with static array

StackByArray.java

package com.hellokoding.datastructure;

import java.util.NoSuchElementException;

public class StackByArray {
    private int[] stack;
    private int top;

    public StackByArray(int capacity) {
        stack = new int[capacity];
        top = -1;
    }

    public void push(int x) {
        if (isFull()) {
            throw new IllegalStateException();
        }

        stack[++top] = x;
    }

    public int pop() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == stack.length - 1;
    }

    public int size() {
        return top + 1;
    }

    public static void main(String[] args) {
        StackByArray myStack = new StackByArray(3);
        myStack.push(4);
        myStack.push(2);
        myStack.push(5);

        System.out.println(myStack.peek()); // 5
        System.out.println(myStack.pop()); // 5
        System.out.println(myStack.peek()); // 2

        System.out.println(myStack.size()); // 2
        System.out.println(myStack.isEmpty()); // false
        System.out.println(myStack.isFull()); // false
    }
}

Stack in Java

Java provides some Stack implementations including java.util.Deque, java.util.concurrent.BlockingDeque and java.util.Stack

  • java.util.Deque (interface), since Java 1.6, unsynchronized / not thread-safe, using in single threaded environment
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.peek();
stack.pop();
  • java.util.concurrent.BlockingDeque (interface), since Java 1.6, synchronized / thread-safe, using in multi threaded environment. For example
BlockingDeque<Integer> stack = new LinkedBlockingDeque<>();
stack.push(1);
stack.peek();
stack.pop();
  • java.util.Stack (class), since Java 1.1, extends Vector, synchronized, should not be used due to its negative impact on performance

Queue Data Structure

Queue is a linear data structure consisting of a collection of elements in FIFO (First In First Out) order

Basic operations

  • Insert aka Enqueue, adds an item onto the end of the queue
  • Remove aka Dequeue, retrieves and removes the head of the queue
  • Examine, retrieves, but does not remove, the head of the queue
  • isEmpty returns true if no more items can be dequeued
  • isFull returns true if no more items can be enqueued
  • size returns the number of items on the queue

You can implement a queue with either a linked list, a static array (capacity restricted) or a dynamic array. The following gives you an implementation example with static array

QueueByArray.java

package com.hellokoding.datastructure;

import java.util.NoSuchElementException;

public class QueueByArray {
    private int[] queue;
    private int front;
    private int rear;

    public QueueByArray(int capacity) {
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = 0;
    }

    public void enqueue(int x) {
        if (isFull()) {
            throw new IllegalStateException();
        }

        queue[rear++] = x;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return queue[front++];
    }

    public int front() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return queue[front];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return rear == queue.length;
    }

    public int size() {
        return rear - front;
    }

    public static void main(String[] args) {
        QueueByArray myQueue = new QueueByArray(3);
        myQueue.enqueue(1);
        myQueue.enqueue(2);
        myQueue.enqueue(3);

        System.out.println(myQueue.front()); // 1
        System.out.println(myQueue.dequeue()); // 1
        System.out.println(myQueue.front()); // 2

        System.out.println(myQueue.size()); // 2
        System.out.println(myQueue.isEmpty()); // false
        System.out.println(myQueue.isFull()); // false
    }
}

Double Ended Queue

Double Ended Queue aka Deque is a regular queue with additional property: elements can be added to or removed from either the front (head) or rear (tail)

Basic operations

  • Insert aka Enqueue, inserts element at rear and front of the queue
  • Remove aka Dequeue, retrieves and removes the rear and the front of the queue
  • Examine, retrieves, but does not remove, the rear and the front of the queue
  • isEmpty returns true if no more items can be dequeued
  • isFull returns true if no more items can be enqueued
  • size returns the number of items on the queue

You can implement a queue with either a linked list, a static array (capacity restricted) or a dynamic array. The following gives you an implementation example with static array

DequeueByArray.java

package com.hellokoding.datastructure;

import java.util.NoSuchElementException;

public class DequeueByArray {
    private int[] dequeue;
    private int front;
    private int rear;

    public DequeueByArray(int capacity) {
        this.dequeue = new int[capacity];
        this.front = 0;
        this.rear = 0;
    }

    public void enqueueFirst(int x) {
        if (isFull()) {
            throw new IllegalStateException();
        }

        for (int i = rear; i > front ; i--) {
            dequeue[i] = dequeue[i-1];
        }

        dequeue[front] = x;
        rear++;
    }

    public void enqueueLast(int x) {
        if (isFull()) {
            throw new IllegalStateException();
        }

        dequeue[rear++] = x;
    }

    public int dequeueFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return dequeue[front++];
    }

    public int dequeueLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return dequeue[rear--];
    }

    public int front() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return dequeue[front];
    }

    public int rear() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return dequeue[rear-1];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return rear == dequeue.length;
    }

    public int size() {
        return rear - front;
    }

    public static void main(String[] args) {
        DequeueByArray myQueue = new DequeueByArray(3);
        myQueue.enqueueFirst(1);
        myQueue.enqueueLast(2);
        myQueue.enqueueFirst(3);

        System.out.println(myQueue.front()); // 3
        System.out.println(myQueue.dequeueFirst()); // 3
        System.out.println(myQueue.front()); // 1

        System.out.println(myQueue.size()); // 2
        System.out.println(myQueue.isEmpty()); // false
        System.out.println(myQueue.isFull()); // false
    }
}

Priority Queue

Priority Queue Data Structure is a regular queue with additional properties

  • Each element has a priority associated with it
  • An element with high priority is served before an element with low priority
  • If two elements have the same priority, they are served according to the order in which they are enqueue

Basic operations

  • enqueue(element), inserts an element into the queue with an associated priority
  • dequeue(), retrieves and removes the highest priority element
  • front() aka peek(), retrieves without removing the highest priority element

You can implement a priority queue with either an array, a linked list or a heap (although priority queues conceptually distinct from heaps). The following gives you an implementation example with a max heap

PriorityQueueByHeap.java

package com.hellokoding.datastructure;

public class PriorityQueueByHeap {
    private MaxHeapByArray maxHeapByArray;

    public PriorityQueueByHeap(int capacity) {
        this.maxHeapByArray = new MaxHeapByArray(capacity);
    }

    public void enqueue(int x) {
        maxHeapByArray.push(x);
    }

    public int dequeue() {
        return maxHeapByArray.pop();
    }

    public int front() {
        return maxHeapByArray.peek();
    }

    public static void main(String[] args) {
        PriorityQueueByHeap myQueue = new PriorityQueueByHeap(5);
        myQueue.enqueue(7);
        myQueue.enqueue(2);
        myQueue.enqueue(3);
        myQueue.enqueue(1);
        myQueue.enqueue(9);

        System.out.println(myQueue.front()); // 9
        System.out.println(myQueue.dequeue()); // 9
        System.out.println(myQueue.front()); // 7
    }
}

MaxHeapByArray is defined in Heap Data Structure

Applications

  • Depth First Search uses a stack while Breath First Search uses a queue to track the traversal path
Follow HelloKoding