{"id":9214,"date":"2022-08-26T11:55:46","date_gmt":"2022-08-26T11:55:46","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9214"},"modified":"2022-12-14T11:44:02","modified_gmt":"2022-12-14T11:44:02","slug":"how-to-create-a-mergeable-stack","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/how-to-create-a-mergeable-stack\/","title":{"rendered":"How to create a mergeable stack?"},"content":{"rendered":"

\"\"<\/p>\n<\/p>\n

Let\u2019s assume there are 2 stacks. Stack A and Stack B. Now we are going to push elements in both the stacks.<\/p>\n

\"\"<\/p>\n

After Merge Operation we will push all elements of Stack B in Stack A.
\n\"\"<\/p>\n

Brief about Stack Data structure:<\/h3>\n

A stack is a linear data structure<\/a> that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack will be on the top of the stack.<\/p>\n

Our task is to design a stack having these functions:-<\/p>\n

    \n
  1. push(s, x)<\/strong>: push an element x into stack s. <\/li>\n
  2. pop(s)<\/strong>: pop element from stack s.<\/li>\n
  3. merge( s1, s2)<\/strong>: Merge stack s2 into s1. <\/li>\n<\/ol>\n

    Logic<\/strong>: <\/p>\n

      \n
    1. \n

      If we choose an Array<\/strong> data structure to create mergeable stack then the time complexity of the merge() function will be more than O(1). Because while merging stack 2 into stack 1 firstly, we have to create a new array for stack 1 of size equal to the number of elements in both stacks and then copy all elements of both stacks in this newly created array for stack 1. So, we can see that this approach is not optimised.<\/p>\n<\/li>\n

    2. \n

      What if we choose the Linked List<\/strong> data structure to create a mergeable stack?
      \na. We can use the linked list data structure with two pointers.
      \nb. The first pointer to point the first node of the linked list and the second pointer to point the last node of the linked list so that we can easily connect a new node to the linked list i.e (we don\u2019t have to traverse the whole linked list so that we can reach the end of the linked list to add a new node there).
      \nc. Another benefit of using two pointers is when the merge() function will be called at that moment we can easily join the last node of one linked list (stack 1) with the first node of another linked list (stack 2) and in this way, we will easily merge two linked list i.e two stacks.
      \nd. push()<\/strong>: To add a new node i.e (new element into the stack) to the linked list. The new node is added at the beginning of the linked list using the first pointer.
      \ne. pop()<\/strong>: To delete a node from the linked list. Remove a node from the beginning using the first pointer.
      \nf. merge()<\/strong>: This function is to merge stack 2\u2019s linked list with stack 1\u2019s linked list. The first pointer of the second stack is assigned to the next pointer of the last pointer of the first linked list.<\/p>\n<\/li>\n<\/ol>\n

      Code Implementation:<\/h3>\n\t\t\t\t\t\t