¿Qué significa Push and Pop para Stacks?

Question

larga historia corta mi profesor es basura, y nos estaba mostrando infijo para prefijar pilas a través de un retroproyector y su sombra bigass estaba bloqueando todo así que me perdí las cosas importantes

se estaba refiriendo a push y pop, push = 0 pop = x

dio un ejemplo, pero no puedo ver cómo se pone su respuesta en absoluto,

2*3/(2-1)+5*(4-1) 

paso 1 Reverse: )1-4(*5+)1-2(/3*2 bien veo que

h E A continuación, pasó a escribir de X y las operaciones de O e I quedó totalmente perdida

respuesta 14-5*12-32*/+ entonces se invierte de nuevo para obtener +/*23-21*5-41

si alguien podría explicarme la emergente empuje por lo que pude entender yo estaría muy agradecido, He buscado en línea, pero muchas cosas que encuentro parece ser un paso por encima de esto, así que realmente necesito entender aquí primero

Answer 1

Una pila es una estructura de datos LIFO (último en entrar primero en salir). Las operaciones push y pop son simples. Push pone algo en la pila, el pop se quita algo. Pones en la parte superior y quitas la parte superior para preservar el orden de LIFO.

corregir - corregido de FIFO, a LIFO. Facepalm!

para ilustrar, se empieza con una pila en blanco

|

luego empuja 'x'

| 'X'

continuación, se presiona 'y'

| 'X' 'y'

entonces que el pop

| 'x'

Answer 2

Una pila en principio es bastante simple: imagine un clip de rifle - Solo puede acceder a la bala superior - sacarlo se llama "pop", insertando uno nuevo se llama "push".
Un ejemplo muy útil para eso es para aplicaciones que le permiten "deshacer".
Imagine que guarda cada estado de la aplicación en una pila. p.ej. el estado de la aplicación después de cada tipo que hace el usuario.
Ahora cuando el usuario presiona "deshacer" simplemente "pop" el estado anterior de la pila. Para cada acción que hace el usuario, "empuja" el nuevo estado a la pila (eso, por supuesto, está simplificado).
Acerca de lo que su profesor específicamente estaba haciendo - para explicarlo, sería útil más información ..

Answer 3

Esperamos que esto le ayude a visualizar una pila y cómo funciona.

vacío Pila:

|  | 
|  | 
|  | 
------- 

después de empujar A, se obtiene:

|  | 
|  | 
| A | 
------- 

después de empujar B, se obtiene:

|  | 
| B | 
| A | 
------- 

Después de estallar, se obtiene:

|  | 
|  | 
| A | 
------- 

después de empujar C, se obtiene:

|  | 
| C | 
| A | 
------- 

Después de estallar, se obtiene:

|  | 
|  | 
| A | 
------- 

Después de estallar, se obtiene:

|  | 
|  | 
|  | 
------- 

Answer 4

Ok. Como explicaron los otros respondedores, una pila es una estructura de datos de último en entrar, primero en salir. Agrega un elemento a la parte superior de la pila con una operación de inserción. Usted toma un elemento de la parte superior con una operación Pop. Los elementos se eliminan en orden inverso al orden en que se insertaron (por lo tanto, último en entrar, primero en salir). Por ejemplo, si empuja los elementos 1,2,3 en ese orden, el número 3 estará en la parte superior de la pila. Una operación Pop lo eliminará (fue el último en entrar) y dejará 2 en la parte superior de la pila.

En cuanto al resto de la conferencia, el profesor trató de describir una máquina basada en la pila que evalúa expresiones aritméticas. La máquina funciona sacando continuamente 3 elementos de la parte superior de la pila. Los dos primeros elementos son operandos y el tercero es un operador (+, -, *, /). A continuación, aplica este operador en los operandos y empuja el resultado a la pila. El proceso continúa hasta que solo haya un elemento en la pila, que es el valor de la expresión.

Supongamos que comenzamos presionando los valores "+/* 23-21 * 5-41" en orden de izquierda a derecha en la pila. A continuación, mostramos 3 elementos de la parte superior. El último en entrar es el primero en salir, lo que significa que los primeros 3 elementos son "1", "4" y "-" en ese orden. Empujamos el número 3 (el resultado de 4-1) en la pila, y luego mostramos los tres elementos superiores: 3, 5, *. Presione el resultado, 15, en la pila, y así sucesivamente.

Answer 5

La analogía del clip de rifle publicado por Oren A es bastante bueno, pero intentaré con otro e intentaré anticipar lo que el instructor estaba tratando de transmitir.

una pila, como su nombre sugiere es una disposición de "cosas" que tiene:

• Una tapa
• Una parte inferior
• un ordenamiento en entre la parte superior y la parte inferior (por ejemplo, segunda desde la arriba, tercero desde abajo).

(pensar en ella como una pila literal de libros sobre su escritorio y sólo se puede tomar algo de la parte superior)

empujar algo en la pila significa "colocándolo en la parte superior". Saltar algo de la pila significa "sacar la 'cosa' superior de la pila.

Un uso simple es para invertir el orden de las palabras. Digamos que quiero invertir la palabra: "palomitas de maíz". Empujo cada letra de izquierda a derecha (las 7 letras), y enseño 7 letras y terminarán en orden inverso. Parece que esto era lo que estaba haciendo con esas expresiones.

de empuje (p) de empuje (o) de empuje (p) de empuje (c) de empuje (o) de empuje (r) de empuje (n)

después de empujar la palabra completa, la pila parece:

| n | <- top 
    | r | 
    | o | 
    | c | 
    | p | 
    | o | 
    | p | <- bottom (first "thing" pushed on an empty stack) 
    ====== 

cuando me pop() siete veces, consigo las letras en este orden:

n, R, O, C, P, O, P

conversión de infijo/postfix/prefijo es un ejemplo patológico en la informática en la enseñanza de las pilas:

Infix to Postfix conversion.

Mensaje solución de conversión a una expresión infija es bastante sencillo:

(expresión exploración desde de izquierda a derecha)

1. Para cada número (operando) empújelo en la pila.
2. Cada vez que encuentre un operador (+, -, /, *), salte dos veces de la pila y coloque al operador entre ellas. Empuje que en la pila:

Así que si tenemos 53 + 2 * Podemos convertir a INFIX que en los siguientes pasos:

1. empuje 5.
2. empuje 3.
3. Encontrados +: pop 3, pop 5, push 5 + 3 en la pila (sea coherente con el pedido de 5 y 3)
4. Push 2.
5. Encountered *: pop 2, pop (5 + 3), push (2 * (5 + 3)).

* Cuando llegue al final de la expresión, si se formó correctamente, la pila solo debe contener un elemento.

Al introducir 'x' y 'o' puede haber estado usándolos como titulares temporales para los operandos izquierdo y derecho de una expresión infija: x + o, x - o, etc. (o orden de x, o invertido).

También hay un buen write up on wikipedia. Dejé mi respuesta como una wiki en caso de que haya estropeado el orden de las expresiones.

Answer 6

El algoritmo para pasar de infija a expresiones prefijo es:

-reverse input 

TOS = top of stack 
If next symbol is: 
- an operand -> output it 
- an operator -> 
     while TOS is an operator of higher priority -> pop and output TOS 
     push symbol 
- a closing parenthesis -> push it 
- an opening parenthesis -> pop and output TOS until TOS is matching 
     parenthesis, then pop and discard TOS. 

-reverse output 

Así que su ejemplo es algo como (x PUSH, o POP):

2*3/(2-1)+5*(4-1) 
)1-4(*5+)1-2(/3*2 

Next 
Symbol Stack   Output 
)  x) 
1  )    1 
-  x)-   1 
4  )-   14 
(  o)    14- 
     o    14- 
*  x *    14- 
5   *    14-5 
+  o    14-5* 
     x +    14-5* 
)  x +)   14-5* 
1   +)   14-5*1 
-  x +)-   14-5*1 
2   +)-   14-5*12 
(  o +)   14-5*12- 
     o +    14-5*12- 
/  x +/   14-5*12- 
3   +/   14-5*12-3 
*  x +/*   14-5*12-3 
2   +/*   14-5*12-32 
     o +/   14-5*12-32* 
     o +    14-5*12-32*/ 
     o    14-5*12-32*/+ 

+/*23-21*5-41 

Answer 7

después de todos estos ejemplos buena Adam Shankman todavía no puede darle sentido. Creo que deberías abrir un código y probarlo. En el momento en que pruebe un myStack.Push (1) y myStack.Pop (1) realmente debería obtener la imagen. Pero por lo que parece, ¡incluso eso será un desafío para ti!

Answer 8

• empuje = añadir a la pila
• pop = eliminar de la pila