Implementing Stack and Queue Operations using Arrays and Linked Lists

In the realm of data structures, two commonly used abstract data types are Stack and Queue. These data structures provide efficient ways to handle data based on their specific behaviors. In this article, we will explore how to implement stack and queue operations using arrays and linked lists in the context of a 'Data Structures Using Java' course.

Stack

A stack is a last-in, first-out (LIFO) data structure, where elements are added and removed from the top. The basic operations of a stack include:

• Push: Add an element to the top of the stack.
• Pop: Remove and return the element from the top of the stack.
• Peek: Get the top element without removing it.

Implementation using an Array

One way to implement a stack is by utilizing an array. In Java, we can create an array of a fixed size to represent the stack. We also need to keep track of the top index indicating the last element in the stack.

Here is a simple example of implementing a stack using an array in Java: ```java public class ArrayStack { private final int MAX_SIZE = 1000; // Define the maximum size of the stack private int[] stackArray; private int top;

public ArrayStack() {
    stackArray = new int[MAX_SIZE];
    top = -1; // Initialize top as -1 for an empty stack
}

public void push(int data) {
    if (top == MAX_SIZE - 1) {
        System.out.println("Stack Overflow");
    } else {
        stackArray[++top] = data;
    }
}

public int pop() {
    if (top == -1) {
        System.out.println("Stack Underflow");
        return -1;
    } else {
        return stackArray[top--];
    }
}

public int peek() {
    if (top == -1) {
        System.out.println("Stack is empty");
        return -1;
    } else {
        return stackArray[top];
    }
}

} ```

Implementation using a Linked List

Alternatively, a stack can be implemented using a linked list, where each element contains a reference to the next element in the stack. In this case, the top of the stack is always the head of the linked list.

Here is an example of implementing a stack using a linked list in Java: ```java public class LinkedListStack { private class Node { int data; Node next; public Node(int data) { this.data = data; } }

private Node top;

public LinkedListStack() {
    top = null; // Initialize top as null for an empty stack
}

public void push(int data) {
    Node newNode = new Node(data);
    newNode.next = top;
    top = newNode;
}

public int pop() {
    if (top == null) {
        System.out.println("Stack Underflow");
        return -1;
    } else {
        int data = top.data;
        top = top.next;
        return data;
    }
}

public int peek() {
    if (top == null) {
        System.out.println("Stack is empty");
        return -1;
    } else {
        return top.data;
    }
}

} ```

Queue

A queue is a first-in, first-out (FIFO) data structure, where elements are added at the rear and removed from the front. The essential operations of a queue include:

• Enqueue: Add an element to the rear of the queue.
• Dequeue: Remove and return the element from the front of the queue.
• Peek: Get the front element without removing it.

Implementation using an Array

Similar to the stack, we can implement a queue using an array. However, we need to keep track of the front and rear indices to handle additions and removals.

Here is a simple example of implementing a queue using an array in Java: ```java public class ArrayQueue { private final int MAX_SIZE = 1000; // Define maximum size of the queue private int[] queueArray; private int front; private int rear;

public ArrayQueue() {
    queueArray = new int[MAX_SIZE];
    front = -1;
    rear = -1;
}

public void enqueue(int data) {
    if (rear == MAX_SIZE - 1) {
        System.out.println("Queue Overflow");
    } else {
        if (front == -1) {
            front = 0;
        }
        queueArray[++rear] = data;
    }
}

public int dequeue() {
    if (front == -1 || front > rear) {
        System.out.println("Queue Underflow");
        return -1;
    } else {
        return queueArray[front++];
    }
}

public int peek() {
    if (front == -1 || front > rear) {
        System.out.println("Queue is empty");
        return -1;
    } else {
        return queueArray[front];
    }
}

} ```

Implementation using a Linked List

Similarly, a queue can be implemented using a linked list. In this case, we can maintain references to both the head and the tail of the linked list.

Here is an example of implementing a queue using a linked list in Java: ```java public class LinkedListQueue { private class Node { int data; Node next;

    public Node(int data) {
        this.data = data;
    }
}

private Node head;
private Node tail;

public LinkedListQueue() {
    head = null;
    tail = null;
}

public void enqueue(int data) {
    Node newNode = new Node(data);
    if (isEmpty()) {
        head = newNode;
        tail = newNode;
    } else {
        tail.next = newNode;
        tail = newNode;
    }
}

public int dequeue() {
    if (isEmpty()) {
        System.out.println("Queue Underflow");
        return -1;
    } else {
        int data = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return data;
    }
}

public int peek() {
    if (isEmpty()) {
        System.out.println("Queue is empty");
        return -1;
    } else {
        return head.data;
    }
}

public boolean isEmpty() {
    return head == null && tail == null;
}

} ```

Conclusion

Implementing stack and queue operations using arrays and linked lists is essential knowledge for any aspiring data structures programmer. By understanding the principles behind these implementations, you can efficiently manage and manipulate data in your Java programs. Whether you use arrays or linked lists, the key is to grasp the underlying concepts and apply them effectively. Good luck in your 'Data Structures Using Java' course, and happy programming!