본문 바로가기
_스타디/알고리'듬'

03_stack&queue 스텍 큐

아너무어렵다 2021. 7. 16. 02:08
반응형

Stack

: 잘 알다시피 입구와 나가는곳이 같다. 문어같은거 생각하면 편함. 문어도 구멍이 하나여서 거기로 먹고 뱉음

First in Last Out 이다. 먼저집어넣으면 젤 아래 들어가서 꺼내기 위해선 나머지 다 빼야함.

스택은 FILO, a가 바텀이고 c가 탑이다.

스택을 구현하는 법 :

1. 배열로 구현하기

원래대로라면 하나 들어올때마다 하나씩 밀어야하나 그러기엔 복잡하니까 그냥 그 뒤에다 넣는걸로 가정하자.

아무튼 그러면 다 받는데 이걸로 받으면 문제점이 배열을 처음에 선언할때 크기를 지정해뒀어야해서 다 차버리면 방법이 없다는 점이다. STATIC이라서 어느 정도 이상 들어갈 수 없음.

#include <iostream>
using namespace std;


int main(){
	int arr[10] = {0,}; //size : 10
    int count = 0;
    int i = 0;
    while(1){
        int n = 0;
        if(count==9){
            cout<<"stack full"<<endl;
            break;
        }
        cin>>n; //new input
        arr[i] = n;
        count++;
        i++;
        for(int j = 0; j < count; j++){
            cout << "|" << arr[j] << "|";
        }
        cout <<endl << "botton :" << arr[0] <<"/" << "top : " <<n<<endl;
    }
}

 

2. 동적 배열로 구현하기.

1의 단점 보완을 위해 동적으로 배열을 만들어서 동적으로 써먹는것이다.

필요한만큼 만들어서 써먹으면 딱인데 단점은 끝날때 free 해줘야 한다는 것이다.

 

3.Linked List

포인터를 활용하는 것이다. 만약 블록 3개가 필요하면 한칸짜리 블록 3개들을 포인터로 앞뒤를 이어주는 방법이다.

다른 방법들보다 더 많은 자유를 준다. 이해도 쉽고.

#include <iostream>
#include <stdlib.h>
using namespace std;

//Node : stack에 들어갈 값
struct Node{ //node 구조체
    struct Node* next; //next
    int n;
};

void menu();
void printNodes(struct Node* p);

int main(){
    int flag = 1;
    int input;

    struct Node *head; //first
    struct Node *last; //last
    struct Node *node; //temp

    head = NULL;
    last = NULL;
    //초기화

    while(flag){
        int n=0;
        int count=0;
        cout<<endl;
        cin >> input;
        count++;
        if(input == -1){
            flag = 0;
        }else{
            node = (struct Node*)malloc(sizeof(struct Node));
            //node 구조체 동적 할당

            node-> n = input;
            node-> next =NULL;
            //node 구조체 값 설정

            if(head==NULL){//연결리스트가 비어있을경우
                head=node;//head에 생성된 node 저장
            }
            else{//아님말고.
                last->next=node;//마지막노드에next노드 저장
            }
            last=node;
            //연결리스트에 추가된 node 주소를 last에 저장
        }
    }
    printNodes(head);
    freeNodes(head);
}
void menu(){
    cout<<"enter number : / "<<endl<<"press -1 to exit";
}
	
void printNodes(struct Node* p){
	while(p!=NULL){
		cout<<"|"<<p->n<<"|";//노드 저장된 값 출력
		p=p->next;//다음 노드로 이동.
	}
}

void freeNodes(struct Node* p){
    struct Node *temp; //다음 노드 주소 임시 저장할 변수
    while(p!=NULL){//연결리스트 끝까지 반복
        temp = p;
        //temp에 임시 저장 후
        p=p->next;//다음노드로
        free(temp);//그사이 임시저장한거 날려버림
    }
}

4.라이브러리 활용

이미 있는걸 활용하는것이다. 

stack <자료형> 변수명 : 자료형을 가진 변수명 스택 생성.

push(집어넣을꺼) --> 추가

pop() --> top에 있는 원소 삭제

top() --> top에 있는 원소 반환

empty()--> stack이 비어있으면 true 아니면 false

size()--> size 반환

==============================================

Queue

이거는 앞과 뒤가 있다. 나오는곳과 들어가는곳이 정해져 있는 친구이다. 선입선출 방식이고

마트나 편의점에서 주로 쓰는 방식이다.(뒤에있는게 신선하다 보통(뒤에있는게 늦게들어온놈이다.)) +이걸 생각해서 주부들이 많이 들르는 지점은 섞어두기도 한다.

아 스택 왜 그림으로 해뒀지 안해뒀으면 이것도 안해도 될텐데

                                   <front>                                                                                <rear>

First in First Out 이다.

따라서 이걸 구현하기 위해서 Round Queue 라는걸 활용하기도 한다. 도넛마냥 빙글빙글 도는것이다.

단점으로는 중간에 늘리기가 어렵다는 점이다.

#include <iostream>
using namespace std;

int n;
int front=-1;
int back=0;
int* queue;
int count;

