List-Based Stacks
If we implement a stack using a singly linked list, we can simplify many things about the implementation. First of all, we can totally remove the isFull
, doubleCapacity
, and halveCapacity
operations since we can grow and shrink our list-based stack as needed. The rest of the operations can be implemented directly with list operations. The front of the list will be the top of the stack since the operations to insert and remove items from the front of list are very efficient.
To implement our stack, we assume we have declared a linked list object named list
.
Push
As expected, the push
operation is almost trivial. We simply call the list prepend
operation to insert the data into the front of the list.
function push(data)
list.prepend(data)
end function
Pop
Like push
, the pop
operation is also easily implemented using the removeFirst
operation of our linked list. As long as the list is not empty, we simply return the data from the first item when we remove it from the list.
function pop() returns data
if list.isEmpty() then
throw exception
end if
return list.removeFirst().data
end function
isEmpty
The isEmpty
operation is even easier. It is implemented by simply returning the results of the list isEmpty
operation.
function isEmpty() return boolean
return list.isEmpty()
end function
Peek
The stack peek
operation is also straightforward. To implement the peek
operation we simply return the results from the list peek
operation, which returns the data
from the first node in the list.
function peek() returns data
return list.peek()
end function
As we can see, each of the major operations for a stack is implemented easily using list operations that run in constant time. This makes list-based stacks extremely efficient data structures to use.