데이터 구조 및 알고리즘-스택

스택은 대부분의 프로그래밍 언어에서 일반적으로 사용되는 ADT (Abstract Data Type)입니다. 예를 들어 카드 한 벌 또는 접시 더미 등과 같이 실제 스택처럼 동작하므로 스택이라고합니다.

실제 스택은 한쪽 끝에서만 작업을 허용합니다. 예를 들어, 스택 상단에서만 카드 또는 플레이트를 배치하거나 제거 할 수 있습니다. 마찬가지로 Stack ADT는 한쪽 끝에서만 모든 데이터 작업을 허용합니다. 주어진 시간에 스택의 최상위 요소에만 액세스 할 수 있습니다.

이 기능은 LIFO 데이터 구조를 만듭니다. LIFO는 후입 선출 (Last-in-first-out)을 의미합니다. 여기서 마지막에 배치 (삽입 또는 추가) 된 요소가 먼저 액세스됩니다. 스택 용어에서 삽입 작업은PUSH 작업 및 제거 작업이 호출됩니다. POP 조작.

스택 표현

다음 다이어그램은 스택과 그 작업을 보여줍니다.

스택은 배열, 구조, 포인터 및 연결 목록을 통해 구현할 수 있습니다. 스택은 고정 된 크기이거나 동적 크기 조정의 감각을 가질 수 있습니다. 여기서는 배열을 사용하여 스택을 구현하여 고정 크기 스택 구현을 만듭니다.

기본 작동

스택 작업에는 스택 초기화, 사용 및 초기화 해제가 포함될 수 있습니다. 이러한 기본적인 것 외에도 스택은 다음 두 가지 주요 작업에 사용됩니다.

• push() − 스택의 요소를 밀기 (저장).

• pop() − 스택에서 요소 제거 (액세스).

데이터가 스택에 푸시되는 경우.

스택을 효율적으로 사용하려면 스택 상태도 확인해야합니다. 같은 목적으로 다음 기능이 스택에 추가됩니다.

• peek() − 스택을 제거하지 않고 스택의 최상위 데이터 요소를 가져옵니다.

• isFull() − 스택이 가득 찼는 지 확인하십시오.

• isEmpty() − 스택이 비어 있는지 확인하십시오.

항상 스택의 마지막 PUSH 데이터에 대한 포인터를 유지합니다. 이 포인터는 항상 스택의 맨 위를 나타내므로top. 그만큼top 포인터는 실제로 제거하지 않고 스택의 최상위 값을 제공합니다.

먼저 스택 함수를 지원하는 절차에 대해 배워야합니다.

몰래 엿보다()

peek () 함수의 알고리즘-

begin procedure peek
   return stack[top]
end procedure

C 프로그래밍 언어로 peek () 함수 구현-

Example

int peek() {
   return stack[top];
}

가득()

isfull () 함수의 알고리즘-

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

C 프로그래밍 언어로 isfull () 함수 구현-

Example

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

비었다()

isempty () 함수의 알고리즘-

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

C 프로그래밍 언어에서 isempty () 함수의 구현은 약간 다릅니다. 배열의 인덱스가 0부터 시작하므로 top을 -1로 초기화합니다. 따라서 top이 0보다 낮은 지 또는 -1인지 확인하여 스택이 비어 있는지 확인합니다. 다음은 코드입니다.

Example

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

푸시 작업

새 데이터 요소를 스택에 넣는 프로세스를 푸시 작업이라고합니다. 푸시 작업에는 일련의 단계가 포함됩니다.

• Step 1 − 스택이 가득 찼는 지 확인합니다.

• Step 2 − 스택이 가득 차면 오류가 발생하고 종료됩니다.

• Step 3 − 스택이 가득 차 있지 않으면 top 다음 빈 공간을 가리 킵니다.

• Step 4 − 상단이 가리키는 스택 위치에 데이터 요소를 추가합니다.

• Step 5 − 성공을 반환합니다.

연결 목록을 사용하여 스택을 구현하는 경우 3 단계에서 동적으로 공간을 할당해야합니다.

PUSH 작업을위한 알고리즘

푸시 연산을위한 간단한 알고리즘은 다음과 같이 유도 할 수 있습니다.

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

이 알고리즘을 C로 구현하는 것은 매우 쉽습니다. 다음 코드를 참조하십시오-

Example

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

팝 작업

콘텐츠를 스택에서 제거하는 동안 액세스하는 것을 팝 작업이라고합니다. pop () 연산의 배열 구현에서 데이터 요소는 실제로 제거되지 않습니다.top다음 값을 가리 키기 위해 스택에서 더 낮은 위치로 감소합니다. 그러나 연결 목록 구현에서 pop ()은 실제로 데이터 요소를 제거하고 메모리 공간을 할당 해제합니다.

팝 작업에는 다음 단계가 포함될 수 있습니다.

• Step 1 − 스택이 비어 있는지 확인합니다.

• Step 2 − 스택이 비어 있으면 오류가 발생하고 종료됩니다.

• Step 3 − 스택이 비어 있지 않은 경우 데이터 요소에 액세스합니다. top 가리키고 있습니다.

• Step 4 − top 값을 1 씩 감소시킵니다.

• Step 5 − 성공을 반환합니다.

팝 작업을위한 알고리즘

Pop 연산을위한 간단한 알고리즘은 다음과 같이 유도 될 수 있습니다.

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

C에서이 알고리즘의 구현은 다음과 같습니다.

Example

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

C 프로그래밍 언어의 전체 스택 프로그램을 보려면 여기 를 클릭하십시오 .