如何创建可合并栈（） _可合并栈

本文概述

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 = https://www.lsbin.com/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 = https://www.lsbin.com/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 = https://www.lsbin.com/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 .tailwhile (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

【如何创建可合并栈（）】输出如下：