In computer science, a stack is an abstract data type that serves as a collection) of elements, with two main principal operations:
- push, which adds an element to the collection, and
- pop, which removes the most recently added element that was not yet removed.
The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out). Additionally, a peek) operation may give access to the top without modifying the stack.[1]#cite_note-1)
peek operation 对应的是方法 top：返回最顶层的数据的值，但不移除它。Top or peek is considered as non-essential operation because it can be done with a “pop” followed by a “push” to return the same data to the stack. 为了防止执行”stack top” 和 “pop” 时发生 underflow condition，一般可以使用isempty方法测试当前stack是否为空栈。
Considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. This data structure makes it possible to implement a stack as a singly linked list and a pointer to the top element. A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack.
Simple representation of a stack runtime with push and pop operations.
A stack is needed to implement depth-first search.
A stack can be easily implemented either through an array or a linked list.
Here is the pseudocode of push operation in array:
procedure push(stk :stack, x :item):if stk.top = stk.maxsize:report overflow errorelse:stk.item[stk.top] ← xstk.top ← stk.top + 1
Another option for implementing stacks is to use a singly linked list. A stack is then a pointer to the “head” of the list. Pushing and popping items happens at the head of the list; overflow is not possible in this implementation (unless memory is exhausted).
References
若有收获，就点个赞吧
0 人点赞
