elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  colas dobles
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: colas dobles  (Leído 1,402 veces)
Beginner Web


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
colas dobles
« en: 15 Octubre 2018, 03:56 am »

Hola, queria preguntarles que operaciones se de colas se modifican cuando usamos bicolas, tengo hecho esto pero no entiendo el comportamiento con arreglos con listas es mucho mas facil ayuda u.u  :(

Código
  1. #include <iostream>
  2. #include <stdlib.h>
  3.  
  4. using namespace std;
  5.  
  6. const int MAX=6;
  7. typedef int contenedor[MAX];
  8. typedef struct tcola{
  9. contenedor datos;
  10. int final, frente;
  11. };
  12.  
  13. void init_queue(tcola &q);
  14. void push_queue(tcola &q, int nuevo, bool ultimo);
  15. bool full_queue(tcola q);
  16. bool empty_queue(tcola q);
  17. int pop_queue(tcola &q);
  18. int top_queue(tcola q);
  19. int bottom_queue(tcola q);
  20. int next(int indice);
  21. int prev(int indice);
  22.  
  23. int main()
  24. {
  25. int dato;
  26. tcola q;
  27. bool opcion;
  28. init_queue(q);
  29. while(full_queue(q)==false){
  30. cout<<"Ingrese dato: ";
  31. cin>>dato;
  32. cout<<"1. Agregar por final"<<endl;
  33. cout<<"0. Agregar por frente"<<endl;
  34. cin>>opcion;
  35. push_queue(q,dato,opcion);
  36. }
  37. q.frente=MAX-1;
  38. q.final=MAX-2;
  39. while(empty_queue(q)==false){
  40. cout<<pop_queue(q);
  41. }
  42. cout<<endl;
  43. system("pause");
  44. }
  45.  
  46. void init_queue(tcola &q)
  47. {
  48. q.final=MAX-1;
  49. q.frente=MAX-1;
  50. }
  51.  
  52. void push_queue(tcola &q, int nuevo, bool ultimo)
  53. {
  54. if(full_queue(q)==true)
  55. cout<<"COLA LLENA"<<endl;
  56. else{
  57. if(ultimo==true){
  58. q.final=next(q.final);
  59. q.datos[q.final]=nuevo;
  60. }
  61. else{
  62. q.frente=prev(q.frente);
  63. q.datos[q.frente]=nuevo;
  64. }
  65. }
  66. }
  67.  
  68. bool full_queue(tcola q)
  69. {
  70. return next(q.final)==q.frente;
  71. }
  72.  
  73. bool empty_queue(tcola q)
  74. {
  75. return q.frente==q.final;
  76. }
  77.  
  78. int pop_queue(tcola &q)
  79. {
  80. int aux;
  81. if(empty_queue(q)==true)
  82. aux=-1;
  83. else{
  84. q.frente=next(q.frente);
  85. aux=q.datos[q.frente];
  86. }
  87. return aux;
  88. }
  89.  
  90. int top_queue(tcola q)
  91. {
  92. int aux;
  93. if(empty_queue(q)==true)
  94. aux=-1;
  95. else{
  96. aux=q.datos[next(q.frente)];
  97. }
  98. return aux;
  99. }
  100.  
  101. int bottom_queue(tcola q)
  102. {
  103. int aux;
  104. if(empty_queue(q)==true)
  105. aux=-1;
  106. else{
  107. aux=q.datos[q.final];
  108. }
  109. return aux;
  110. }
  111.  
  112. int next(int indice)
  113. {
  114. if(indice==MAX-1)
  115. indice=0;
  116. else
  117. indice++;
  118. return indice;
  119. }
  120.  
  121. int prev(int indice)
  122. {
  123. if(indice==0){
  124. indice=MAX-1;
  125. }
  126. else{
  127. indice--;
  128. }
  129. return indice;
  130. }
  131.  


En línea

7w7
Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: colas dobles
« Respuesta #1 en: 15 Octubre 2018, 05:38 am »

Depende de la forma en que estén unidas las dos colas.
He llegado a programar diferentes variedades como colas que extraían (si no estaba vacía) alternativamente, de una y luego de otra... también por prioridad extrayendo de la cola que tenga un valor que cumpla una cierta condición (por ejemplo el menor)...

En general al margen de otras propiedades que se pueden añadir, la única operación extra suele ser extraer de la cola y encolarla de nuevo por una de las dos. requiere un parámetro para señalar a cual de ellas se refiere, basta un buleano para decidirlo, pués son solo 2.

PopAndPush( cola)


Sobre las colas realizadas con arrays:
La dificultad de los arrays, es que al extraer un elemento, los demás no bajan 'por su peso'.... se soluciona moviendo el índice de lo que es el tope y la cima según convenga...

Sea un elemento lo definido entre 2 rayas verticales: "||"
Y sea una cola vacía de 10 elementos, el fondo y la cima ahora mismo son 0,
   -------------
------------->|--->
   -------------

después de meter 4 elementos (cuenta 4 espacios entre las 5 rayitas), el fondo es 0, la cima 4
   -------------
--------->|||||--->
   -------------

ahora sacamos un elemento... el fondo es 1 y la cima sigue siendo 4
   -------------
--------->||||--->
   -------------

Metemos 4 elementos más (hay 7), el fondo sigue siendo 1, la cima suma 4 más (ahora es 8).
   -------------
----->||||||||--->
   -------------
Ahora extraemos 4 (quedan 3 otra vez), el fondo suma 4 (ahora es 5), la cima no cambia (sigue siendo 8)...
       -------------
----->||||--->
       -------------
Extraemos 1 elemento más, el fondo ahora suma 1 (pasa a valer 5), la cima no cambia (sigue siendo 8 y quedan aún 2 elementos en la cola)
       -------------
----->|||--->
       -------------
Ahora metemos 4 elementos (pasa a haber 6), el fondo no cambia cuando se mete (sigue siendo 5), la cima suma 4, (pasa a ser 12) pero como excede el tamaño del array ... verás como se solventa.
       -------------
---->||||--->||||
       -------------
solo caben 1 ahí, los otros 3 se colocan al otro lado del array... es decir en el índice 0, 1 y 2.
La cima ahora está donde pongo la '¡' y el fondo donde pongo '!'
       -------------
---->|||!---->¡|||
       -------------

Así ves que siempre se suma... en la cima cuando se añaden, en la cola cuando se sacan.
Y entonces resulta circular, pero transparente desde fuera. como nos daba 12 y queda fuera de rango, hay que modularlo...

cima = (((cima + añadidos) modulo size-1) -1)
Se puede resumir, puesto que si "size-1" y luego "-1" se resume en "modulo size"... Esto porque el array se basa en indice 0.

Luego una función resulta ideal para llevar la cuenta de cima y fondo, lo que al final facilita enormemente la tarea...
Código:
entero Funcion Recalcular(previo, cambios)
   devolver ((previo + cambios) modulo size)
fin funcion

 // se añaden 4 elementos
cima = Recalcular(cima, 4)
size  += 4
 
 // se sacan 2 elementos
fondo = Recalcular(fondo, 2)
size -= 2

Natualmente como se añade uno a uno, y se sacan uno a uno... el parámetro cambios solo tendrá valores: '+1' y '-1' y allí dentro mismo puede actualizarse también size.

Código:
entero Funcion Recalcular(previo, cambio)
   devolver ((previo + cambio) modulo size)
   size += cambio  // suma 1 o resta uno según el signo de 'cambio'.
fin funcion

 // después de añadir 1 elemento
cima = Recalcular(cima, 1)

 // después de sacar 1 elemento
fondo = Recalcular(fondo, -1)






« Última modificación: 15 Octubre 2018, 05:47 am por NEBIRE » En línea

Beginner Web


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
Re: colas dobles
« Respuesta #2 en: 18 Octubre 2018, 02:29 am »

Muchas gracias no lei todo pero creo que me sirvio me quedo asi.

Bicola entrada restringida:
Código
  1. int pop_queue(tcola &q, bool ultimo)
  2. {
  3. int aux;
  4. if(empty_queue(q)==true)
  5. aux=-1;
  6. else{
  7. if(ultimo==false){
  8. aux=q.datos[q.final];//Aqui tenia sueño y puse
  9. q.final=prev(q.final);//esta linea antes que la de arriba
  10. }
  11. else{
  12. q.frente=next(q.frente);
  13. aux=q.datos[q.frente];
  14. }
  15. q.contador--;
  16. }
  17. return aux;
  18. }

Bicola salida restringida:
Código
  1. void push_queue(tcola &q, int nuevo, bool ultimo)
  2. {
  3. if(full_queue(q)==true)
  4. cout<<"COLA LLENA"<<endl;
  5. else{
  6. if(ultimo==true){
  7. q.final=next(q.final);
  8. q.datos[q.final]=nuevo;
  9. }
  10. else{
  11. q.datos[q.frente]=nuevo;//Aqui
  12. q.frente=prev(q.frente);//lo mismo
  13. }
  14. }
  15. }
« Última modificación: 18 Octubre 2018, 02:42 am por Beginner Web » En línea

7w7
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
aclaracion de listas dobles enlazadas
Programación C/C++
josue_tux 2 3,731 Último mensaje 15 Marzo 2011, 14:41 pm
por Don Pollo
Reemplazar comillas dobles dentro de comillas dobles.
.NET (C#, VB.NET, ASP)
seba123neo 2 7,956 Último mensaje 22 Agosto 2012, 20:25 pm
por seba123neo
ayuda con pilas dobles
Java
gibi77 0 1,638 Último mensaje 7 Septiembre 2012, 02:03 am
por gibi77
Procesos dobles
Windows
DavEmmanuel 2 2,544 Último mensaje 24 Marzo 2015, 00:12 am
por DavEmmanuel
Punteros Dobles en C
Programación C/C++
GonzaloRamirez 3 3,163 Último mensaje 7 Diciembre 2019, 06:57 am
por AlbertoBSD
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines