¿Cómo implementar una pila que admitirá las siguientes operaciones en una complejidad de tiempo O (1) ?
1) push() que agrega un elemento a la parte superior de la pila.
2) pop() que elimina un elemento de la parte superior de la pila.
3) findMiddle() que devolverá el elemento medio de la pila.
4) deleteMiddle() que eliminará el elemento central.
Push y pop son operaciones de pila estándar.
Método 1:
la pregunta importante es si se debe usar una lista enlazada o una array para la implementación de la pila.
Tenga en cuenta que necesitamos encontrar y eliminar el elemento central. Eliminar un elemento del medio no es O (1) para la array. Además, es posible que necesitemos mover el puntero del medio hacia arriba cuando empujamos un elemento y moverlo hacia abajo cuando hacemos pop(). En una lista enlazada individualmente, no es posible mover el puntero central en ambas direcciones.
La idea es utilizar una lista doblemente enlazada (DLL). Podemos eliminar el elemento medio en el tiempo O(1) manteniendo el puntero medio. Podemos mover el puntero medio en ambas direcciones usando los punteros anterior y siguiente.
A continuación se muestra la implementación de las operaciones push(), pop() y findMiddle(). Si hay elementos pares en la pila, findMiddle() devuelve el segundo elemento central. Por ejemplo, si la pila contiene {1, 2, 3, 4}, findMiddle() devolvería 3.
C++
/* C++ Program to implement a stack
that supports findMiddle() and
deleteMiddle in O(1) time */
#include <bits/stdc++.h>
using namespace std;
class myStack {
struct Node {
int num;
Node* next;
Node* prev;
Node(int num) { this->num = num; }
};
// Members of stack
Node* head = NULL;
Node* mid = NULL;
int size = 0;
public:
void push(int data)
{
Node* temp = new Node(data);
if (size == 0) {
head = temp;
mid = temp;
size++;
return;
}
head->next = temp;
temp->prev = head;
// update the pointers
head = head->next;
if (size % 2 == 1) {
mid = mid->next;
}
size++;
}
int pop()
{
int data=-1;
if (size != 0) {
data=head->num;
if (size == 1) {
head = NULL;
mid = NULL;
}
else {
head = head->prev;
head->next = NULL;
if (size % 2 == 0) {
mid = mid->prev;
}
}
size--;
}
return data;
}
int findMiddle()
{
if (size == 0) {
return -1;
}
return mid->num;
}
void deleteMiddle()
{
if (size != 0) {
if (size == 1) {
head = NULL;
mid = NULL;
}
else if (size == 2) {
head = head->prev;
mid = mid->prev;
head->next = NULL;
}
else {
mid->next->prev = mid->prev;
mid->prev->next = mid->next;
if (size % 2 == 0) {
mid = mid->prev;
}
else {
mid = mid->next;
}
}
size--;
}
}
};
int main()
{
myStack st;
st.push(11);
st.push(22);
st.push(33);
st.push(44);
st.push(55);
st.push(66);
st.push(77);
st.push(88);
st.push(99);
cout <<"Popped : "<< st.pop() << endl;
cout <<"Popped : "<< st.pop() << endl;
cout <<"Middle Element : "<< st.findMiddle() << endl;
st.deleteMiddle();
cout <<"New Middle Element : "<< st.findMiddle() << endl;
return 0;
}
// This code is contributed by Nikhil Goswami
// Updated by Amsavarthan LV
C
/* Program to implement a stack that supports findMiddle()
and deleteMiddle in O(1) time */
#include <stdio.h>
#include <stdlib.h>
/* A Doubly Linked List Node */
struct DLLNode {
struct DLLNode* prev;
int data;
struct DLLNode* next;
};
/* Representation of the stack data structure that supports
findMiddle() in O(1) time. The Stack is implemented
using Doubly Linked List. It maintains pointer to head
node, pointer to middle node and count of nodes */
struct myStack {
struct DLLNode* head;
struct DLLNode* mid;
int count;
};
/* Function to create the stack data structure */
struct myStack* createMyStack()
{
struct myStack* ms
= (struct myStack*)malloc(sizeof(struct myStack));
ms->count = 0;
return ms;
};
/* Function to push an element to the stack */
void push(struct myStack* ms, int new_data)
{
/* allocate DLLNode and put in data */
struct DLLNode* new_DLLNode
= (struct DLLNode*)malloc(sizeof(struct DLLNode));
new_DLLNode->data = new_data;
/* Since we are adding at the beginning,
prev is always NULL */
new_DLLNode->prev = NULL;
/* link the old list off the new DLLNode */
new_DLLNode->next = ms->head;
/* Increment count of items in stack */
ms->count += 1;
/* Change mid pointer in two cases
1) Linked List is empty
2) Number of nodes in linked list is odd */
if (ms->count == 1) {
ms->mid = new_DLLNode;
}
else {
ms->head->prev = new_DLLNode;
if (ms->count & 1) // Update mid if ms->count is odd
ms->mid = ms->mid->prev;
}
/* move head to point to the new DLLNode */
ms->head = new_DLLNode;
}
/* Function to pop an element from stack */
int pop(struct myStack* ms)
{
/* Stack underflow */
if (ms->count == 0) {
printf("Stack is empty\n");
return -1;
}
struct DLLNode* head = ms->head;
int item = head->data;
ms->head = head->next;
// If linked list doesn't become empty, update prev
// of new head as NULL
if (ms->head != NULL)
ms->head->prev = NULL;
ms->count -= 1;
// update the mid pointer when we have even number of
// elements in the stack, i,e move down the mid pointer.
if (!((ms->count) & 1))
ms->mid = ms->mid->next;
free(head);
return item;
}
// Function for finding middle of the stack
int findMiddle(struct myStack* ms)
{
if (ms->count == 0) {
printf("Stack is empty now\n");
return -1;
}
return ms->mid->data;
}
void deleteMiddle(struct myStack* ms)
{
if (ms->count == 0) {
printf("Stack is empty now\n");
return;
}
ms->count -= 1;
ms->mid->next->prev = ms->mid->prev;
ms->mid->prev->next = ms->mid->next;
if (ms->count % 2 != 0) {
ms->mid=ms->mid->next;
}else {
ms->mid=ms->mid->prev;
}
}
// Driver program to test functions of myStack
int main()
{
/* Let us create a stack using push() operation*/
struct myStack* ms = createMyStack();
push(ms, 11);
push(ms, 22);
push(ms, 33);
push(ms, 44);
push(ms, 55);
push(ms, 66);
push(ms, 77);
push(ms, 88);
push(ms, 99);
printf("Popped : %d\n", pop(ms));
printf("Popped : %d\n", pop(ms));
printf("Middle Element : %d\n", findMiddle(ms));
deleteMiddle(ms);
printf("New Middle Element : %d\n", findMiddle(ms));
return 0;
}
//Updated by Amsavarthan Lv
Java
/* Java Program to implement a stack that supports
findMiddle() and deleteMiddle in O(1) time */
/* A Doubly Linked List Node */
class DLLNode {
DLLNode prev;
int data;
DLLNode next;
DLLNode(int data) { this.data = data; }
}
/* Representation of the stack data structure that
supports findMiddle() in O(1) time. The Stack is
implemented using Doubly Linked List. It maintains
pointer to head node, pointer to middle node and
count of nodes */
public class myStack {
DLLNode head;
DLLNode mid;
DLLNode prev;
DLLNode next;
int size;
/* Function to push an element to the stack */
void push(int new_data)
{
/* allocate DLLNode and put in data */
DLLNode new_node = new DLLNode(new_data);
// if stack is empty
if (size == 0) {
head = new_node;
mid = new_node;
size++;
return;
}
head.next = new_node;
new_node.prev = head;
head = head.next;
if (size % 2 != 0) {
mid = mid.next;
}
size++;
}
/* Function to pop an element from stack */
int pop()
{
int data = -1;
/* Stack underflow */
if (size == 0) {
System.out.println("Stack is empty");
// return -1;
}
if (size != 0) {
if (size == 1) {
head = null;
mid = null;
}
else {
data = head.data;
head = head.prev;
head.next = null;
if (size % 2 == 0) {
mid = mid.prev;
}
}
size--;
}
return data;
}
// Function for finding middle of the stack
int findMiddle()
{
if (size == 0) {
System.out.println("Stack is empty now");
return -1;
}
return mid.data;
}
void deleteMiddleElement()
{
// This function will not only delete the middle
// element
// but also update the mid in case of even and
// odd number of Elements
// when the size is even then findmiddle() will show the
// second middle element as mentioned in the problem
// statement
if (size != 0) {
if (size == 1) {
head = null;
mid = null;
}
else if (size == 2) {
head = head.prev;
mid = mid.prev;
head.next = null;
}
else {
mid.next.prev = mid.prev;
mid.prev.next = mid.next;
if (size % 2 == 0) {
mid = mid.prev;
}
else {
mid = mid.next;
}
}
size--;
}
}
// Driver program to test functions of myStack
public static void main(String args[])
{
myStack ms = new myStack();
ms.push(11);
ms.push(22);
ms.push(33);
ms.push(44);
ms.push(55);
ms.push(66);
ms.push(77);
ms.push(88);
ms.push(99);
System.out.println("Popped : " + ms.pop());
System.out.println("Popped : " + ms.pop());
System.out.println("Middle Element : "
+ ms.findMiddle());
ms.deleteMiddleElement();
System.out.println("New Middle Element : "
+ ms.findMiddle());
}
}
// This code is contributed by Abhishek Jha
// Updated by Amsavarthan Lv
Python3
''' Python3 Program to implement a stack
that supports findMiddle()
and deleteMiddle in O(1) time '''
''' A Doubly Linked List Node '''
class DLLNode:
def __init__(self, d):
self.prev = None
self.data = d
self.next = None
''' Representation of the stack
data structure that supports
findMiddle() in O(1) time. The
Stack is implemented using
Doubly Linked List. It maintains
pointer to head node, pointer
to middle node and count of
nodes '''
class myStack:
def __init__(self):
self.head = None
self.mid = None
self.count = 0
''' Function to create the stack data structure '''
def createMyStack():
ms = myStack()
ms.count = 0
return ms
''' Function to push an element to the stack '''
def push(ms, new_data):
''' allocate DLLNode and put in data '''
new_DLLNode = DLLNode(new_data)
''' Since we are adding at the beginning,
prev is always NULL '''
new_DLLNode.prev = None
''' link the old list off the new DLLNode '''
new_DLLNode.next = ms.head
''' Increment count of items in stack '''
ms.count += 1
''' Change mid pointer in two cases
1) Linked List is empty
2) Number of nodes in linked list is odd '''
if(ms.count == 1):
ms.mid = new_DLLNode
else:
ms.head.prev = new_DLLNode
# Update mid if ms->count is odd
if((ms.count % 2) != 0):
ms.mid = ms.mid.prev
''' move head to point to the new DLLNode '''
ms.head = new_DLLNode
''' Function to pop an element from stack '''
def pop(ms):
''' Stack underflow '''
if(ms.count == 0):
print("Stack is empty")
return -1
head = ms.head
item = head.data
ms.head = head.next
# If linked list doesn't become empty,
# update prev of new head as NULL
if(ms.head != None):
ms.head.prev = None
ms.count -= 1
# update the mid pointer when
# we have even number of elements
# in the stack, i,e move down
# the mid pointer.
if(ms.count % 2 == 0):
ms.mid = ms.mid.next
return item
# Function for finding middle of the stack
def findMiddle(ms):
if(ms.count == 0):
print("Stack is empty now")
return -1
return ms.mid.data
def deleteMiddle(ms):
if(ms.count == 0):
print("Stack is empty now")
return
ms.count-=1
ms.mid.next.prev=ms.mid.prev
ms.mid.prev.next=ms.mid.next
if ms.count %2==1:
ms.mid=ms.mid.next
else:
ms.mid=ms.mid.prev
# Driver code
if __name__ == '__main__':
ms = createMyStack()
push(ms, 11)
push(ms, 22)
push(ms, 33)
push(ms, 44)
push(ms, 55)
push(ms, 66)
push(ms, 77)
push(ms, 88)
push(ms, 99)
print("Popped : " +
str(pop(ms)))
print("Popped : " +
str(pop(ms)))
print("Middle Element : " +
str(findMiddle(ms)))
deleteMiddle(ms)
print("New Middle Element : " +
str(findMiddle(ms)))
# This code is contributed by rutvik_56.
# Updated by Amsavarthan Lv
C#
/* C# Program to implement a stack
that supports findMiddle()
and deleteMiddle in O(1) time */
using System;
class GFG {
/* A Doubly Linked List Node */
public class DLLNode {
public DLLNode prev;
public int data;
public DLLNode next;
public DLLNode(int d) { data = d; }
}
/* Representation of the stack
data structure that supports
findMiddle() in O(1) time. The
Stack is implemented using
Doubly Linked List. It maintains
pointer to head node, pointer
to middle node and count of
nodes */
public class myStack {
public DLLNode head;
public DLLNode mid;
public int count;
}
/* Function to create the stack data structure */
myStack createMyStack()
{
myStack ms = new myStack();
ms.count = 0;
return ms;
}
/* Function to push an element to the stack */
void push(myStack ms, int new_data)
{
/* allocate DLLNode and put in data */
DLLNode new_DLLNode = new DLLNode(new_data);
/* Since we are adding at the beginning,
prev is always NULL */
new_DLLNode.prev = null;
/* link the old list off the new DLLNode */
new_DLLNode.next = ms.head;
/* Increment count of items in stack */
ms.count += 1;
/* Change mid pointer in two cases
1) Linked List is empty
2) Number of nodes in linked list is odd */
if (ms.count == 1) {
ms.mid = new_DLLNode;
}
else {
ms.head.prev = new_DLLNode;
// Update mid if ms->count is odd
if ((ms.count % 2) != 0)
ms.mid = ms.mid.prev;
}
/* move head to point to the new DLLNode */
ms.head = new_DLLNode;
}
/* Function to pop an element from stack */
int pop(myStack ms)
{
/* Stack underflow */
if (ms.count == 0) {
Console.WriteLine("Stack is empty");
return -1;
}
DLLNode head = ms.head;
int item = head.data;
ms.head = head.next;
// If linked list doesn't become empty,
// update prev of new head as NULL
if (ms.head != null)
ms.head.prev = null;
ms.count -= 1;
// update the mid pointer when
// we have even number of elements
// in the stack, i,e move down
// the mid pointer.
if (ms.count % 2 == 0)
ms.mid = ms.mid.next;
return item;
}
// Function for finding middle of the stack
int findMiddle(myStack ms)
{
if (ms.count == 0) {
Console.WriteLine("Stack is empty now");
return -1;
}
return ms.mid.data;
}
void deleteMiddle(myStack ms){
if (ms.count == 0) {
Console.WriteLine("Stack is empty now");
return;
}
ms.count-=1;
ms.mid.next.prev=ms.mid.prev;
ms.mid.prev.next=ms.mid.next;
if(ms.count %2!=0){
ms.mid=ms.mid.next;
}else{
ms.mid=ms.mid.prev;
}
}
// Driver code
public static void Main(String[] args)
{
GFG ob = new GFG();
myStack ms = ob.createMyStack();
ob.push(ms, 11);
ob.push(ms, 22);
ob.push(ms, 33);
ob.push(ms, 44);
ob.push(ms, 55);
ob.push(ms, 66);
ob.push(ms, 77);
ob.push(ms, 88);
ob.push(ms, 99);
Console.WriteLine("Popped : " + ob.pop(ms));
Console.WriteLine("Popped : " + ob.pop(ms));
Console.WriteLine("Middle Element : "
+ ob.findMiddle(ms));
ob.deleteMiddle(ms);
Console.WriteLine("New Middle Element : "
+ ob.findMiddle(ms));
}
}
// This code is contributed
// by Arnab Kundu
// Updated by Amsavarthan Lv
C++
#include <bits/stdc++.h>
using namespace std;
class myStack {
stack<int> st;
deque<int> dq;
public:
void add(int data)
{
dq.push_back(data);
if (dq.size() > st.size() + 1) {
int temp = dq.front();
dq.pop_front();
st.push(temp);
}
}
void pop()
{
int data = dq.back();
dq.pop_back();
if (st.size() > dq.size()) {
int temp = st.top();
st.pop();
dq.push_front(temp);
}
}
int getMiddleElement() {
return dq.front();
}
void deleteMiddleElement()
{
dq.pop_front();
if (st.size() > dq.size()) { // new middle element
int temp = st.top(); // should come at front of deque
st.pop();
dq.push_front(temp);
}
}
};
int main()
{
myStack st;
st.add(2);
st.add(5);
cout << "Middle Element: " << st.getMiddleElement() << endl;
st.add(3);
st.add(7);
st.add(4);
cout << "Middle Element: " << st.getMiddleElement() << endl;
st.deleteMiddleElement();
cout << "Middle Element: " << st.getMiddleElement() << endl;
st.deleteMiddleElement();
cout << "Middle Element: " << st.getMiddleElement() << endl;
st.pop();
st.pop();
st.deleteMiddleElement();
}
//By- Vijay Chadokar
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