병합 가능한 스택을 만드는 방법은 무엇입니까?

우리는 디자인하고 창조해야합니다 스택 일정한 시간에 작업을 수행합니다. 병합 가능한 스택을 만드는 방법에 대한 한 가지 문제가 있습니다. 여기서 우리는 두 스택을 병합하기 위해 아래 작업을 수행합니다.

• push (element) : 스택에 요소를 삽입합니다.
• pop () : 스택에서 최상위 요소를 제거합니다.
• 병합 (스택 1, 스택 2) : 2 개의 스택을 병합하거나 결합합니다.

핀

예

다음은 병합 가능한 스택을 만드는 몇 가지 예입니다.

입력 

푸시 (1, s1);
푸시 (2, s1);
푸시 (3, s1);
푸시 (4, s2);
푸시 (5, s2);
푸시 (6, s2);
merge (s1, s2);
디스플레이 (들 1);

산출 

병합 된 스택 : 3 2 1 6 5 4

입력 

푸시 (1, s1);
푸시 (5, s2);
푸시 (6, s2);
merge (s1, s2);
디스플레이 (들 1);

산출 

병합 된 스택 : 1 6 5

암호알고리즘

여기에서 먼저 두 개의 스택을 만든 다음 병합 가능한 스택을 만듭니다.

1. 두 스택 s1 및 s2를 만듭니다.
2. 정수 값 및 스택을 매개 변수로 허용하는 함수 푸시를 작성하십시오. 그 안에 노드를 초기화하십시오. 새 노드의 데이터를 주어진 정수로 업데이트하고 스택의 헤드에 연결합니다.
3. 스택의 헤드가 null 인 경우 스택의 꼬리를 새 노드로 업데이트합니다. 그렇지 않으면 스택의 헤드를 새 노드로 업데이트합니다.
4. 스택을 매개 변수로 받아들이는 함수 팝을 만듭니다. 스택의 헤드가 null인지 확인 "stack underflow"인쇄 그렇지 않으면 스택의 헤드를 새 노드에 저장하고 헤드를 다음 헤드로 업데이트합니다. 새 노드의 데이터를 반환하고 노드를 삭제합니다.
5. 두 스택을 매개 변수로 받아들이는 함수 병합을 만듭니다. 스택 1의 머리가 null 업데이트인지 확인하고 스택 2의 머리로 머리를 업데이트하고 스택 2의 꼬리로 꼬리를 반환하고 반환합니다.
6. 그렇지 않으면 스택 1의 꼬리를 스택 2의 머리로 업데이트하고 스택 1의 꼬리를 스택 2의 꼬리로 업데이트합니다.

병합 가능한 스택을 만드는 C ++ 프로그램

#include <iostream> 
using namespace std; 
  
class node{ 
    public: 
        int data; 
        node* next; 
}; 
  
class newStack{ 
    public: 
        node* head; 
        node* tail; 
      
        newStack(){ 
            head = NULL; 
            tail = NULL; 
        } 
}; 
  
newStack* create(){ 
    newStack* ns = new newStack(); 
    return ns; 
} 
  
void push(int data, newStack* ns){ 
    node* temp = new node(); 
    temp->data = data; 
    temp->next = ns->head; 
  
    if(ns->head == NULL)   
        ns->tail = temp;  
      
    ns->head = temp; 
} 
  
int pop(newStack* ns){ 
    if (ns->head == NULL) { 
        cout << "stack underflow" << endl; 
        return 0; 
    } 
    else{ 
        node* temp = ns->head; 
        ns->head = ns->head->next; 
        int popped = temp->data; 
        delete temp; 
        return popped; 
    } 
} 
  
void merge(newStack* ns1, newStack* ns2){ 
   if (ns1->head == NULL){ 
       ns1->head = ns2->head; 
       ns1->tail = ns2->tail;  
       return; 
   } 
     
   ns1->tail->next = ns2->head; 
   ns1->tail = ns2->tail;  
} 
  
void display(newStack* ns){ 
    node* temp = ns->head; 
    cout<<"Merged Stack : ";
    while(temp != NULL) { 
        cout << temp->data << " "; 
        temp = temp->next; 
    }  
} 
  
int main(){ 
    newStack* s1 = create(); 
    newStack* s2 = create(); 
  
    push(1, s1); 
    push(2, s1); 
    push(3, s1); 
    
    push(4, s2); 
    push(5, s2); 
    push(6, s2); 
    
    merge(s1, s2); 
    display(s1); 
    
    return 0;
}

Merged Stack : 3 2 1 6 5 4

병합 가능한 스택 생성을위한 복잡성 분석

시간 복잡성 : O (1) 모든 작업이 일정한 시간 즉 O (1)을 사용하고 있기 때문입니다.

보조 공간 : 추가 공간을 사용하지 않기 때문에 O (1).

참조