Что такое Push и Pop для Stacks?

Question

Короче мой преподаватель это дерьмо, и показывал нам инфиксными с приставкой штабеля через диапроектор и его Bigass тень перекрывала все, так что я пропустил важный материал

он имел в виду толкать и поп, нажать = 0 поп = х

он привел пример, но я не могу видеть, как он получает ответ на все,

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

шаг 1 Реверс: )1-4(*5+)1-2(/3*2 хорошо я могу видеть, что

ч е затем продолжал писать иксы и операции O и я получил полностью потерял

ответ 14-5*12-32*/+ затем снова перевернуть, чтобы получить +/*23-21*5-41

если кто-нибудь может объяснить мне толчок поп, чтобы я мог понять, я была бы очень признательна, я смотрел онлайн, но много вещей, которые я нахожу, кажется, это шаг выше этого, поэтому мне нужно сначала понять это.

Answer 1

A Stack - структура данных LIFO (Last In First Out). Операции push и pop просто. Push ставит что-то в стек, поп убирает что-то. Вы ставите сверху и снимаете верх, чтобы сохранить заказ LIFO.

изменение - исправлено с FIFO, LIFO. Facepalm!

для иллюстрации, вы начинаете с пустой стек

|

затем вы нажимаете 'x'

| 'Х'

тогда нажать 'у'

| 'Х 'у'

тогда вы поп

| 'x'

Answer 2

Стек в принципе довольно проста: представьте себе клип винтовки. Вы можете получить доступ только к самой верхней пуле. Вывод из нее называется «поп», а вставка нового - «push».
Очень полезный пример для приложений, которые позволяют вам «отменить».
Представьте, что вы сохраняете каждое состояние приложения в стеке. например состояние приложения после каждого типа пользователя.
Теперь, когда пользователь нажимает «отменить», вы просто «выталкиваете» предыдущее состояние из стека. Для каждого действия, которое выполняет пользователь - вы «нажимаете» новое состояние в стек (это, конечно, упрощено).
О том, что конкретно сделал ваш лектор - чтобы объяснить это, вам будет полезна дополнительная информация.

Answer 3

Надеюсь, это поможет вам визуализировать стек и как оно работает.

Пустой Stack:

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

После нажатия A, вы получите:

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

После нажатия B, вы получите:

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

После поппинг, вы получите:

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

После нажатия C, вы получите:

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

После поппинг, вы получите:

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

После поппинг, вы получите:

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

Answer 4

Ok. Как пояснили другие ответчики, стек - это последняя структура данных. Вы добавляете элемент в верхнюю часть стека с помощью операции Push. Вы снимаете элемент сверху с помощью функции Pop. Элементы удаляются в порядке, обратном порядку, в который они были вставлены (следовательно, Last In, First Out). Например, если вы нажмете элюменты 1,2,3 в этом порядке, число 3 будет в верхней части стека. Поп-операция удалит его (он был последним) и оставьте 2 в верхней части стека.

Что касается остальной части лекции, лектор попытался описать машину на основе стека, которая оценивает арифметические выражения. Машина работает, непрерывно выталкивая 3 элемента из верхней части стека. Первые два элемента являются операндами, а третий - оператором (+, -, *, /). Затем он применяет этот оператор к операндам и выталкивает результат в стек. Процесс продолжается до тех пор, пока в стеке не будет только одного элемента, который является значением выражения.

Итак, предположим, что мы начнем с нажатия значений «+/* 23-21 * 5-41» в порядке слева направо в стек. Затем мы выталкиваем 3 элемента сверху. Последний из них первый, что означает, что первые 3 элемента: «1», «4» и «-» в этом порядке. Мы выталкиваем номер 3 (результат 4-1) в стек, затем выставляем три верхних элемента: 3, 5, *. Вставьте результат, 15, в стек и т. Д.

Answer 5

Аппликация зажима винтовки, размещенная Oren A довольно неплохая, но я попробую другую и постараюсь предвидеть то, что пытался испытать инструктор.

Стек, как это предполагает название является расположение «вещей», что имеет:

• Верхняя
• Дно
• Упорядочение между верхней и нижней (например, второй из сверху, 3-й снизу).

(думайте об этом как буквальной стопке книг на вашем столе, и вы можете взять только что-то из верхней части)

Раздвигая что-то в стеке означает «поместить его на вершине». Попадание чего-то из стека означает «взять верхнюю вещь» из стека.

Простое использование для изменения порядка слов. Скажем, я хочу обратить вспять слово: «попкорн». Я нажимаю каждую букву слева направо (все 7 букв), а затем выталкиваю 7 букв, и они попадают в обратном порядке. Похоже, это то, что он делал с этими выражениями.

толчка (р) толчка (о) толчка (р) толчка (с) толчка (о) толчка (г) толчка (п)

после нажатия всего слова, стек выглядит следующим образом:

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

, когда я поп() семь раз, я получаю письмо в таком порядке:

п, г, о, с, р, о, р

преобразование инфиксного/постфикс/префикса является патологическим примером в области информатики при обучении стеки:

Infix to Postfix conversion.

сообщения преобразования фикса для выражения инфиксного является довольно прямо вперед:

(выражение сканирования из слева направо)

1. Для каждого номера (операнда) нажмите его на стек.
2. Каждый раз, когда вы сталкиваетесь с оператором (+, -, /, *), дважды выходите из стека и помещаете оператор между ними. Нажмите, что в стеке:

Так что, если у нас есть 53 + 2 * мы можем преобразовать, что инфиксными в следующих шагах:

1. Push-5
2. Нажмите 3.
3. Столкнутые +: pop 3, pop 5, нажмите 5 + 3 на стеке (будет соответствовать порядку 5 и 3)
4. Push 2.
5. Encountered *: pop 2, pop (5 + 3), push (2 * (5 + 3)).

* Когда вы достигнете конца выражения, если оно было правильно сформировано, вы должны содержать только один элемент.

Вводя «x» и «o», он, возможно, использовал их в качестве временных держателей для левого и правого операндов выражения инфикса: x + o, x - o и т. Д. (Или порядок x, o в обратном порядке).

Есть также хороший write up on wikipedia. Я оставил свой ответ в виде вики-подделки, я исказил любые выражения выражений.

Answer 6

Алгоритм перехода от инфиксом к префиксов выражений:

-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 

Так что ваш пример идет что-то вроде (х PUSH, о 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

после всех этих хороших примеров Адам Шенкман все еще не может понять. Я думаю, вам нужно открыть какой-то код и попробовать. Во-вторых, вы пытаетесь использовать myStack.Push (1) и myStack.Pop (1), вам действительно нужно получить изображение. Но, по внешнему виду, даже это будет проблемой для вас!

Answer 8

• толчок = добавить в стек
• поп = удалить из стека