Data Structures in Ruby: Stack
A stack is a simple data structure that follows the principle, “Last In, First Out.” Unlike many terms used in computer science, this one actually says what it is: A stack. Think of a stack of papers. If you piled the bills you received in the mail on a table one on top of the other as you received them each day, you would have a stack of bills. Let say you did this all month, and at the end of the month, you went to pay them all. You may simply begin at the top of the pile of the bills and continue to grab from the top for each bill you pay. In effect, you would be paying the last bill you received first. This is a stack: Last in, first out.
In computing, stacks are used when order is important and constant time is a concern. The Big O time complexity of the two main methods for the stack data structure is O(1) for insertion and removal. The history of your internet browser is an example of information stored as a Stack. Whenever you hit the back button, the last page you visited is the first page you see. The undo function of a text editor is another example of the use of a stack. In the following posts on data structures, we will need to use stacks and its cousin, queues for more involved data structures, and their traversal.
We are going to create a stack using a data structure we have already covered, the Singly Linked List. The two main methods for Stack are…
