Implementing a Stack

When implementing a stack, there are several ways to represent the underlying data structure. The choice of implementation depends on various factors, such as the programming language used, the application requirements, and the desired performance characteristics.

Array-Based Stack

One common way to implement a stack is by using an array. In this implementation, the stack elements are stored in a fixed-size array, and an index variable is used to keep track of the top element.

Here's an example of how an array-based stack can be implemented in Java:

1public class ArrayStack {
2  private int maxSize;
3  private int[] stackArray;
4  private int top;
5
6  public ArrayStack(int size) {
7    maxSize = size;
8    stackArray = new int[maxSize];
9    top = -1;
10  }
11
12  public void push(int value) {
13    if (isFull()) {
14      System.out.println("Stack is full. Cannot push element.");
15      return;
16    }
17
18    stackArray[++top] = value;
19  }
20
21  public int pop() {
22    if (isEmpty()) {
23      System.out.println("Stack is empty. Cannot pop element.");
24      return -1;
25    }
26
27    return stackArray[top--];
28  }
29
30  public int peek() {
31    if (isEmpty()) {
32      System.out.println("Stack is empty. No top element.");
33      return -1;
34    }
35
36    return stackArray[top];
37  }
38
39  public boolean isEmpty() {
40    return top == -1;
41  }
42
43  public boolean isFull() {
44    return top == maxSize - 1;
45  }
46}

In the above implementation, the ArrayStack class has a stackArray variable to hold the elements, a top variable to keep track of the top element's index, and methods to perform stack operations such as push, pop, and peek. The isFull and isEmpty methods check if the stack is full or empty, respectively.

The advantage of using an array-based stack is that it provides constant-time complexity for the push and pop operations. However, it requires a fixed-size array, which may limit the number of elements the stack can hold. Additionally, if the stack becomes full, further push operations will result in an error.

Linked List-Based Stack

Another way to implement a stack is by using a linked list. In this implementation, each element of the stack is represented by a node in the linked list, and the top of the stack is represented by the head of the linked list.

Here's an example of how a linked list-based stack can be implemented in Java:

1public class LinkedListStack {
2  private Node top;
3
4  public void push(int value) {
5    Node newNode = new Node(value);
6    newNode.next = top;
7    top = newNode;
8  }
9
10  public int pop() {
11    if (isEmpty()) {
12      System.out.println("Stack is empty. Cannot pop element.");
13      return -1;
14    }
15
16    int value = top.data;
17    top = top.next;
18    return value;
19  }
20
21  public int peek() {
22    if (isEmpty()) {
23      System.out.println("Stack is empty. No top element.");
24      return -1;
25    }
26
27    return top.data;
28  }
29
30  public boolean isEmpty() {
31    return top == null;
32  }
33
34  private class Node {
35    private int data;
36    private Node next;
37
38    public Node(int value) {
39      data = value;
40    }
41  }
42}

In the above implementation, the LinkedListStack class uses a nested Node class to represent the elements of the stack. The push, pop, peek, and isEmpty methods are similar to the array-based implementation but operate on the linked list structure.

The advantage of using a linked list-based stack is that it allows for dynamic resizing and can accommodate an arbitrary number of elements. However, it requires additional memory to store references to the next nodes in the list, which may result in a higher memory overhead compared to the array-based implementation.

Conclusion

When implementing a stack, consider the specific requirements of your application and the trade-offs between the array-based and linked list-based implementations. Both options have their advantages and disadvantages, and the choice depends on factors such as memory efficiency, performance, and flexibility.

Now that you understand different ways to implement a stack and their pros and cons, let's move on to exploring the common operations performed on a stack in the next section.