[C] Stack, 스택

The stack is literally a data structure in the form of stacking data one by one. The stack is also a data structure that is accessed and processed from the top, just as it is impossible to remove the book from the bottom when the books are stacked one after another in a box. This data structure is called a last-in-first-out structure because the last inserted data is deleted first. A stack is a data structure that stacks or returns data of the same structure and size in one direction, and stacks data from the bottom to the top. In general, an index called top is used, and the process of putting data is called push, and the process of pulling out data is called pop.

스택은 말 그대로 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 상자 속에 책을 차례차례 쌓게되면 맨 밑의 책부터 빼내는 것이 불가능한 것 처럼 스택 역시 맨 위에서부터 접근하고 처리하는 자료구조이다. 이러한 자료구조는 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되기 때문에 후입선출구조라고 부른다. 스택은 같은 구조, 크기의 데이터를 한 방향으로 접근하여 쌓거나 반환하는 자료구조이며 아래쪽부터 위쪽으로 데이터를 쌓는다. 일반적으로 top 이라는 인덱스를 사용하며 데이터를 집어넣는 과정을 push, 데이터를 꺼내는 과정을 pop 이라고 한다.

#include <stdio.h>
#define s_size 100

int stack[s_size];
int top = -1;

int empty_check(){
    if (top == -1 ) return 1;
    else return 0;
}

int full_check(){
    if (top== s_size - 1) return 1;
    else return 0;
}

void push(int x){
    if (full_check()) return;
    else stack[ ++top ]= x;
    return;
}

int pop(){
    if (empty_check()) return -1;
    else return stack[top--];       
}

int main(){
    push(1);
    printf("%d\n", stack[top]);

    push(2); 
    push(3);
    pop();
    printf("%d", stack[top]);

    return 0;
}

1
2

The simplest way to implement the stack is to implement it through an array of a certain size, and declare and use a stack array of a certain size. Since the index of the location where the first element is to be stored is 0, top is initialized to -1 for convenience of operation. Since the size of the array is declared in advance, it is necessary to check the condition of whether the size of the array is exceeded and whether the array is not empty. When inserting data in an array, a value is assigned to the position where the index of top is increased, and for deletion, a post-value operation is performed that decreases (moves) top by 1 after deleting the currently located element.

스택을 구현하는 가장 간단한 방법은 일정 크기의 배열을통해 구현하는 방법으로 일정 크기의 stack 배열을 선언하여 사용한다. 첫 번째 요소가 저장될 위치의 인덱스가 0이기 때문에 연산의 편의를 위하여 top 은 -1로 초기화 된다. 미리 배열의 크기를 선언한다는 점에서 배열의 크기를 초과하지않는지, 그리고 배열이 비어있지 않은지에 대한 조건을 선행적으로 확인해야한다. 배열에서의 데이터 삽입은 top 인덱스를 증가시킨 위치에 값을 대입하며, 삭제는 현재 위치한 원소를 삭제 후 top을 1만큼 감소시키는(이동하는) 후치연산이 수행된다.

The stack code implemented in a simple form is as follows.

간단한 형태로 구현하는 stack 코드는 아래와 같다.

#include <stdio.h>

int stack[100];
int top = -1;

int main(){

    stack[++top]=1;
    printf("%d\n", stack[top]);

    stack[++top]=2; 
    stack[++top]=3;

    printf("%d", stack[--top]);

    return 0;
}

1
2