[Bingrae] 9월 28일 Stack & Queue 김영준

1. Stack

• 스택이란?

자료의 입출력이 후입선출(LIFO:Last-In First-Out)의 형태로 일어나는 자료구조를 말한다.

• 후입선출(LIFO:Last-In First-Out)

나중에 들어온 데이터가 먼저 나간다!!!

• 스택의 구조 ( 요소,항목 / 스택 상단 - TOP / 삽입 연산 - PUSH / 삭제 연산 - POP )

• 스택의 연산

1. push(x) : 주어진 요소 x를 스택의 맨 위에 추가한다.

2. pop( ) : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환한다.

3. peek( ) : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환한다.

4. isEmpty( ) : 스택이 비어있으면 true 값을, 비어있지 않으면 false 값을 반환한다.

5. isFull( ) : 스택이 꽉 차있으면 true 값을, 꽉 차있지 않으면 false 값을 반환한다.

6. size( ) : 스택 내의 모든 요소들의 개수를 반환한다.

7. display( ) : 스택 내의 모든 요소들을 출력한다.

• 스택 활용의 예시

1. Undo 기능 ( 되돌리기 )

2. 함수 호출 : 하나의 함수가 끝나면 스택에서 가장 최근의 복귀 주소를 구해서 그 곳으로 돌아간다.

3. 괄호 닫기 확인 : 소스코드나 문서에서 괄호 닫기가 정상적으로 되었는지를 검사하는 프로그램에서 사용.

4. 미로에서 출구 찾기

• 스택의 구현(BaekJoon - 10828번) 

#include
#include 
using namespace std;
const int MAX_STACK_SIZE = 10000;

class ArrayStack {
private:
   int top;
   int data[MAX_STACK_SIZE];
public:
   ArrayStack() { top = -1; }
   ~ArrayStack() {}

   void Push(int a) {
      if (isFull() == false) data[++top] = a;
   }

   int Pop() {
      if (isEmpty()) return -1;
      else return data[top--];
   }

   int Size() {
      return top + 1;
   }

   int empty() {
      if (isEmpty()) return 1;
      else return 0;
   }

   int Top() {
      if (isEmpty()) return -1;
      else return data[top];
   }

   bool isEmpty() { return top == -1; }

   bool isFull() { return top == MAX_STACK_SIZE - 1; }

};

int main() {

   ArrayStack stack;

   char order[6];
   int n;
   int a;
   int check=0;

   cin >> n;

   int* Print = new int[n];

   if (n >= 1 && n <= 10000) {
      for (int i = 0; i < n; i++) {
         cin >> order;
         if (strcmp(order, "push") == 0) {
            cin >> a;
            stack.Push(a);
         }
         if (strcmp(order, "pop") == 0) {
            Print[check] = stack.Pop();
            check++;
         }
         if (strcmp(order, "top") == 0) {
            Print[check] = stack.Top();
            check++;
         }
         if (strcmp(order, "size") == 0) {
            Print[check] = stack.Size();
            check++;
         }
         if (strcmp(order, "empty") == 0) {
            Print[check] = stack.empty();
            check++;
         }
      }

      for (int i = 0; i < check; i++) cout << Print[i] << endl;
   }

   delete[] Print;

   return 0;
}

2. QUEUE

• 큐란?

자료의 입출력이 선입선출(FIFO:First-In First-Out)의 형태로 일어나는 자료구조

• 선입선출

먼저들어온 데이터가 나중에 들어오는 데이터에 의해 앞으로 밀리고 제일 앞쪽의 데이터(Front)가 나온다!

• 큐의 구조 ( 요소,항목 / 큐 전단 - FRONT / 큐 후단 - REAR / 삽입 연산 - ENQUEUE / 삭제 연산 - DEQUEUE)

• 큐의 연산

1. push(x) : 주어진 요소 x를 스택의 맨 위에 추가한다.

2. pop( ) : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환한다.

3. peek( ) : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환한다.

4. isEmpty( ) : 스택이 비어있으면 true 값을, 비어있지 않으면 false 값을 반환한다.

5. isFull( ) : 스택이 꽉 차있으면 true 값을, 꽉 차있지 않으면 false 값을 반환한다.

6. size( ) : 스택 내의 모든 요소들의 개수를 반환한다.

7. display( ) : 스택 내의 모든 요소들을 출력한다.