Edit on GitHub

Stack

The Stack data structure corresponds to a Last In, First Out (LIFO) queue in which elements are added to and removed from only one of the ends of the queue. In DataStructures.jl the Stack type is a light-weight wrapper around the Deque type.

Notes on the Iterator interface implemented by the Stack

The Stack type implements the Julia Iterator interface; iterating over Stack returns items in First In, Last Out (FILO) order, i.e. "from top to bottom" of the stack. There is also a Iterators.reverse function which iterates over the items in First In, First Out (FIFO) order, or "from bottom to top" of the stack.

julia> s = Stack{Int64}()
Stack{Int64}(Deque [Int64[]])

julia> for i in 1:4
           push!(s, i)
       end

julia> for el in s # top to bottom iteration 
           println(el)
       end
4
3
2
1

julia> for el in Iterators.reverse(s) # bottom to top iteration 
           println(el)
       end
1
2
3
4

Constructors

DataStructures.Stack — Type
Stack{T}() where {T}
Stack{T}(blksize::Integer) where {T}

Create a Stack object containing elements of type T for Last In, First Out (LIFO) access.

Parameters

  • T::Type Stack element data type.
  • blksize::Integer Unrolled linked-list block size (in bytes) used in the underlying representation of the stack. Default = 1024.

Examples

julia> s_int = Stack{Int64}() # create a stack with Int64 elements
Stack{Int64}(Deque [Int64[]])

julia> s_float = Stack{Float64}() # create a stack with Float64 elements
Stack{Float64}(Deque [Float64[]])
source

Usage

The Stack type implements the following methods:

Base.:== — Method
==(x::Stack, y::Stack)

Check if stacks x and y are equal in terms of their contents and the order in which they are present in the stack. Internally calls ==() for each of the pairs formed by the elements of x and y in the order they appear in the stack.

Example

julia> s1, s2 = Stack{String}(), Stack{String}()
(Stack{String}(Deque [String[]]), Stack{String}(Deque [String[]]))

julia> for string in ["foo", "bar", "42"]
          push!(s1, string)
          push!(s2, string)
       end

julia> s1 == s2
true

julia> pop!(s1)
"42"

julia> s1 == s2
false
julia> a, b = Stack{Int}(), Stack{Int}()
(Stack{Int64}(Deque [Int64[]]), Stack{Int64}(Deque [Int64[]]))

julia> for num in [1, 2, 3, 4] push!(a, num) end

julia> for num in [1, 2, 4, 3] push!(b, num) end

julia> a == b # same elements but in different order
false
source
Base.eltype — Method
eltype(::Type{Stack{T}}) where {T}

Return the type of the elements in the stack.

source
Base.empty! — Method
empty!(s::Stack)

Make s empty by inplace-removing all its elements.

source
Base.first — Method
first(s::Stack)

Get the first element of s in Last In, First Out order. Since s is a stack, the first element will be the element at the top of s (also known as "peek" of the stack).

Example

julia> s = Stack{Float32}()
Stack{Float32}(Deque [Float32[]])

julia> for i in range(1, 0.2, 5)
           push!(s, i)
       end

julia> s
Stack{Float32}(Deque [Float32[1.0, 0.8, 0.6, 0.4, 0.2]])

julia> first(s)
0.2f0
source
Base.isempty — Method
isempty(s::Stack)

Returns true if stack s is empty - i.e. has no elements - or false otherwise.

source
Base.last — Method
last(s::Stack)

Get the last element of s in Last In, First Out. Since s is a stack, the last element will be the at bottom of the stack.

Example

julia> s = Stack{Float32}()
Stack{Float32}(Deque [Float32[]])

julia> for i in range(1, 0.2, 5)
           push!(s, i)
       end

julia> s
Stack{Float32}(Deque [Float32[1.0, 0.8, 0.6, 0.4, 0.2]])

julia> last(s)
1.0f0
source
Base.length — Method
length(s::Stack)

Return the number of elements in stack s.

source
Base.pop! — Method
pop!(s::Stack)

Remove and return the top element from stack s.

source
Base.push! — Method
push!(s::Stack, x)

Insert new element x in top of stack s.

source