후입선출(LIFO : Last-In First-Out)
가장 최근에 들어온 데이터가 가장 먼저 나가는 것.
각티슈에서 가장 위에 있는 것부터 뽑아 쓰는 것처럼!
입력과 출력이 역순으로 필요한 경우 사용한다. (ex. undo, 함수 호출 스택)
연산
init(stack) : 스택을 초기화한다.
create() : 스택을 생성한다.
push(stack, data) : 데이터를 스택 가장 위에 삽입한다.
pop(stack) : 스택 가장 위의 데이터를 삭제한다.
is_empty(stack) : 스택이 비어있는지 검사한다.
is_full(stack) : 스택이 가득 찼는지 검사한다.
peek(stack) : 스택의 맨 위에 있는 요소를 삭제하지 않고 반환한다.
배열을 이용한 스택
#include <iostream>
#define MAX_STACK_SIZE 3
typedef int element;
typedef struct{
element stack[MAX_STACK_SIZE];
int top;
}Stack;
void init(Stack *stack){
stack->top = -1;
}
bool is_empty(Stack *stack){
return stack->top == -1;
}
bool is_full(Stack *stack){
return stack->top == MAX_STACK_SIZE-1;
}
void push(Stack *stack, element data){
if(is_full(stack)){
std::cerr << "Stack is Full\n";
exit(-1);
}
stack->stack[++stack->top] = data;
}
element pop(Stack *stack){
if(is_empty(stack)){
std::cerr << "Stack is Empty\n";
exit(-1);
}
return stack->stack[stack->top--];
}
element peek(Stack *stack){
if(is_empty(stack)){
std::cerr << "Stack is Empty\n";
exit(-1);
}
return stack->stack[stack->top];
}
int main(){
Stack stack;
init(&stack);
push(&stack, 1);
push(&stack, 2);
push(&stack, 3);
std::cout << is_full(&stack) << "\n"; // 1
std::cout << pop(&stack) << "\n"; // 3
std::cout << pop(&stack) << "\n"; // 2
std::cout << peek(&stack) << "\n"; // 1
std::cout << pop(&stack) << "\n"; // 1
std::cout << is_empty(&stack) << "\n"; // 1
}
연결리스트를 이용한 스택
#include <iostream>
typedef int element;
typedef struct StackNode{
element data;
StackNode * link;
}StackNode;
typedef struct linkedStack{
StackNode * top;
}linkedStack;
void init(linkedStack *stack){
stack->top = nullptr;
}
bool is_empty(linkedStack *stack){
return stack->top == nullptr;
}
void push(linkedStack *stack, element data){
StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
if(temp == nullptr){
std::cerr << "Memory Allocation Error\n";
return;
}
temp->data = data;
temp->link = stack->top;
stack->top = temp;
}
element pop(linkedStack *stack){
if(is_empty(stack)){
std::cerr << "Stack is Empty\n";
exit(-1);
}
StackNode *temp = stack->top;
stack->top = stack->top->link;
element data = temp->data;
free(temp);
return data;
}
element peek(linkedStack *stack){
if(is_empty(stack)){
std::cerr << "Stack is Empty\n";
exit(-1);
}
return stack->top->data;
}
int main(){
linkedStack stack;
init(&stack);
push(&stack, 1);
push(&stack, 2);
push(&stack, 3);
std::cout << pop(&stack) << "\n"; // 3
std::cout << pop(&stack) << "\n"; // 2
std::cout << peek(&stack) << "\n"; // 1
std::cout << pop(&stack) << "\n"; // 1
std::cout << is_empty(&stack) << "\n"; // 1
}
'공부 > 자료구조' 카테고리의 다른 글
[자료구조] 우선 순위 큐(Priority Queue) (0) | 2023.05.12 |
---|---|
[자료구조] 이진트리(Binary Tree) (0) | 2023.05.11 |
[자료구조] 덱(Deque) (0) | 2023.04.30 |
[자료구조] 큐(Queue) (0) | 2023.04.30 |