Push和Pop对Stacks意味着什么？

Question

长话短说我的讲师很废话,并且通过高架投影仪向我们展示了中缀,并且他的巨大阴影阻挡了一切,所以我错过了重要的东西

他指的是push和pop,push = 0 pop = x

他举了一个例子,但我看不出他是如何得到答案的,

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

第1步反向: )1-4(*5+)1-2(/3*2好的,我可以看到

然后他继续编写x和o的操作,我完全迷失了

回答14-5*12-32*/+然后再次逆转得到+/*23-21*5-41

如果有人可以向我解释推送流行音,那么我可以理解我会非常感激,我已经在网上看了很多东西我发现似乎比这更好了,所以我真的需要先了解一下这里

Answer 1

希望这可以帮助您可视化堆栈及其工作原理.

空堆栈:

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

推送后A,你得到:

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

推送后B,你得到:

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

弹出后,你得到:

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

推送后C,你得到:

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

弹出后,你得到:

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

弹出后,你得到:

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

Answer 2

Oren A发布的步枪剪辑类比非常好,但我会尝试另一个,并试着预测教练试图通过什么.

一个堆栈,顾名思义就是"事物"的安排,它具有:

• 在顶上
• 一个底部
• 顶部和底部之间的排序(例如,从顶部开始,第三个从底部开始).

(把它想象成你书桌上的书架,你只能从顶部拿东西)

在堆栈上推送东西意味着"将其放在顶部".从堆栈中弹出一些东西意味着"从堆栈中取出顶级'东西'".

一个简单的用法是颠倒单词的顺序.说我想扭转这个词:"爆米花".我将每个字母从左向右推(所有7个字母),然后弹出7个字母,它们将以相反的顺序结束.看起来这就是他用这些表达做的事情.

推(p)推(o)推(p)推(c)推(o)推(r)推(n)

在推完整个单词后,堆栈看起来像:

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

当我pop()七次时,我按顺序得到这些字母:

N,R,O,C,P,O,P

在学习堆栈时,中缀/后缀/前缀的转换是计算机科学中的病态示例:

中缀到Postfix转换.

将修复后转换为中缀表达式非常简单:

(从左到右扫描表达式)

1. 对于每个数字(操作数),将其推入堆栈.
2. 每次遇到一个操作符(+, - ,/,*)从堆栈弹出两次并将操作符放在它们之间.把它推到堆栈上:

因此,如果我们有53 + 2*,我们可以通过以下步骤将其转换为中缀:

1. 推5.
2. 推3.
3. 遇到+:弹出3,弹出5,在堆栈上按5 + 3(与5和3的顺序一致)
4. 推2.
5. 遇到*:pop 2,pop(5 + 3),push(2*(5 + 3)).

*到达表达式的末尾时,如果形式正确,则堆栈应该只包含一个项目.

通过引入'x'和'o',他可能一直使用它们作为中缀表达式的左右操作数的临时持有者:x + o,x-o等(或x的顺序,反转).

维基百科也有很好的写作.我把答案留给了wiki,因为我搞砸了任何表达式的排序.

Answer 3

从中缀到前缀表达式的算法是:

-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

所以你的例子就像(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 4

堆栈是一种 LIFO（后进先出）数据结构。推入和弹出操作很简单。Push 将一些东西放入堆栈，pop 则取出一些东西。您将顶部放入，然后取下顶部，以保留 LIFO 顺序。

编辑--从先进先出 (FIFO) 更正为后进先出 (LIFO)。捂脸！

为了说明这一点，你从一个空白堆栈开始

|

然后你按“x”

| 'X'

然后你按“y”

| 'x' 'y'

然后你弹出

| 'X'