스택의 순차 표현

---

✅ Array

• 특징
  • 스택을 표현하는 가장 간당한 방법
  • n : 스택에 저장할 수 있는 최대 원소 수
  • top : 스택의 가장 위를 가리킴
  • top = -1 : 공백 스택임을 의미

✅ 알고리즘 표현

createStack()
make stack[n]
top = -1

isEmpty(stack)
if (top<0) return true;
else return false;

isFull(Stack)
if (top>n) return true;
else return false;

push(stack, item)
if isFull(stack) return error;
else top = top + 1;    //top 포인터를 먼저 올린 후
stack[top] = item      //item을 삽입해야함

pop(stack)
if isEmpty(stack) return error;
else item = stack[top];  //item을 우선 따로 저장한 후
top = top - 1;           //top 포인터를 내려야함
return item

delete(stack)
if isEmpty(stack) return error;
else top = top -1;

✅ C의 구현

#include <stdio.h>
#define STACK_SIZE 100 //스택의 최대크기

typedef struct element
{
    int id;
    char name[10];
    /* data */
} element;

typedef int element;
element stack[STACK_SIZE];
int top = -1;

int isEmpty(){
    if(top == -1) return 1;
    else return 0; 
}

int isFull(){
    if(top > STACK_SIZE) return 1;
    else return 0;
}

void push(int* top, element item){
    if(isFull()) {
        printf("Stack is full\n"); 
        return;
    }
    //top+1 후 item 삽입
    else {
        stack[++(*top)] = item;
    }
}

element pop(int* top){
    if(isEmpty()) {
        printf("Stack is empty\n"); 
        return;
    }
    else {
        return stack[(*top)--]; //item반환 후 top-1
    }

}

void delete(int* top){
    if(isEmpty()) {
        printf("Stack is empty\n"); 
        return ;
    }
    else {
        (*top)--; //item반환 후 top-1
    }
}

element peek(int top){
    if(isEmpty()) {
        printf("Stack is empty\n"); 
        return;
    }
    else {
        return stack[top];
    }
}

int main(void){
    int top = -1;
    element data1, data2;

    printf("push data1: %d\n", 1);
    push(&top, 1);

    printf("push data2: %d\n", 2);
    push(&top, 2);

    data2 = peek(top);
    printf("peek data2: %d\n", data2);

    delete(&top);
    printf("delete data2: %d\n", data2);

    data1 = pop(&top);
    printf("pop data1: %d\n", data1);
    
    return 0;

}

[자료 레퍼런스] (C언어) 배열을 이용해 스택(Stack) 구현하기

스택의 연결 표현

---

✅ Linked stack

• 장단점
  • 장점 : 크기가 제한되지 않음
  • 단점 : 구현이 복잡하고 삽입이나 삭제 시간이 오래 걸림
• 특징
  • top이 지시하는 연결리스트로 표현
  • top : 첫 번째 원소 가리킴
  • 삽입 : 생성된 노드를 연결 리스트의 첫 번째 노드로 삽입
  • 삭제 : 연결 리스트의 첫 번째 노드를 삭제하고 원소 값 반환

✅ 알고리즘 표현

//공백 연결스택 생성
createStack(){
	top = null;  
}
//연결스택의 공백검사
isEmpty(stack){
	if (top = null) return true
	else return false
}
//연결 스택 top에 item 삽입
push(stack, item){
	newNode = getNode()
	newNode.data = item
	newNode.link = top
	top = newNode
}
//연결스택에서 top 원소를 삭제하여 반환
pop(Stack){
	if (top = null) return null
	else{
		item = top.data
		oldNode = top
		top = top.link
		retNode(oldNode)
	}
	return item
}
//연결스택에서 top원소 삭제
remove(stack)
	if (top = null) return null
	else{
	oldNode = top
	top = top.link
	retNode(oldNode)
}
//스택의 top원소 검색
peek(stack){
	if (top = null) return null
	else return top.data
}

✅ C를 이용한 구현

#include <stdio.h>
#include <stdlib.h>

//연결 리스트 노두 구조체 정의
typedef struct stackNode {
    char data;
    struct stackNode* link;
} stackNode;

//스택의 맨 위 노드 주소를 저장할 포인터 변수
stackNode* top = NULL;

int isEmpty(){
    if(top == NULL){
        printf("Stack is Empty\n");
        return 1;
    }
    return 0;
}

void push(char data){
    //새로운 노드 동적할당
    stackNode* newNode = (stackNode *)malloc(sizeof(stackNode));
    newNode->data = data;
    newNode->link = top;
    top = newNode;
}

char pop(){
    if(!isEmpty()) {
        stackNode* temp = top;
        char data = top->data;
        top = top->link;
        free(temp);
        return data;
    }
    return 0;
}

char peek(){
    if(!isEmpty()){
        return top->data;
    }
    return 0;
}

void printStack(){
    if(!isEmpty()){
        //각 노드를 순환하는 포인터
        stackNode* temp = top;
        //현재 노드가 비어있지 않은 경우 반복
        while(temp){
            printf("%c", temp->data);
            temp = temp->link;
        }
        printf("\n");
    }
}

int main() {
    printStack();
    push('A');
    push('B');
    push('C');
    printStack();
    pop();
    printStack();
    push('D');
    printStack();
    pop();
    pop();
    printStack();
    return 0;
}

[참고 레퍼런스] (C언어) 연결 리스트를 이용해 스택(Stack) 구현하기