알고리즘 study -17-

스택, 큐

-> 선형 자료구조

<스택(Stack)>

• LIFO - Last in First Out
  가장 최근에 삽입(push)한 원소가 먼저 나온다(pop)

• 정해진 크기가 있다

Stack overflow : 더 이상 들어가지 못하는 상황에서 넣으려 할때 발생

Stack underflow : 빈 상태에서 더 빼려 할때 발생

#include <stdio.h>


struct Stack{
  
  int data[100];
  int len = 0; // 현재 스택 원소 개수
  int capacity = 0; // 스택 용량
  
  void create(int y){
    capacity = y;
  }
  
  void push(int y){
    if(len >= capacity){
      printf("Starck overflow!\n");
    }
    else{
      data[len++] = y; // y를 len에 넣고 그 다음 len++
    }
    
  }
  void pop(){
    // 맨 위 원소가 빠진다
    
    if(len <= 0){
      printf("Stack underflow!\n");
    }
    else{
      data[len-1] = 0;
      len--;
    }
  }
  
  int top(){
    // 스택의 가장 위에 있는 원소를 반환
    // 스택에 아무것도 없다면 -1 출력
    if(len <= 0)
      return -1;
    else
      return data[len-1];
  }
  
  int size(){
    // 스택 안에 들어있는 원소 개수 반환
    return len;
  }
};


int main() {

  Stack s1;
  
  s1.create(5); // 크기 5 스택 생성
  
  s1.push(1);
  s1.push(2);
  s1.push(3);
  s1.push(4);
  s1.push(5);
  s1.push(6); // overflow
  
  printf("%d\n", s1.top()); // 5
  
  s1.pop();
  
  printf("%d\n", s1.top()); // 4
  
  s1.push(6);
  s1.push(7); // overflow
  
   printf("%d\n", s1.top()); // 6
   
   s1.pop();
   s1.pop();
   s1.pop();
   s1.pop();
   s1.pop();
   
   s1.pop(); // underflow
   
   printf("%d\n", s1.size());

  return 0;
}

결과 ->

Starck overflow!
5
4
Starck overflow!
6
Stack underflow!
0

<스택 라이브러리 사용 (in C)>

https://travelbeeee.tistory.com/69

참고 링크

<큐(Queue)>

• FIFO(First in First out)
• 먼저 삽입한 원소가 먼저 나온다
• 큐에도 크기 존재 -> queue overflow & queue underflow 존재

<큐 구현>

#include <stdio.h>

struct Queue{  // Queue 원소들은 모두 자연수라고 가정
  
  // data  1 2 3 4
  //       f       r
  
  int data[100];
  int front, rear;  // rear - front = 현재 원소의 개수!!!
  int capacity;
  
  void create(int y){
    capacity = y;
    front = 0;
    rear = 0;
  }
  
  void push(int x){
    if(rear-front >= capacity)
      printf("queue overflow\n");
    else
      data[rear++] = x; // rear도 하나 증가
  }
  
  void pop(){
    if(rear-front <= 0)
      printf("queue underflow\n");
    else{
      data[front] = 0;
      front++; // front 증가
    }
  }
  
  int returnFrontValue(){
    // 큐의 맨 앞 원소 반환
    // 없다면 -1 반환
    if(rear-front <= 0)
      return -1;
    else
      return data[front];
  }
  
  int returnQueueSize(){ // 큐 원소 개수 반환
    
    return rear-front;
  }
};

int main() {
  
  Queue q1;
  
  q1.create(3);
  
  q1.push(1);
  q1.push(2);
  q1.push(3);
  q1.push(4); // overflow
  q1.push(5); // overflow
  
  printf("%d\n", q1.returnFrontValue()); // 1
  printf("%d\n", q1.returnQueueSize()); // 3
  
  q1.pop();
  q1.pop();
  
  printf("%d\n", q1.returnFrontValue()); // 3
  printf("%d\n", q1.returnQueueSize()); // 1
  
  q1.pop();
  q1.pop(); // underflow
  
  printf("%d\n", q1.returnQueueSize()); // 0
  
  

  return 0;
}

<큐 구현의 문제점>

위에서 구현한 큐의 경우 front와 rear이 증가만 하므로 앞의 배열에 비는 공간이 생겨도 추가할 수가 없는 문제가 발생한다!

-->> 원형큐를 사용하자

<원형큐>

-> 앞 뒤가 없다 -->> 공간 활용 능력 우수

!!! 원형큐에서는 front와 rear의 차이로 현재 원소의 개수를 구할 수 없으므로 별도로 원소의 개수를 저장하는 변수를 선언하자 !!!

<원형큐 구현>

#include <stdio.h>

const int MAX = 10; // 배열 범위
// const = 상수 : 변경시킬 수 없다


struct Queue{  // Queue 원소들은 모두 자연수라고 가정
  
  // data  1 2 3 4
  //       f       r
  
  int data[MAX];  // const 정의해서 사용하는 습관!
  
  int front, rear;  // rear - front = 현재 원소의 개수!!!
  int capacity;
  int numElement; // 원소 개수 기억
  
  void create(int y){
    capacity = y;
    front = 0;
    rear = 0;
    numElement = 0;
  }
  
  void push(int x){
    if(numElement >= capacity)
      printf("queue overflow\n");
    else{
      
      /* data[rear++] = x;
      
      if(rear >= MAX){  // 배열 범위 벗어날 시
        rear = 0;
      }
      */
      
      data[rear] = x;
      rear = (rear+1) % MAX;   // 같은 표현
      
      numElement++;
    }
      
  }
  
  void pop(){
    if(numElement <= 0)
      printf("queue underflow\n");
    else{
      data[front] = 0;
      front++; // front 증가
      
      if(front >= MAX){ // 배열 범위 벗어날 시
        front = 0;
      }
      
      numElement--;
    }
  }
  
  int returnFrontValue(){
    // 큐의 맨 앞 원소 반환
    // 없다면 -1 반환
    if(numElement <= 0)
      return -1;
    else
      return data[front];
  }
  
  int returnQueueSize(){ // 큐 원소 개수 반환
    
    return numElement;
  }
};

int main() {
  
  Queue q1;
  
  q1.create(4);
  
  for(int i = 0; i<100; i++){
    q1.push(i);
    q1.push(i+1);
    q1.push(i+2);
    q1.push(i+3);
    
    q1.pop();
    q1.pop();
    q1.pop();
    q1.pop();
  }
  
  q1.push(1);
  q1.push(2);
  
  printf("%d\n", q1.returnFrontValue());
  
  q1.pop();
  
   printf("%d\n", q1.returnFrontValue());
  

  return 0;
}