Array and linked list implementation of stack in java

Introduction to the stack

The stack is a first-in, last-out (FILO) linear data structure. The main operations are pushing and popping. stack.

Bottom of stack: The location where the earliest entered element is stored.

Top of stack: The last location where the element is stored (in some stacks, the top of the stack is represented as the next position of the top element).

Free online learning video recommendation: java video

Implementation of stack array

The example is as follows:

public class MyStack {
    private int[] array;
    private int top = -1;//用top来表示栈顶，指向栈顶元素
 
    public MyStack(int capacity){
        array = new int[capacity];
    }
 
    public void push(int data) throws Exception{
        if(top >= array.length-1)
            throw new IndexOutOfBoundsException("边界超过范围！");
        else
            array[++top] = data;//先将指针上移，后赋值
    }
 
    public int pop() throws Exception{
        int temp;
        if(top < 0)
            throw new IndexOutOfBoundsException("栈为空，不能再删除元素！");
        else{
            temp = array[top];
            array[top--] = 0;
        }
        return temp;
    }
 
    public void output(){
        for(int i = 0; i <= top; i++){
            System.out.println(array[i]);
        }
    }
 
    public static void main(String[] args) throws Exception{
        MyStack myStack = new MyStack(5);
        myStack.push(1);
        myStack.push(3);
        myStack.push(2);
        myStack.pop();
        myStack.push(4);
        myStack.pop();
        myStack.output();
    }
}

Linked list implementation of stack

When the stack is implemented using a linked list, the difference from the array implementation is that when popping the stack, because we only have one top node pointing to the top of the stack, so It needs to be traversed from beginning to end to find the previous position on the top of the stack.

The specific implementation is as follows:

public class MyStack_LinkList {
    private static class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }
    private Node head;//定义链表的头结点
    private Node top;
    private int size;//定义栈中的元素个数
    private int maxSize;
 
    private MyStack_LinkList(int capacity){
        maxSize = capacity;
    }
 
    public void push(int data) throws Exception{
        if(size >= maxSize){
            throw new IndexOutOfBoundsException("栈已满，不能再入栈！");
        }
        Node pushedNode = new Node(data);
        if(size == 0){
            head = pushedNode;
            top = pushedNode;
            pushedNode.next = null;
        }
        else{
            top.next = pushedNode;
            pushedNode.next = null;
            top = pushedNode;
        }
        size++;
    }
 
    public int pop() throws Exception{
        int temp = 0;
        if(size <= 0)
            throw new IndexOutOfBoundsException("栈为空，不能再出栈！");
        else if(size == 1){//当栈中元素个数为1时，单独讨论，需将头节点置为空
            temp = top.data;
            top = null;
        }
        else{
            temp = top.data;
            top = get(size - 1);//此时需遍历一遍链表，用top指向需出栈的上一个节点
            top.next = null;
        }
        size--;
        return temp;
 
    }
 
    /*
    从头到尾查找元素
     */
    public Node get(int index){
        Node temp = head;
        for(int i = 1; i < index; i++){
            temp = temp.next;
        }
        return temp;
    }
 
    public void output(){
        Node temp = head;
        for(int i = 0; i < size; i++){
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
 
    public static void main(String[] args) throws Exception{
        MyStack_LinkList myStack_linkList = new MyStack_LinkList(5);
        myStack_linkList.push(1);
        myStack_linkList.push(2);
        myStack_linkList.pop();
        myStack_linkList.push(3);
        myStack_linkList.push(5);
        myStack_linkList.output();
    }
}

Stack application scenario

(1) Bracket matching judgment, used for judgment (), {}, etc. match;

(2) During hex conversion, the converted number is output in reverse;

(3) The logic to implement recursion can be implemented using a stack;

(4) The stack can also be used for breadcrumb navigation, allowing users to easily go back to the previous page or higher when browsing the page.

If you want to learn more related knowledge, please visit: java introductory program, everyone is welcome to learn together!

The above is the detailed content of Array and linked list implementation of stack in java. For more information, please follow other related articles on the PHP Chinese website!