如何创建可合并栈？

本文概述

• C ++
• Java
• Python3

使用以下操作设计堆栈。

a)push(Stack s, x)：将项目x添加到堆栈s

b)pop(Stack s)：从堆栈s中删除顶层项目

c)merge(堆栈s1, 堆栈s2)：将s2的内容合并到s1中。

所有上述操作的时间复杂度应为O(1)。

要是我们

使用数组

实现堆栈, 然后不可能在O(1)时间内完成合并, 因为我们必须执行以下步骤。

a)删除旧数组。

b)为s1创建一个新数组, 其大小等于s1的旧数组的大小加上s2的大小。

c)将s1和s2的旧内容复制到s1的新数组

上述操作需要O(n)时间。

我们可以用一个链表

有两个指针, 一个指向第一个节点的指针(当从头开始添加和删除元素时, 也用作顶部)。最后一个节点需要另一个指针, 以便我们可以在s1的末尾快速链接s2的链接列表。以下是所有操作。

a)push()：使用第一个指针在链接列表的开头添加新项。

b)pop()：使用第一个指针从头开始删除一个项目。

c)merge()：将第一个指针的第二个堆栈链接为第一个列表的最后一个指针的下一个指针。

如果我们不允许使用可以做吗

an

多余的指针？

我们可以用

循环链表

。这个想法是要跟踪链表中的最后一个节点。最后一个节点的下一个指示堆栈的顶部。

a)push()：将新项目添加到最后一个节点的下一个节点。

b)pop()：删除最后一个节点的下一个。

c)merge()：将第二个列表的顶部(倒数第二个)链接到第一个列表的顶部(倒数第二个)。并使第二个列表中的最后一个成为整个列表中的最后一个。

本文作者：

拉胡尔·古普塔(Rahul Gupta)

。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

上面的代码如下：

C ++

#include <iostream>
using namespace std;
 
class node {
public :
     int data;
     node* next;
};
 
class mystack {
public :
     node* head;
     node* tail;
 
     mystack()
     {
         head = NULL;
         tail = NULL;
     }
};
 
mystack* create()
{
     mystack* ms = new mystack(); //creating a new stack
     return ms;
}
 
void push( int data, mystack* ms)
{
     node* temp = new node();
     temp->data = data;
     temp->next = ms->head;
 
     //when pushing first element in the stack the tail
     //must be pointed by that first element
     if (ms->head == NULL)
         ms->tail = temp;
     
     ms->head = temp;
}
 
int pop(mystack* ms)
{
     if (ms->head == NULL) {
         cout <<"stack underflow" <<endl;
         return 0;
     }
     else {
         node* temp = ms->head;
         ms->head = ms->head->next;
         int popped = temp->data;
         delete temp;
         return popped;
     }
}
 
//making the next pointer of tail of
//one stack point to other stack
void merge(mystack* ms1, mystack* ms2)
{
if (ms1->head == NULL)
{
     ms1->head = ms2->head;
     ms1->tail = ms2->tail;
     return ;
}
     
ms1->tail->next = ms2->head;
ms1->tail = ms2->tail;
}
 
void display(mystack* ms)
{
     node* temp = ms->head;
     while (temp != NULL) {
         cout <<temp->data <<" " ;
         temp = temp->next;
     }
}
 
int main()
{
     mystack* ms1 = create();
     mystack* ms2 = create();
 
     push(6, ms1);
     push(5, ms1);
     push(4, ms1);
     push(9, ms2);
     push(8, ms2);
     push(7, ms2);
     merge(ms1, ms2);
     display(ms1);
}
 
//This code is contributed by jayshmi

Java

import java.io.*;
 
//The class Node contains the
//structure of our Node of
//the linked list
class Node
{
     Node next;
     Node prev;
     int data;
     
     //Create a node with the
     //given value
     Node( int value)
     {
         data = value;
         next = null ;
         prev = null ;
     }
}
 
class Stack{
     
private Node head;
private Node tail;
 
//Initialize stack class
//with its head and tail as null
Stack()
{
     head = null ;
     tail = null ;
}
 
public void push( int value)
{
     Node newNode = new Node(value);
     if (head == null )
     {
         head = newNode;
         head.next= null ;
         head.prev = null ;
         tail = newNode;
     }
     else
     {
         newNode.prev = tail;
         tail.next = newNode;
         tail = newNode;
     }
}
 
public void pop()
{
     if (head == null )
         System.out.println( "stack underflow" );
     
     if (head == tail)
     {
         head = null ;
         tail = null ;
     }
     else
     {
         Node n = tail;
         tail = tail.prev;
         n.prev = null ;
         tail.next = null ;
     }
}
 
public void merge(Stack s)
{
     head.prev = s.tail;
     s.tail.next = head;
     head = s.head;
     s.tail = null ;
     s.head = null ;
}
 
public void display()
{
     if (tail != null )
     {
         Node n = tail;
         while (n != null )
         {
             System.out.print(n.data + " " );
             n = n.prev;
         }
         System.out.println();
     }
     else
     {
         System.out.println( "Stack Underflow" );
     }
}
}
 
class GFG{
public static void main (String[] args)
{
     Stack ms1 = new Stack();
     Stack ms2 = new Stack();
     
     ms1.push( 6 );
     ms1.push( 5 );
     ms1.push( 4 );
     ms2.push( 9 );
     ms2.push( 8 );
     ms2.push( 7 );
     
     ms1.merge(ms2);
     ms1.display();
}
}
 
//This code is contributed by Ayaan

Python3

# The Node class for Linked List
class Node():
     def __init__( self , data):
         
         self . next = None
         self .prev = None
         self .data = data
 
class Stack():
     
     # Initialize stack class with
     # its head and tail as None
     def __init__( self ):
         
         self .head = None
         self .tail = None
 
     def push( self , data):
         
         new_node = Node(data)
         
         if ( self .head = = None ):
             self .head = new_node
             self .head. next = None
             self .head.prev = None
             self .tail = new_node
 
         else :
             new_node.prev = self .tail
             self .tail. next = new_node
             self .tail = new_node
 
     def pop( self ):
         
         if ( self .head = = None ):
             print ( "Stack underflow" )
 
         if ( self .head = = self .tail):
             self .head = None
             self .tail = None
 
         else :
             node = self .tail
             self .tail = self .tail.prev
             node.prev = None
             tail. next = None
 
     def merge( self , stack):
         
         self .head.prev = stack.tail
         stack.tail. next = self .head
         stack.tail = None
         stack.head = None
 
     def display( self ):
         
         if ( self .tail ! = None ):
             n = self .tail
             
             while (n ! = None ):
                 print (n.data, end = " " )
                 n = n.prev
 
             print ()
 
         else :
             print ( "Stack Underflow" )
 
# Driver code
ms1 = Stack()
ms2 = Stack()
 
ms1.push( 6 )
ms1.push( 5 )
ms1.push( 4 )
ms2.push( 9 )
ms2.push( 8 )
ms2.push( 7 )
 
ms1.merge(ms2)
ms1.display()
 
# This code is contributed by maheswaripiyush9

输出如下：

4 5 6 7 8 9