Diseñe una pila con las siguientes operaciones.
- push (Pila s, x): agrega un elemento x a la pila s
- pop (Pila s): elimina el elemento superior de la pila s
- merge(Stack s1, Stack s2): fusiona el contenido de s2 en s1.
La complejidad temporal de todas las operaciones anteriores debe ser O(1).
Si usamos la implementación de array de la pila, entonces no es posible realizar la combinación en el tiempo O (1), ya que tenemos que realizar los siguientes pasos.
- Eliminar arrays antiguas.
- Cree una nueva array para s1 con un tamaño igual al tamaño de la array anterior para s1 más el tamaño de s2.
- Copie los contenidos antiguos de s1 y s2 en una nueva array para s1
Las operaciones anteriores toman tiempo O(n).
Podemos usar una lista enlazada con dos punteros, un puntero al primer Node (también se usa como parte superior cuando se agregan y eliminan elementos desde el principio). El otro puntero es necesario para el último Node para que podamos vincular rápidamente la lista vinculada de s2 al final de s1. Las siguientes son todas las operaciones.
- push(): agrega el nuevo elemento al comienzo de la lista vinculada usando el primer puntero.
- pop(): elimina un elemento desde el principio usando el primer puntero.
- merge(): vincula el primer puntero de la segunda pila como el siguiente del último puntero de la primera lista.
¿Podemos hacerlo si no se nos permite usar un puntero adicional?
Podemos hacerlo con una lista enlazada circular . La idea es hacer un seguimiento del último Node en la lista enlazada. El siguiente del último Node indica la parte superior de la pila.
- push(): agrega el nuevo elemento como el siguiente del último Node.
- pop(): elimina el siguiente del último Node.
- merge() : Vincula la parte superior (penúltimo) de la segunda lista con la parte superior (penúltimo) de la primera lista. Y hace último de la segunda lista como último de toda la lista.
El código para lo anterior se da a continuación:
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
del node
self.tail.next = None
# self (stack) is linked on top (which is tail here) of stack
# self becomes the merged stack
def merge(self, stack):
if stack.head == None: return # if stack is empty self stays as it is
if self.head == None: # self (stack) is empty -> point to stack
self.head = stack.head
self.tail = stack.tail
return
self.head.prev = stack.tail # link self on top of stack
stack.tail.nxt = self.head
self.head = stack.head # set new head for self (stack)
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()
while ms1.head != ms1.tail:
ms1.pop ()
print ("check pop all elements until head == tail (one element left)")
print ("on merged stack: ", end = "")
ms1.display()
# This code is contributed by maheswaripiyush9
C#
using System;
// The class Node contains the
// structure of our Node of
// the linked list
public
class Node {
public
Node next;
public
Node prev;
public
int data;
// Create a node with the
// given value
public
Node(int value)
{
data = value;
next = null;
prev = null;
}
}
public
class Stack {
private Node head;
private Node tail;
// Initialize stack class
// with its head and tail as null
public 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)
Console.WriteLine("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) {
Console.Write(n.data + " ");
n = n.prev;
}
Console.WriteLine();
}
else {
Console.WriteLine("Stack Underflow");
}
}
}
public 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 contributed by aashish1995
Producción
4 5 6 7 8 9
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA