하나의 데이터 구조를 사용하여 여러 스택(K 스택) 구현

동적 멀티 스택은 여러 스택에 요소를 저장할 수 있는 기능을 갖춘 탁월한 데이터 구조이며, 스택 수는 끊임없이 변화합니다. 하나의 데이터 구조만 사용하여 K 스택을 구현하는 것은 어려운 작업이 될 수 있습니다. 이 튜토리얼에서는 C++를 사용하여 동적 멀티 스택(K 스택)을 수행하는 두 가지 방법을 살펴보겠습니다. 첫 번째 방법은 배열을 사용하여 요소를 저장하고 두 개의 추가 배열을 사용하여 스택의 최상위 및 다음 인덱스를 모니터링합니다. 두 번째 방법은 노드 벡터를 사용하여 요소를 저장하고 벡터를 사용하여 각 스택의 헤드를 추적합니다.

이 글에서는 데이터 구조를 사용하여 C++에서 동적 멀티스택을 수행하는 방법에 중점을 둘 것입니다.

방법

• 방법 1 - 배열을 사용하여 데이터 구조의 요소를 저장하고, 두 개의 보조 배열을 사용하여 각 스택의 최상위 요소와 배열에서 사용 가능한 다음 빈 슬롯의 인덱스를 저장합니다.

• 방법 2 - 이중 연결 리스트를 사용하여 데이터 구조의 요소를 저장하고, 벡터를 사용하여 각 스택의 헤드 노드를 저장합니다.

문법

주어진 구문은 C++에서 KStacks라는 클래스를 선언하는 것입니다. 이 클래스에는 다음과 같은 멤버 함수 또는 메서드가 있습니다.

• 두 개의 매개변수 k와 n을 받아들이는 생성자 메서드 KStacks.

• 두 개의 매개변수 item과 sn을 허용하는 push라는 메서드는 스택 sn에 요소를 삽입하는 데 사용됩니다.

• sn 매개변수를 받아들이고 스택 sn에서 요소를 제거하는 데 사용되는 pop이라는 메서드입니다.

• 단일 매개변수 sn을 사용하고 스택 sn이 비어 있는지 여부를 나타내는 부울 값을 반환하는 is_empty라는 메서드입니다.

• 전체 데이터 구조가 가득 찼는지 여부를 나타내는 부울을 반환하는 is_full이라는 메서드입니다.

으아아아

알고리즘

다음은 단일 데이터 구조를 사용하여 K-heap 동적 다중 배낭을 구현하는 알고리즘입니다.

• 1단계 - 먼저 요소를 저장할 n 크기의 배열과 k 크기의 보조 배열 두 개를 포함하는 데이터 구조를 만듭니다. 한 배열은 각 스택의 최상위 요소에 대한 정보를 저장하고, 다른 배열은 기본 배열에서 사용 가능한 다음 인덱스를 추적합니다.

• 2단계 - 다음으로 부모 배열과 해당 배열을 -1과 0 값으로 호출합니다.

• 3단계 - cart() 함수를 사용하여 특정 스택에 객체를 추가할 수 있습니다. 이 기능에는 추가할 항목과 그룹 번호라는 두 가지 입력이 필요합니다. 항목을 추가하기 전에 push() 함수는 다음 사용 가능한 인덱스 값을 n과 비교하여 데이터 구조가 가득 찼는지 확인합니다. 여전히 공간이 있는 경우 항목은 사용 가능한 다음 인덱스에 추가되고 사용 가능한 다음 인덱스의 값이 업데이트됩니다.

• 4단계 - pop() 함수는 그룹 번호를 매개변수로 사용하여 특정 스택에서 항목을 제거하는 데 사용됩니다. pop() 함수는 상위 배열 값을 -1과 비교하여 스택이 비어 있는지 확인합니다. 스택이 비어 있지 않으면 pop() 함수는 스택에서 최상위 요소를 제거하고 새로운 최상위 요소를 가리키도록 부모 배열 값을 업데이트합니다.

• 5단계 - 특정 스택이 비어 있는지 확인하려면 is_empty() 함수를 사용하고 그룹 번호를 매개변수로 사용합니다. 이 함수는 상위 배열의 값이 -1인지 확인합니다.

• 6단계 - 모든 스택이 가득 찼는지 확인하기 위해 사용 가능한 다음 인덱스 값이 n과 같은지 확인하는 is_full() 함수를 사용합니다.

방법 1

우리는 요소를 보유하기 위해 배열을 활용하고 스택의 최상위 및 후속 인덱스를 모니터링하기 위해 두 개의 추가 배열을 활용하는 접근 방식을 취할 것입니다. 이는 간단하고 효과적인 솔루션이지만 미리 정의할 수 있는 미리 결정된 수의 스택이 필요합니다.

아래는 동일한 프로그램 코드입니다.

예

이 코드는 K Stacks 데이터 구조의 구현을 나타냅니다. 이는 여러 스택을 단일 배열에 수용할 수 있는 스택 데이터 구조를 동적으로 해석한 것입니다.

KStacks 클래스에는 세 개의 멤버 변수가 포함되어 있습니다−

• arr − 모든 스택 요소로 저장된 배열입니다.

• top − 각 스택의 최상위 저장소로 사용되는 배열입니다.

• next − 배열에서 사용 가능한 다음 위치를 저장하는 데 사용되는 배열입니다.

• push - 지정된 스택에 요소를 삽입합니다.

• pop - 지정된 스택에서 요소를 제거합니다.

• is_empty − 지정된 스택이 비어 있는지 확인합니다.

