데이터 구조: 스택 및 큐

12364 단어 muict datastructure queue stack

스택 및 큐는 프로그램 작동 중에 프로그래머의 도구로 자주 사용되며 일반적으로 작업이 완료된 후 삭제됩니다.

스택

스택은 "후입선출"또는 LIFO 모델을 따르는 추상 데이터 구조입니다. 몇 가지 실제 예는 이전 웹 페이지로 돌아가는 "클릭"과 텍스트 편집기의 실행 취소 기능입니다.

스택에는 3가지 기본 작업이 있습니다.
1. 푸시: 스택에 데이터 항목을 삽입합니다.
2. 팝: 스택 맨 위에서 항목을 제거합니다.
3. 엿보기: 항목을 제거하지 않고 스택 맨 위에서 항목 값을 읽습니다.

프로그래밍에서 배열이나 연결된 목록을 사용하여 스택을 구현할 수 있습니다. (아래는 Java로 스택을 구현한 예입니다.)

class StackX {
    private int maxSize;
    private long[] stackArray;
    private int top;

    public StackX(int s) {                // constructor
        maxSize = s;                      // set the array size
        stackArray = new long[maxSize];   // create an array
        top = -1;                         // no items yet
    }

    public void push(long j) {        // put items on top of the stack
        stackArray[++top] = j;        // increment top when item inserted
    }
    public long pop() {               // take item from the top of the stack
        return stackArray[top--];     // access item, then decrement top
    }
    public long peek() {              // peek at the top of the stack
        return stackArray[top];
    }
    public boolean isEmpty() {        // true if the stack is empty
        return (top == -1);
    }
    public boolean isFull() {         // true if the stack is full
        return (top == maxSize -1);
    }

스택 애플리케이션

데이터 반전; 예를 들어 문자열 반전

구문 분석: 추가 증명을 위해 데이터를 독립적인 조각으로 나눕니다. 예를 들어 [,{,(,),},]와 일치하는 구분 기호를 확인합니다.

how it works:

read characters from the string one at a time

if you encounter an opening delimiter [,{,(, place it on a stack

if you encounter a closing delimiter, pop the item from the top of the stack

in case they don't match (the opening and closing delimiter), then an error occurs.

예: a{b(c[d]e)f}h

끈
스택

ㅏ
비어 있는

{
{

비
{

(
{(

씨
{(

[
{([

디
{([

]
{(

이자형
{(

)
{

에프
{

{
비어 있는

시간
비어 있는

연기: 데이터 사용을 잠시 연기해야 하는 경우. 예를 들어, 산술 표현식을 구문 분석합니다. 3+(5-9)*4

Notations we're going to use:

prefix -> + a b

infix -> a + b

postfix a b +

+, -, *, /, these are operators.
While we call the numbers (1,2,3,...) the operands.

Precedence (priority, rank) relationships:

+, - have the same precedence

*, / have the same precedence, and are higher than +, -

작동 방식을 설명하기 위해 비디오를 사용하는 것이 더 쉬울 것이라고 생각했습니다. 그래서 시작하겠습니다...

이렇게 해야 하는 이유는 컴퓨터가 표현식을 통해 앞으로 또는 뒤로만 이동할 수 있기 때문입니다.

중위식을 후위식으로 변환하는 방법을 살펴보겠습니다.

그리고 접미사 표현을 평가하는 방법에 대한 영상입니다..

자세한 설명은 here 을 클릭하세요.

역추적: 많은 검색 응용 프로그램, 여덟 여왕 문제 등에서 사용됩니다.
경로 찾기의 예:

n-queen 문제의 예:

대기줄

대기열은 "선입선출"또는 FIFO 모델을 따르는 추상 데이터 구조입니다. 일부 실제 사례에는 파일 인쇄(대기열에 파일이 있음), 프로세스 스케줄러, 대기 줄이 포함됩니다.

대기열의 기본 작업:
1. Enque/Add/Put: Queue의 뒤 또는 뒤에 데이터 항목을 삽입합니다.
2. Deque/Delete/Get: 큐의 맨 앞에서 항목을 제거합니다.
3. 엿보기: 항목을 제거하지 않고 대기열 맨 앞에서 항목 값을 읽습니다.

이제 아래 자바에서 큐 구현을 살펴보겠습니다!

class Queue {
    private int maxSize;
    private long[] queArray;
    private int front;
    private int back;
    private int nItems;

    public Queue(int s) {                    // Constructor
        maxSize = s;
        quaArray = new long[maxSize];
        front = 0;
        back = -1;
        nItems = 0;
    }

    public void insert(long j) {            // Put an item at the back of the queue
        if(back == maxSize -1) back = -1;   // Deal with wraparound
        queArray[++back] = j;               // Increment back and insert the item
        nItems++;                           // One more item
    }
    public long remove() {                  // Take item from the front of the queue
        long temp = queArray[front++];      // Get the item and increment front
        if(front == maxSize) front = 0;     // Deal with wraparound
        nItems--;                           // One less item
        return temp;
    }
    public long peekFront() {
        return queArray[front];
    }