수색…


스택 소개

스택은 LIFO (last-in, first-out) 데이터 구조입니다. 즉, 스택에 추가 된 가장 최근의 (또는 "last in") 요소는 첫 번째 요소가 제거 된 것입니다 ( "first out").

상자 안에있는 책의 예를 생각해 봅시다. 한 번에 하나의 책 만 상자에서 추가하거나 제거 할 수 있으며 맨 위에 추가하거나 제거 할 수 있습니다.

이제 첫 번째 두 권의 책은 다음과 같습니다.

  |--------|
  | book 2 | ◀──── top of box
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

3 권을 추가하면 맨 위에 표시됩니다. 책 3 이전에 추가 된 나머지 책은 그 아래에 남아 있습니다.

  |--------|
  | book 3 | ◀──── top of box
  |--------|
  | book 2 |
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

상자는 스택과 같으며 책은 데이터 요소입니다. 상자에 책을 추가하는 것은 푸시 작업이며 상자 맨 위에서 책을 제거 / 가져 오는 것은 팝 작업입니다. pop 연산을 수행하면 book 3이 나오고, book 3을 push하기 전에 상자는 원래의 방식으로 되돌아갑니다. 이것은 우리가 마지막으로 넣은 (또는 가장 최근의) 요소가 우리가 첫 번째 요소 였음을 의미합니다. 나왔다 (LIFO). 책 1을 얻으려면 책 2를 제거하는 책과 책 1을 가져 오는 책이 더 있어야합니다.

배열을 사용하여 스택 구현. 이를 위해 최상위 위치 (tos)를 가리키는 색인이 필요합니다. 요소가 스택에 푸시 될 때마다 tos는 1 씩 증가하고 pop 연산이 수행 될 때마다 스택의 최상부를 가리키는 인덱스 (tos)가 1 씩 감소합니다.

푸시:

PUSH 작동 전

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|
void push(dataElment item){
    stack[top]=item; //item = i4
    top++;
    
}

PUSH 조작 후 스택에는 스택의 맨 위를 가리키는 포인터가 있습니다. 푸시 연산이 호출 될 때마다 상단에 값을 배치하고 값을 업데이트합니다.

        tos -- Top of the stack
                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |     |
        |-----|-----|-----|-----|

POP : pop 연산은 스택의 맨 위에서 내용을 제거하고 tos의 값을 1 씩 감소시킴으로써 업데이트합니다

팝 작동 전 :

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|
dataElment pop(){
    dataElment value = stack[tos--];
    return value;
}

팝 조작 후 :

                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |
        |-----|-----|-----|-----|
        When a push operation is performed it overwrites i4.
    

스택을 사용하여 문장 검색

회문은 '카약'과 같이 두 가지 방법으로 읽을 수있는 단어입니다.

이 예제는 주어진 단어가 파이썬 3을 사용하여 회문문인지 찾는 방법을 보여줍니다.

먼저 문자열을 스택으로 변환해야합니다 (배열을 스택으로 사용합니다).

str = "string"
stk = [c for c in str] #this makes an array: ["s", "t", "r", "i", "n", "g"]
stk.append("s") #adds a letter to the array
stk.pop() #pops the last element

이제 우리는 그 말을 뒤집어 써야합니다.

def invert(str):
    stk = [c for c in str]
    stk2 = []
    while len(stk) > 0:
        stk2.append(stk.pop())
    #now, let's turn stk2 into a string
    str2 = ""
    for c in stk2:
        str2 += c
    return str2

이제 우리는 단어와 거꾸로 된 형태를 비교할 수 있습니다.

def palindrome(str):
    return str == invert(str)

배열 및 링크 된 목록을 사용하여 스택 구현

배열 구현

#include<stdio.h>

#define MAX 100000                    //Global variables
int top = -1;
int a[MAX];

void push(int x){
    
    if(top == MAX-1){                         // Check whether stack is full
        printf("Stack Overflow\n");
        return;
    }
    
    a[++top] = x;                            // Otherwise increment top and insert x
}

void pop(){
    if(top == -1){                                     // if top = -1, empty stack
        printf("Empty stack\n");
        return;
    }
    top--;        
}

void print(){                         //printing stack values
    
    for(int i=0;i <= top;i++){
        printf("%d ",a[i]);        
    }        
    printf("\n");        
}

void topValue(){                        // Method can print the top value of a stack
    printf("%d",a[top]);
}
int main(){
        
    push(5);
    push(20);
    push(15);
    print();
    pop();
    print();
    push(35);
    print();
    topValue();    
    
}

링크 된 목록 구현

#include<stdio.h>
#include<malloc.h>

 struct node{
    int data;
    node* link;
};
node* top = NULL;

void push(int data){
    
    node* temp = (struct node*)malloc(sizeof(struct node*));
    temp->data = data;
    temp->link = top;
    top = temp;
}

void pop(){
    
    if(top == NULL) return;
    node* temp = top;
    top = top->link;
    free(temp);
}
void print(){
    
    node* t = top;
    while(t != NULL){
        printf("%d ",t->data);
        t=t->link;
    }
    printf("\n");
}

void topValue(){
    printf("%d ",top->data);
}
int main(){
        
    push(5);
    push(20);
    push(15);
    print();
    pop();
    print();
    push(35);
    print();            
    topValue();    
}

균형 괄호 확인

브래킷은 ( , ) , { , } , [ , 또는 ] 중 하나의 문자로 간주됩니다.

여는 괄호 (즉, ( , [ 또는 { )가 닫는 괄호 (즉 ) , ] , 또는 } )의 정확히 동일한 유형으로 발생하면 두 개의 괄호가 일치 쌍으로 간주됩니다. 대괄호 쌍에는 [] , {}() 등 세 가지 유형이 있습니다.

일치하는 대괄호 쌍이 포함되지 않은 경우 대괄호 쌍이 균형을 이루지 않습니다. 예를 들어, {[(])} 사이에 내용물이 때문에 균형되지 {} 균형 아니다. 대괄호의 쌍은 하나의 불평형 개구 브래킷을 둘러싸는 ( , 괄호 쌍은 하나의 불평형 폐쇄 사각형 브래킷을 둘러싸 ] .

이 논리에 따라 다음 조건이 충족 될 경우 일련의 대괄호가 균형을 이룬 것으로 간주됩니다.

그것은 짝이없는 대괄호를 포함하고 있지 않습니다.

일치하는 쌍의 괄호의 경계 내에 포함 된 괄호의 하위 집합은 일치하는 쌍의 괄호입니다.

연산:

  1. 스택을 선언합니다 (예를 들어 stack ).
  2. 이제 문자열 입력을 탐색합니다.
  • a) 현재 문자가 시작 괄호 (예 : ( 또는 { 또는 [ ) 인 경우 스택에 밀어 넣습니다.
  • b) 현재의 문자는 폐쇄 금구 (즉, 인 경우 ) 또는 } 또는 ] )를 스택으로부터 팝. 팝 된 문자가 일치하는 시작 브래킷 인 경우 다른 else 괄호는 not balanced 이루지 not balanced .
  • c) 현재 문자가 폐쇄 금구 (즉, 인 경우 ) 또는 } 또는 ] ) 스택이 비어있는 다음 괄호은 not balanced .
  1. 완전한 순회 후, 스택에 시작 브래킷이 남아 있으면 문자열이 not balanced 이루지 not balanced 그렇지 않으면 우리는 balanced 문자열을 갖는다.


Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow