Stack

Stack is a kind of data structure that insertions and deletions only performed at the top of its structure. It is LIFO by design which is in contrast with Queue. It could be implemented in list# or array#.

Stack can be used for:

balancing symbols
postfix expressions which could result in O(N)
infix to postfix conversion which could result in O(N)
function call

Attention

Push, the insertion on Stack, need to detect out of space as an implementation error
Pop, the deletion on Stack, and Top, to view most recently inserted element need to detect empty stack as an ADT error

Links to this page

Topological Sort

When optimised with 202112031157 or 202112101836, it results in \(O(\vert E \vert + \vert V \vert)\)
Rust Box

Box<T> is a kind of #202111301656 implemented by Rust standard library which is actually a single element Tuple with 202206221604# and Drop 202204061235#. It doesn’t have performance overhead. It stores data on the 202202062259# rather than on the 202112031157#. We can directly print the value (if it is of simple type) just like other primitive types without dereferencing it. Comparing to normal references, box is pointing to a copied value.
Queue

Queue is a kind of data structure that insertions done at one end, deletions done at the other end. It is FIFO by design which is in contrast with 202112031157. It could be implemented in array#.
Linked List Implementation of Stack

#Stack could be implemented using #Linked List.
Array Implementation of Stack

#202112031157 could be implemented using Array. However, the Array size need to be declared ahead of time before the creation of the Stack.

#data-structure #stack