Haskell Stacks : Two Different Ways

I am starting to attempt to understand how Haskell can persist functions sans the variables. You can do it with lists, already. There are plenty of functions that demonstrate the concept. But I want to expand further. I want to try implementing a stack with a list, and then do it with a recursive type. This is what I have for the first one:

putAtEnd [] item = [item]
putAtEnd (x:xs) item = x : putAtEnd xs item

push lst item = putAtEnd lst item
-- or
-- push lst item = reverse (item : (reverse lst))

pop lst = pop_ lst ((length lst) - 1)

pop_ _ 0 = []
pop_ (x:xs) len = x : pop_ xs (len - 1)

-- or
-- pop lst = reverse (tail (reverse lst))

I thought the reverse function was neat, but seemingly costly. But, from the Prelude:

reverse :: [a] -> [a]
reverse = foldl (flip (:)) []

flip f x y = f y x

foldl f z [] = z
foldl f z (x : xs) = foldl f (f z x) xs

We can see a really slick way of doing reverses. "reverse" is merely a function curry of a foldl waiting for the last parameter. Let's see if it is costly:

reverse [1,2,3,4]
 -> foldl (flip (:)) [] [1,2,3,4]
    -> foldl (flip (:)) (flip [] 1) [2,3,4]
    -> foldl (flip (:)) (1 : []) [2,3,4]
          -> foldl (flip (:)) (flip [1] 2) [3,4]
          -> foldl (flip (:)) (2 : [1]) [3,4]
                -> foldl (flip (:)) (flip [2,1] 3) [4]
                -> foldl (flip (:)) (3 : [2,1]) [4]
                      -> foldl (flip (:)) (flip 4 : [3,2,1]) []
                      -> foldl (flip (:)) [4,3,2,1] []
-> [4,3,2,1]

So, the ones with the same indentation are the same, except the second line is the flip function evaluated. It is what I expected, though. It takes O(n) (?) time (there are two operations on the data: one operation to flip, and another operation to add to the new list. So, maybe it is O(2n)? I forget my algorithm lessons.) It seems though, that the original implementation I provided performs the same though. Maybe expressing it via reverse then is easier.

Lists are, still probably still efficiently implemented, and those operations I am doing are turned into an iteration (tail-call recursion), plus some other magic I don't know about. I have to think of a nifty way of handling it faster though.

Anyway, the other idea I had was to make a stack a recursive data type:

data Stack n m = Item m | StackFrame ((Stack n) (Item m))

-- so ... 

(StackFrame (StackFrame (Item 1) (Item 2)) (Item 3))

-- looks like

-- 3
-----
-- 2
-----
-- 1
-----

What a wacky idea. I have to think about this one, and read some common examples on this.