Java에서 스택의 배열 및 연결 목록 구현

스택 소개

스택은 FILO(선입 후출) 선형 데이터 구조입니다. 주요 작업은 푸시와 팝입니다.

스택 하단: 가장 먼저 입력된 요소가 저장되는 위치입니다.

스택 상단: 요소가 저장된 마지막 위치입니다(일부 스택에서는 스택 상단이 상단 요소의 다음 위치로 표시됩니다).

무료 온라인 학습 영상 추천 : java 영상

스택 배열 구현

예는 다음과 같습니다.

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();
    }
}

스택의 링크드 리스트 구현

스택을 링크드 리스트로 구현하는 경우, 배열 구현과의 차이점은 스택을 팝할 때 스택의 상단을 가리키는 최상위 노드가 하나만 있기 때문에 스택 상단의 이전 위치를 찾으려면 처음부터 끝까지 이를 탐색해야 한다는 것입니다.

구체적인 구현은 다음과 같습니다.

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();
    }
}

스택의 적용 시나리오

(1) 대괄호 일치 판단, (), {} 등이 일치하는지 판단하는 데 사용됩니다.

(2) 동안; 16진수 변환, 역방향 변환된 숫자를 출력합니다.

(3) 재귀를 구현하는 논리는 스택을 사용하여 구현할 수 있습니다.

(4) 스택은 이동 경로 탐색에도 사용할 수 있으므로 사용자가 쉽게 이전으로 돌아갈 수 있습니다. 수준 또는 이전 페이지로 이동합니다.

더 많은 관련 지식을 배우고 싶다면 다음을 방문하세요: Java 입문 프로그램, 누구나 함께 배울 수 있습니다!

위 내용은 Java에서 스택의 배열 및 연결 목록 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!