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 #push and #pop. These operate the same way that #unshift and #shift work in a Singly Linked List. However, since it is conventional to name the method to add to a list #push, and to remove from a list #pop, we will follow this guideline.
To begin creating our Stack data structure in Ruby, we’ll begin similarly to the creation of the Singly Linked List. A Node class needs to be initialized with instance variables to store the data or value of the node, as well as the pointer to the next node.
attr_accessor :data, :nextdef initialize(data)
@data = data
@next = nil
For the Stack class, we will begin by initializing variables for the beginning of the list, commonly called the root, the last node in the list, and the size of the list.
attr_accessor :root, :last, :sizedef initialize
@root = nil
@last = nil
@size = 0
To begin populating the Stack, we will first code our #push method. Unlike an array or standard linked list, we will be pushing onto the front of the list, not the end. This is specifically to keep time complexity to constant time: O(1). If you recall, removing a node at the end of a Singly Linked List is O(n) since we have to traverse the entire list to get to the pointer of the node previous to the end. Here, we are setting up our data structure to always operate at the beginning of the linked list
The #push method begins by creating a new Node. Then, we check if the Stack is currently empty. If so, we just assign both the root and the last variables to be the newly created node. If there is at least one other node already in the Stack, we set the next pointer of the newly created node to be the old root, and reassign @root to be the newly created node. The return of the method can be a few different things, such as true or the node just entered. Here, we will return the size of the Stack. But this is up to you.
new_node = Node.new(data)
@root = new_node
@last = new_node
old_head = @root
@root = new_node
new_node.next = old_head
return @size += 1
To remove from a Stack, we use the #pop method. Here, the method returns the root, or the last element pushed onto the Stack and also reassigns the node that was after the root to be the new @root. If this was the last node in the Stack, we need to set @last to nil. Also, if the Stack was empty we also need to return nil.
return nil if @size==0
old_head = @root
@last = nil
@root = @root.next
@size -= 1
There are two other minor methods that are often a part of the Stack functionality: #is_empty? and #peek. The #is_empty? method returns a Boolean true/false and checks to see if there is a root present. We could have also done this by checking the size of the Stack. The #peek method returns what is on the top of the Stack without actually removing it.
At this point, you make be asking if we could have just done this using #pop and #push on a standard Ruby array and still keep Big O to O(1). Yes, of course. However, the Ruby array object comes loaded with many other functions that may be unnecessary for your purpose, and the flexibility of being able to populate the Node Class with any type of information that you want is good to have in case you need it.
Next week we will delve into the Queue Data Structure in Ruby.