void inputQueue(int data);
void deleteQueue();
void printQueue();
bool isFull();
bool isEmpty();


int main() {
	cout << " enter Circle Queue size :";
	cin >> n;
    queue = new int[n];

	while (1) {
		int menu, data;
		cout << "1. insert 2. delete"<<endl;
        cin >> menu;

		switch (menu) {
            case 1:
                printf("삽입할 데이터 입력 : ");
                cin>>data;
                inputQueue(data);
                break;
            case 2:
                //input 추가
                deleteQueue();
                break;
            default:
                cout<<"wrong input, try again"<<endl;
                break;
		}
	}
}

void inputQueue(int data){
    int index = 0;
    if(isFull()){
        cout<<"queue full"<<endl;
    }else{ //queue is not full.
        if(back == n){
            index = back;
            queue[index] =data;
            back = 0;
        }
        else{
            back++;
        }
    }
}

void deleteQueue() {
    int index = front;
    if(isEmpty()){
        cout<<"queue is empty"<<endl;
    }else{
        cout << queue[index];
        if(front == n){
            front = 0;
        }
        else{
            front++;
        }
    }
}

void printQueue(){
    int temp = 0;
    temp = (front + 1) % (n+1);

    while(1){
        if(front == back){
            cout<<"queue empty"<<endl;
            break;
        }
		else if (temp > back){
			break;
		}
		printf("%d ", queue[temp++ % (n + 1)]);
    }
}

bool isFull(){
    if(front < back){
        return back-front == n;
    }
    else{
        return back+1 == front;
    }
}

bool isEmpty(){
    if(front==back){
        return true;
    }
    else{
        return false;
    }
}

이건 내가 짠 코드고

#include <iostream>
using namespace std;

typedef struct {
    int data;
} Node;

typedef struct _CircularQueue {
    Node* nodes;
    unsigned int capacity;
    unsigned int front;
    unsigned int rear;
} CircularQueue;

bool isEmpty(CircularQueue *q) {
    return (q->front) == (q->rear);
}

bool isFull(CircularQueue *q) {
    if(q->front < q->rear)
        return q->rear - q->front == q->capacity;
    else
        return q->rear+1 == q->front;
}

void dequeue(CircularQueue *q) {
    int pop = q->front;
    if(isEmpty(q)) {
        cout << "Queue is Empty.\n";
        return;
    }


    if(q->front == q->capacity) q->front = 0;
    else q->front++;

    cout << "The pop element is " << q->nodes[pop].data << "\n";
    return;
}

void enqueue(CircularQueue *q, int data) {
    int push = 0;

    if(isFull(q)) {
        cout << "Queue is Full.\n";
        return;
    }

    if(q->rear == q->capacity) {
        push = q->rear;
        q->rear = 0; // 1칸 키운것
    }
    else {
        push = q->rear++;
    }
    q->nodes[push].data = data;
    return;
}

void print(CircularQueue* q) {
    int index = q->front;
    cout << "Queue elements\n";

    while(index != q->rear) {
        // index는 내가 출력할 원소의 인덱스.
        if(index == q->capacity+1) {
            index = 0;
        }
        cout << q->nodes[index].data << " ";
        index++;
    }
    cout << "\n";
    return;
}

void freeQueue(CircularQueue* q) {
    delete q->nodes;
    delete q;
}

int main() {
    int menu, data;

    CircularQueue *q;
    unsigned int size;

    cout << "Enter the queue size : ";
    cin >> size;

    q = new CircularQueue[1];
    q->nodes = new Node[size+1];
    q->capacity = size;
    q->front = 0;
    q->rear = 0;

    bool flag = true;
    while(flag) {
        cout << "1. Push\n2. Pop\n3. Print\n4. Exit\n=================\nEnter the number : ";
        cin >> menu;
        switch(menu) {
            case 1:
                cout << "Enter the element number : ";
                cin >> data;
                enqueue(q, data);
                break;
            case 2:
                dequeue(q);
                break;
            case 3:
                print(q);
                break;
            case 4:
                flag = false;
                break;
            default:
                cout << "Error. Enter the element number : ";
        }
    }
    freeQueue(q);

    return 0;
}

이건 이 블로그 최다 방문자님께서 짜신 코드다.

동적으로 배열 크기를 입력받고

원형 큐가 돌아가면서 처리해준다.

 

2. 이걸 위에서 했던것처럼 linked list로 구현하기도 한다.

 

3. Deque 라는게 있다. Double Ended Queue 인데. 시작과 끝이 두개씩 있는것이다.

둘중 가까운곳에 접근해서 써먹는 것 같다.

 

 

 

반응형
저작자표시 비영리 변경금지

'_스타디 > 알고리'듬'' 카테고리의 다른 글

03-divide and conquer -Quick sort  (0) 2021.07.08
02-Divide_and_Conquer_분할정복  (0) 2021.07.06
01-SORT-bubble, counting, selection, radix 버블 카운팅 셀렉션 라딕스 거품정렬 계수정렬 선택정렬 기수정렬 c++ c  (0) 2021.07.05

'_스타디/알고리'듬'' 관련글

티스토리툴바