Data Structures: Stack

I. Conceptual

What is the Stack?

stack The stack is also a linear data structure and it contains an ordered data set.

Stacks provide three methods for interaction:

push: adds data to the “top” of the stack.
pop: get the top element off the stack.
peek: returns data from the “top” of the stack without removing it.
Unlike queue, stack uses Last In First Out(LIFO) or First In Last Out(FILO) structure.

You can think of a stack of books as a way to organize a booklet in your home: stack

Each book has information (data). The first book you add (push) to the cabinet is both the top and bottom of the stack. Each added book becomes the new top of the stack.

Every time you want to read a book you can only take out the top one (pop) because if you take it from below the stack will spilled.

You can look through and read the title of the top book without taking it off the stack(peek).

II. Ideas

We can implement stack using linked list or array:

Below we will implement a stack using single-link list:

Stacks can be implemented using a linked list as the underlying data structure because it’s more efficient than a list or array.

The top of the stack is equivalent to the top node of the linked list, and the bottom of the stack is equivalent to the tail node.

One limitation that can be placed on a stack is its size. This is done to limit and quantify the resources the data structure will use when it is “full”.

Pushing data onto a full stack will result in a stack overflow. Similarly, if you try to pop data from an empty stack, it will result in a flow under the stack.

More detail:

First, create a Class to create the nodes of a linked list. Inside it, initialize a constructor that takes a node (value) as a parameter
Next, create a Stack class Inside it: Create a constructor that takes size as a parameter, set head and tail with nil => empty stack

We will do Push , Pop, Peek and Display operations: 1. Push: Insert a new element at the top of the stack, i.e. insert a new element at the beginning of the linked list.

Pop: Get the top element of the Stack, i.e. just remove the first element from the linked list.
Peek: provide the data of the first element of the stack.
Display: Print all elements in Stack.

III. Implementation

Implement stack using linked list:

- First, we create a class to initialize the linked list:

class Node
  attr_accessor :data 

  def initialize(data)
    @data = data
    @next_node = nil
  end
end

##  Now we will create a Stack class and perform main operations (methods) for it:

class Stack
  attr_accessor :data, :next_node

  def initialize
    @head_node = nil  
  end
  
#Method push adds a data to the start of the stack:
  def push(data)
    if @head_node == nil
      @head_node = Node.new(data)
    else
      new_node = Node.new(data)
      new_node.next_node = @head_node
      @head_node = new_node
    end
  end

#Method pop remove element that is the current head (start of the stack):
  def pop
    if @head_node == nil
      puts "The stack is empty"

#Remove the head node and make the node before it the new head node:
    else
      pop_node = @head_node
      @head_node = @head_node.next_node
      pop_node.next_node = @head_node
      return pop_node
    end
  end

#The peek method returns the head node data:
  def peep
    if @head_node == nil
      puts "No top button to show"
    else
      @head_node.data
    end
  end

#To output the contents of the linked list, we will create a method that uses to traverse the linked list as follows:
  def print
    print_list = ""
    current = @head_node
    if current == nil
      puts "Stack is empty"
    else
      while current != nil
        print_list += "#{current.data} -->"
        current = current.next_node
      end

      return print_list
    end
  end
end

##Driver code

Implement stack using array:

- Since ruby has built-in methods for arrays, we can implement stacks more easily:

We need to create 1 size to check if the array is full or not

class Stack
  class OverflowException < StandardError; end
  class UnderflowException < StandardError; end
  attr_accessor :size 

  def initialize(size: 6, value: 0)
    @size = size
    @arr = [value]
  end

  def push(value)
    raise OverflowException.new("The queue is full") if @size <= @arr.length

    @arr.unshift(value)
  end

  def pop
     raise UnderflowException.new("the queue is empty") if @arr.length == 0 

    @arr.shift
  end

  def peek
    puts @arr.first
  end

  def print
    puts "#{@arr}"
  end
end

# Let's try it:
stack = Stack.new(size: 5, value: 1)
puts "size stack: #{stack.size}"
puts "------------ expectation: [1]"
stack.print
stack.push(2)
stack.push(3)

puts "------------ expectation: [1,2,3]"
stack.print

puts "Peek: expectation: 3"
stack.peek

puts "------------ expect: [1,2,3]"
stack.print

puts "pop time #1: #{stack.pop}"
puts "pop time #2: #{stack.pop}"
puts "pop time #3: #{stack.pop}"
puts "------------ expectation: []"

#UnderflowException
#puts "pop time #4: #{stack.pop}"

stack.push(4)
stack.push(5)
stack.push(6)
stack.push(7)
stack.push(8)
stack.print
puts "------------"

#OverflowException
#stack.push(9)
stack.peek

# Output:
size stack: 5
------------ expectation: [1]
[1]
------------ expectation: [3, 2, 1]
[3, 2, 1]
Peek: expectation: 3
3
------------ expect: [3, 2, 1]
[3, 2, 1]
pop time #1: 3
pop time #2: 2
pop time #3: 1
------------ expectation: []
[8, 7, 6, 5, 4]
------------
8

IV. Recap

Stacks process data Last In, First Out (LIFO)
Stack is a data structure which contains an ordered set of data.
Stack provide three methods for interaction:

push: adds data to the “top” of the stack pop: get the first element out of the stack peek: provide the data of the first element of the stack without deleting it
Can be implemented using a linked list or array
There may be a size limit
Pushing into a full queue causes a stack overflow
Taking an element from an empty stack causes underflow.

Thanks for reading my post. See you in the next lesson!

thank

Data Structures: Queues

React