• is_full - 어레이가 완전히 채워졌는지 확인합니다.

메인 함수에서는 스택 수와 배열 크기를 입력 매개변수로 사용하여 KStacks 클래스의 인스턴스가 생성됩니다. 그런 다음 요소는 세 가지 다른 스택에 푸시됩니다. 마지막으로 각 스택의 최상위 요소를 제거하고 표시합니다.

#include <iostream>
#include <vector>
#include<climits>
using namespace std;

class KStacks {
   private:
   int *arr;
   int *top;
   int *next;
   int n, k;
   public:
   KStacks(int k, int n) {
      this->k = k;
      this->n = n;
      arr = new int[n];
      top = new int[k];
      next = new int[n];
   for (int i = 0; i < k; i++)
      top[i] = -1;

   for (int i = 0; i < n - 1; i++)
      next[i] = i + 1;
   next[n - 1] = -1;
}

void push(int item, int sn) {
   if (is_full()) {
      cout << "Stack Overflow\n";
      return;
   }

   int i = next[sn];
   next[sn] = top[sn];
   top[sn] = i;
   arr[i] = item;
}

int pop(int sn) {
   if (is_empty(sn)) {
      cout << "Stack Underflow\n";
      return INT_MAX;
   }

   int i = top[sn];
   top[sn] = next[i];
   next[i] = i;
   return arr[i];
   }

   bool is_empty(int sn) {
      return top[sn] == -1;
   }

   bool is_full() {
      return next[0] == -1;
   }
};

int main() {
   KStacks ks(3, 10);
   ks.push(15, 2);
   ks.push(45, 2);

   ks.push(17, 1);
   ks.push(49, 1);
   ks.push(39, 1);

   ks.push(11, 0);
   ks.push(9, 0);
   ks.push(7, 0);

   cout << "Popped element from stack 2: " << ks.pop(2) << endl;
   cout << "Popped element from stack 1: " << ks.pop(1) << endl;
   cout << "Popped element from stack 0: " << ks.pop(0) << endl;

   return 0;
}

输出

Stack Overflow
Stack Overflow
Popped element from stack 2: Stack Underflow
2147483647
Popped element from stack 1: 39
Popped element from stack 0: 11

方法二

我们将采用一种方法，其中使用节点向量来存储元素。这种方法应该由一个用于维护每个堆栈头部的向量来补充。事实证明，我们的方法是一种更灵活的解决方案，可以容纳经历动态变化的可变数量的堆栈。然而，这种方法可能会带来更重的内存负担并带来更多的开销。

示例 2

该代码构成了一个 C++ 程序，该程序实现了称为“KStacks”的数据架构。这种数据结构通过应用一种称为“固定划分”的方法，可以在单个数组中存储多个堆栈。

“KStacks”类包含一系列成员函数，包括“push”、“pop”、“is_empty”和“is_full”。 “推入”操作允许将项目添加到指定的堆栈，而“弹出”功能则从指定的堆栈中消除顶部项目。

如果指定的堆栈未被占用，则“is_empty”函数返回true，如果所有堆栈都完全被占用，则“is_full”函数返回true。在主函数中，建立了三个容量为10的堆栈，并从每个堆栈中推入和弹出项目。最终，弹出的项目将显示在控制台上。

代码

#include <iostream>
#include <vector>
#include<climits>
using namespace std;

class Node {
public:
   int data;
   int prev;
   int next;
};

class KStacks {
  private:
   vector<Node> arr;
   vector<int> head;
   int n, k;
   int free;

  public:
   KStacks(int k, int n) {
   this->k = k;
   this->n = n;
   arr.resize(n);
   head.resize(k, -1);
   free = 0;
   for (int i = 0; i < n - 1; i++)
      arr[i].next = i + 1;
   arr[n - 1].next = -1;
}

void push(int item, int sn) {
   if (is_full()) {
      cout << "Stack Overflow\n";
      return;
   }

   int i = free;
   free = arr[i].next;
   arr[i].data = item;
   arr[i].prev = head[sn];
   arr[i].next = -1;

   if (head[sn] != -1)
      arr[head[sn]].next = i;
      head[sn] = i;
   }

   int pop(int sn) {
      if (is_empty(sn)) {
         cout << "Stack Underflow\n";
         return INT_MAX;
      }
      int i = head[sn];
      head[sn] = arr[i].prev;

      if (head[sn] != -1)
         arr[head[sn]].next = -1;

      arr[i].next = free;
      free = i;

      return arr[i].data;
   }

   bool is_empty(int sn) {
      return head[sn] == -1;
   }
   bool is_full() {
      return free == -1;
   }
};

int main() {
   KStacks ks(3, 10);
   ks.push(15, 2);
   ks.push(45, 2);

   ks.push(17, 1);
   ks.push(49, 1);
   ks.push(39, 1);

   ks.push(11, 0);
   ks.push(9, 0);
   ks.push(7, 0);

   cout << "Popped element from stack 2: " << ks.pop(2) <<endl;
   cout << "Popped element from stack 1: " << ks.pop(1) <<endl;
   cout << "Popped element from stack 0: " << ks.pop(0) <<endl;

   return 0;
}

输出

Popped element from stack 2: 45
Popped element from stack 1: 39
Popped element from stack 0: 7

结论

在本文中，我们讨论了使用 C++ 中的单个数据结构创建动态多堆栈的两种不同方法。两种方法都有其优点和缺点，选择使用哪一种方法将取决于当前问题的具体需求。

위 내용은 하나의 데이터 구조를 사용하여 여러 스택(K 스택) 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!