List Based Stack Algorithm
The List-Based Stack Algorithm is a data structure that organizes and manages elements in a linear format, following the Last-In-First-Out (LIFO) principle. This means that the most recently added element is always the first one to be removed, and elements that were added earlier are removed later. The stack can be implemented using various data structures, but in the List-Based Stack Algorithm, it is built using a linked list or dynamic array, which allows for efficient insertion and deletion of elements at the top of the stack. The stack supports two primary operations: push (to add an element) and pop (to remove the top element), with the latter operation returning the value of the removed element. Additionally, the algorithm may include a method to check if the stack is empty, and another to return the value of the top element without removing it (peek).
In a List-Based Stack Algorithm, each element is stored in a node (in the case of a linked list) or a dynamically resizable array (in the case of a dynamic array). When an element is pushed onto the stack, a new node is created, and its value is set to the element being added. The new node's pointer (or in the case of an array, its index) is then set to the previous top node, and the top of the stack is updated to point to the new node. When an element is popped from the stack, the value of the top node is returned, the top pointer (or index) is updated to point to the next node, and the previous top node is deleted. In dynamic arrays, resizing occurs when the number of elements in the stack exceeds the current capacity, in which case a new, larger array is created, and elements are copied over from the old array. Similarly, when the number of elements drops below a certain threshold, the array is resized to a smaller capacity to conserve memory. The List-Based Stack Algorithm offers constant-time complexity for push and pop operations, making it an effective choice for various applications, such as parsing expressions, managing function calls, and undo-redo functionality in software programs.
using System.Collections.Generic;
namespace DataStructures.ListBasedStack
{
/// <summary>
/// Implementation of a list based stack. FIFO style.
/// </summary>
/// <typeparam name="T">Generic Type.</typeparam>
public class ListBasedStack<T>
{
/// <summary>
/// <see cref="List{T}"/> based stack.
/// </summary>
private readonly List<T> stack;
/// <summary>
/// Initializes a new instance of the <see cref="ListBasedStack{T}"/> class.
/// </summary>
public ListBasedStack() => stack = new List<T>();
/// <summary>
/// Initializes a new instance of the <see cref="ListBasedStack{T}"/> class.
/// </summary>
/// <param name="item">Item to push onto the <see cref="ListBasedStack{T}"/>.</param>
public ListBasedStack(T item)
: this() => Push(item);
/// <summary>
/// Initializes a new instance of the <see cref="ListBasedStack{T}"/> class.
/// </summary>
/// <param name="items">Items to push onto the <see cref="ListBasedStack{T}"/>.</param>
public ListBasedStack(IEnumerable<T> items)
: this()
{
foreach (var item in items)
{
Push(item);
}
}
/// <summary>
/// Gets the number of elements on the <see cref="ListBasedStack{T}"/>.
/// </summary>
public int Count => stack.Count;
/// <summary>
/// Removes all items from the <see cref="ListBasedStack{T}"/>.
/// </summary>
public void Clear() => stack.Clear();
/// <summary>
/// Determines whether an element is in the <see cref="ListBasedStack{T}"/>.
/// </summary>
/// <param name="item">The item to locate in the <see cref="ListBasedStack{T}"/>.</param>
/// <returns>True, if the item is in the stack.</returns>
public bool Contains(T item) => stack.Contains(item);
/// <summary>
/// Returns the item at the top of the <see cref="ListBasedStack{T}"/> without removing it.
/// </summary>
/// <returns>The item at the top of the <see cref="ListBasedStack{T}"/>.</returns>
public T Peek() => stack[^1];
/// <summary>
/// Removes and returns the item at the top of the <see cref="ListBasedStack{T}"/>.
/// </summary>
/// <returns>The item removed from the top of the <see cref="ListBasedStack{T}"/>.</returns>
public T Pop()
{
var item = stack[^1];
stack.RemoveAt(stack.Count - 1);
return item;
}
/// <summary>
/// Inserts an item at the top of the <see cref="ListBasedStack{T}"/>.
/// </summary>
/// <param name="item">The item to push onto the <see cref="ListBasedStack{T}"/>.</param>
public void Push(T item) => stack.Add(item);
}
}
