数据结构之栈

栈(stack),实现的是一种后进先出(Last-in,first-out)策略。类似餐馆中的装盘子的东西,我们从容器中拿出盘子的顺序正好和我们放入盘子的顺序相反,总是最上面的盘子先被拿出。
栈上的 INSERT 操作被称作压栈(PUSH)
可以用一个数组S[1..N]来实现一个最多容纳 n 个元素的栈。该数组有一个属性S.TOP,指向最新插入的元素。栈中包含的元素为S[1..S.TOP],其中S[1]是栈底元素,而S[S.TOP]是栈顶元素。

栈.jpg

上图所示:栈 S 的数组实现。只有出现在浅灰色格子里的才算是栈内元素。
(a)栈S有四个元素。栈顶元素为9。
(b)调用 PUSH 方法将17,3 压入栈中
(c)调用 POP 并返回最后压入的元素3后的栈S。
虽然元素3仍然在数组当中,但是他已经不在栈内了,此时栈顶的是元素17

当S.TOP=0时,表示栈是空的(也就是不包含任何元素)。如果对一个空栈执行 POP(弹出)操作,则称为下溢(underflow)。如果S.TOP超出了数组的的长度,则称为上溢(overflow)。
栈通常的几个操作伪代码实现:

STACK-EMPTY(S)
if S.TOP == 0
	return ture;
else return false;
PUSH(s,x)
S.TOP = S.TOP + 1
S[S.TOP] = x
POP(S)
if STACK-EMPTY(S)
	error "underflow"
else S.TOP = S.TOP - 1
	return S[S.TOP + 1]

注意:三种栈操作的执行时间复杂度都为 O(1)。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×