data-structures
스택
수색…
스택 소개
스택은 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();
}
균형 괄호 확인
브래킷은 ( , ) , { , } , [ , 또는 ] 중 하나의 문자로 간주됩니다.
여는 괄호 (즉, ( , [ 또는 { )가 닫는 괄호 (즉 ) , ] , 또는 } )의 정확히 동일한 유형으로 발생하면 두 개의 괄호가 일치 쌍으로 간주됩니다. 대괄호 쌍에는 [] , {} 및 () 등 세 가지 유형이 있습니다.
일치하는 대괄호 쌍이 포함되지 않은 경우 대괄호 쌍이 균형을 이루지 않습니다. 예를 들어, {[(])} 사이에 내용물이 때문에 균형되지 { 및 } 균형 아니다. 대괄호의 쌍은 하나의 불평형 개구 브래킷을 둘러싸는 ( , 괄호 쌍은 하나의 불평형 폐쇄 사각형 브래킷을 둘러싸 ] .
이 논리에 따라 다음 조건이 충족 될 경우 일련의 대괄호가 균형을 이룬 것으로 간주됩니다.
그것은 짝이없는 대괄호를 포함하고 있지 않습니다.
일치하는 쌍의 괄호의 경계 내에 포함 된 괄호의 하위 집합은 일치하는 쌍의 괄호입니다.
연산:
- 스택을 선언합니다 (예를 들어
stack). - 이제 문자열 입력을 탐색합니다.
- a) 현재 문자가 시작 괄호 (예 :
(또는{또는[) 인 경우 스택에 밀어 넣습니다. - b) 현재의 문자는 폐쇄 금구 (즉, 인 경우
)또는}또는])를 스택으로부터 팝. 팝 된 문자가 일치하는 시작 브래킷 인 경우 다른 else 괄호는not balanced이루지not balanced. - c) 현재 문자가 폐쇄 금구 (즉, 인 경우
)또는}또는]) 스택이 비어있는 다음 괄호은not balanced.
- 완전한 순회 후, 스택에 시작 브래킷이 남아 있으면 문자열이
not balanced이루지not balanced그렇지 않으면 우리는balanced문자열을 갖는다.