Stack

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(n)	O(n)	O(1)	O(1)

Definition

Short

Stack is a data structure that stores items in a Last-In-First-Out (LIFO) manner, meaning the most recently added item is the first one to be removed.

Simplified

You have a stack of plates. You can only put a new plate on the top of the stack, and you can only take the plate that's on the top. You can't take the ones in the middle until you've take the ones on top of them.

Detailed

Stack is a concept that functions as a collection of elements. It primarily operates through 2 actions:

• push, which adds an element to the collection
• pop, which removes the most recent element that hasn't been removed yet

This structure is also known as LIFO (last in, first out) due to the order in which elements are removed. A peek operation can also be used to access the top element without altering the stack. The term "stack" is derived from the physical analogy of items stacked on top of each other, allowing easy removal from the top, while accessing deeper items may require removing several top items first.

Practice

Practice

Aspect	Pseudo Code
Peek	peek(): stack.show_last()
Push	push(): stack.add_to_end(data)
Pop	pop(): stack.pop_from_end()

Solution

package main

type Stack struct {
	elements []interface{}
}

func (s *Stack) Push(item interface{}) {
	s.elements = append(s.elements, item)
}

func (s *Stack) Pop() (interface{}, bool) {
	if len(s.elements) == 0 {
		return nil, false
	} else {
		index := len(s.elements) - 1
		element := s.elements[index]
		s.elements = s.elements[:index]
		return element, true
	}
}

func (s *Stack) Peek() (interface{}, bool) {
	if len(s.elements) == 0 {
		return nil, false
	} else {
		index := len(s.elements) - 1
		return s.elements[index], true
	}
}

import java.util.ArrayList;

public class Stack<T> {

  private ArrayList<T> elements = new ArrayList<>();

  public void push(T item) {
    elements.add(item);
  }

  public T pop() {
    if (!elements.isEmpty()) {
      return elements.remove(elements.size() - 1);
    }
    return null;
  }

  public T peek() {
    if (!elements.isEmpty()) {
      return elements.get(elements.size() - 1);
    }
    return null;
  }
}

class Stack {
  constructor() {
    this.elements = [];
  }

  push(item) {
    this.elements.push(item);
  }

  pop() {
    if (this.elements.length !== 0) {
      return this.elements.pop();
    }
    return null;
  }

  peek() {
    if (this.elements.length !== 0) {
      return this.elements[this.elements.length - 1];
    }
    return null;
  }
}

class Stack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun push(item: T) {
        elements.add(item)
    }

    fun pop(): T? {
        if (elements.isNotEmpty()) {
            return elements.removeAt(elements.size - 1)
        }
        return null
    }

    fun peek(): T? {
        return elements.lastOrNull()
    }
}

class Stack:
    def __init__(self):
        self.elements = []

    def push(self, item):
        self.elements.append(item)

    def pop(self):
        if len(self.elements) > 0:
            return self.elements.pop()
        return None

    def peek(self):
        if len(self.elements) > 0:
            return self.elements[-1]
        return None

struct Stack<T> {
    elements: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack {
            elements: Vec::new(),
        }
    }

    fn push(&mut self, item: T) {
        self.elements.push(item);
    }

    fn pop(&mut self) -> Option<T> {
        self.elements.pop()
    }

    fn peek(&self) -> Option<&T> {
        self.elements.last()
    }
}

class Stack<T> {
  private elements: T[] = [];

  push(item: T): void {
    this.elements.push(item);
  }

  pop(): T | null {
    if (this.elements.length > 0) {
      return this.elements.pop();
    }
    return null;
  }

  peek(): T | null {
    return this.elements[this.elements.length - 1] || null;
  }
}