Stacks

Stacks are containers of objects based on arrays that follow a Last-In-First-Out (LIFO) order, meaning that the most recently added item is removed first. Stacks are often used with the recursive backtracking algorithm and as the mechanism supporting the “undo” or “back” button in applications and browsers. Compilers often use stacks to parse the syntax of expressions before translating them into low-level code.

With stacks, we only remove the most recently added item. A popular example is a stack of lunch trays in a cafeteria.

Implementation of stacks

Stacks can be implemented using various data structures, including:

• Arrays: As defined earlier, arrays are sequential collections of elements stored in contiguous memory locations. Arrays are easy to implement and offer fast access to the elements, but they have a fixed size and cannot be altered once they are created.
• Linked lists: Linked lists are collections of elements linked together using pointers. Linked lists are more flexible than arrays because they can grow and shrink when required, but the downside is that they are more complex to implement and require extra memory to store pointers.
• Dynamic arrays: These are arrays that can automatically resize themselves when required. Dynamic arrays combine the simplicity of arrays with the flexibility of linked lists, but are generally slower than other data structures due to having to copy elements when an array is resized.
• Vector: A vector is a dynamic array with an added ability to shrink. It allows for efficient insertion and deletion of elements at the end of the stack, but may be slower for inserting or deleting at the beginning or middle of the stack.
• Deque (Double-ended queue): A deque is a dynamic array that allows for efficient insertion and deletion of elements at both the beginning and end of the stack. It offers the fastest insertion and deletion among the stack implementations, but may be slower for accessing the middle elements and therefore should be used sparingly.
  
  스택(Stack)은 배열을 기반으로 한 객체 컨테이너로, 가장 최근에 추가된 항목이 먼저 제거되는 Last-In-First-Out (LIFO) 순서를 따릅니다. 스택은 주로 재귀적 백트래킹 알고리즘과 같은 곳에서 사용되며, 응용 프로그램과 브라우저에서 "실행 취소" 또는 "뒤로 가기" 버튼을 지원하는 메커니즘으로도 활용됩니다. 컴파일러는 종종 식의 구문을 해석하기 위해 스택을 사용하고, 이후 이를 저수준 코드로 변환하기 전에 사용합니다.스택의 구현 스택은 다양한 데이터 구조를 사용하여 구현할 수 있으며, 이에는 다음과 같은 것들이 포함됩니다:
  • 배열(Array): 앞에서 정의한 대로 배열은 연속적인 메모리 위치에 저장된 요소의 순차적인 모음입니다. 배열은 구현하기 쉽고 요소에 빠르게 액세스할 수 있지만 크기가 고정되며 한 번 생성되면 변경할 수 없습니다.
  • 연결 리스트(Linked List): 연결 리스트는 포인터를 사용하여 연결된 요소의 모음입니다. 연결 리스트는 필요할 때 성장하고 축소할 수 있는 배열보다 유연하지만, 구현이 복잡하고 포인터를 저장하기 위한 추가 메모리가 필요합니다.
  • 동적 배열(Dynamic Array): 이것은 필요할 때 자동으로 크기를 조절할 수 있는 배열입니다. 동적 배열은 배열의 간결성과 연결 리스트의 유연성을 결합하지만, 배열 크기를 조절할 때 요소를 복사해야 하므로 일반적으로 다른 데이터 구조보다 느릴 수 있습니다.
  • 벡터(Vector): 벡터는 크기를 줄일 수 있는 동적 배열입니다. 스택 끝에서 요소를 효율적으로 삽입하고 삭제할 수 있으며, 스택의 시작 또는 중간에 삽입 또는 삭제할 때는 더 느릴 수 있습니다.
  • 데크(Double-ended Queue): 데크는 스택의 시작과 끝에서 효율적으로 요소를 삽입하고 삭제할 수 있는 동적 배열입니다. 스택 구현 중에서 가장 빠른 삽입 및 삭제를 제공하지만, 중간 요소에 액세스할 때는 느릴 수 있으므로 삼가야 합니다.
• 스택을 사용할 때, 가장 최근에 추가된 항목만 제거합니다. 대표적인 예로는 식당에서 사용되는 점심용 쟁반 스택이 있습니다.

Implement Stack using Array

#include <iostream>
using namespace std;
#define SIZE 10
class Stack
{
    int* arr;
    int top;
    int capacity;
    
public:
    Stack(int size = SIZE);
    ~Stack();
    void push(int);
    int pop();
    int peek();
    int size();
    bool isEmpty();
    bool isFull();

};
Stack::Stack(int size)
{
    arr = new int[size];
    capacity = size;
    top = -1;
}
Stack::~Stack()
{
    delete[] arr;
}
void Stack::push(int x)
{
    if (isFull()) {
        exit(EXIT_FAILURE);
    }
    arr[++top] = x;
}
int Stack::pop() 
{
    if (isEmpty()) {
        exit(EXIT_FAILURE);
    }
    return arr[top--];
}
int Stack::peek()
{
    if (!isEmpty()) {
        return arr[top];
    }
    else {
        exit(EXIT_FAILURE);
    }
}
int Stack::size()
{
    return top + 1;
}
bool Stack::isEmpty()
{
    return top == -1;
}
bool Stack::isFull()
{
    return top == capacity - 1;
}