스택과 큐

스택과 큐 자료구조

• 리스트, 스택과 큐 : 스택과 큐는 리스트 자료구조의 특별한 경우이다
• 리스트
  • 순서가 있다.
  • 읽기, 삽입과 삭제를 리스트의 어느곳에서나 행함
  • → 순서 유지를 위해 복잡한 상황이 유지됨.
• 스택
  • 순서가 있다
  • 삽입과 삭제를 리스트 한 쪽(top)에서 행함
• 큐
  • 순서가 있다.
  • 삽입은 리스트의 한쪽(rear)에서 하고 삭제는 삽입의 반대쪽(front)에서 행함
• 자료구조와 연산 모델
  • 자료구조= 자료선언+연산
  • 자료 선언 : 프로그램 언어의 타입을 이용하여 선언
  • 연산
    • 자료의 검색과 갱신에 관한 연산으로 이루어진다
    • 검색 : 찾기
    • 갱신 : 삽입, 삭제, 수정

 

스택

• 삽입은 리스트의 마지막, 삭제도 리스트의 마지막에서 행한다
• Last-In-First-Out(LIFO)의 자료구조
• 스택 자료구조와 연산
  • 검색
    • top() : 맨 위에 있는 데이터 값을 반환한다. → 읽기에 해당
    • isempty() : 스택에 원소가 없으면 true 있으면 false 값 반환 → 검사에 해당
    • isfull() : 스택에 원소가 없으면 false 있으면 true 값 반환 → 검사에 해당
  • 갱신
    • push() : 스택에 데이터를 삽입 → 삽입
    • pop() : 스택에 데이터 삭제 → 삭제

코드 전문

/* DBLAB struct-linkedlist.c */
#include <stdio.h>
#include <malloc.h>
#define MAX_STACK_SIZE 100

char stack[MAX_STACK_SIZE];
int top = -1;
void push(char item) {
	if (top >= MAX_STACK_SIZE - 1) { printf("stack full()\n"); return; }
	stack[++top] = item;
}
char pop() {
	if (top == -1) { printf("stack_empty()\n"); exit(); }
	return stack[top--];
}
int isempty() { if (top <0) return(1); 
else return(0);
}
int isfull() { if (top >= MAX_STACK_SIZE - 1) return(1); 
else return(0);
}

java에서 스택을 구현하는 방법 : 객체 지향이 좀 더 편하다. 자료구조에서의 비교법을 찾아야 한다.

차이가 있느냐?

→ c는 펼쳐져 있으나 java는 class로 만들어준다.

java는 스택이라는 자료구조를 미리 만들어준다. → java.util.Stack 을 만들어놨음

 

 

큐

• 순서가 있는 리스트
• 삽입 연산은 한 쪽 끝에서 일어난다.
• 삭제 연산은 삽입의 반대쪽에서 일어난다.
• FIFO
• insert →rear에 들어오고 Delete 하면 front가 나간다.

큐의 생성

자료+연산으로 이뤄져있다.

• front와 rear의 값을 어떻게 줘야하는가?
  • 스택에서 top 값을 -1로 줬기 때문에 위 값들은 -1로 정의가 된다.
• first()
• insert()
  • 원소를 큐에 집어넣는 역할을 한다.
  • insert 하고 element 값을 줘야한다. 아이템을 호출해야 하는데,
    • 중요한 것!! return 타입이 void이어야한다.
    • insert 이후에 main에 바뀐 값을 전달해줘야한다.
    • front로 전달해줘야한다. 근데.. 왜 void지??
      • 값이 막 바뀐다. 바뀌는 변수가 rear이다.
  • 호출하는 곳을 봐보자.
  • insert(rear, item) /*바뀌는 rear 값을 줘야한다. rear 값을 주면 바뀌어서 들어와야한다.*/ /* main에도 변경된 값을 기입하기 위해서 주솟값으로 보내야한다. 아래는 올바른 호출*/ insert(&rear, item)
  • 모두 주솟값으로 접근을 해야한다.
• delete()
  • 위의 설명과 동일하게 주솟값을 넣어야한다.
  • front 가 가르키는 것은 데이터가 없다. +1을 해야지 큐 원소에 접근이 가능하다.
  • front==rear의 경우 원소가 존재하지 않음!
• isempty(), isfull()

큐의 예

ex1

• 이런 식으로 하면 됨~~

큐 코딩하기~

/* DBLAB queue.c */
#include <stdio.h>
#define MAX_QUEUE_SIZE 100
typedef struct {
	int key;
	/* other fields */
} element;

element queue[MAX_QUEUE_SIZE];

void insertq(int *rear, int front, element item) {
	if(*rear == MAX_QUEUE_SIZE - 1) {
		printf(" => Queue Full\\n");
		//exit();
		/* 다른 처리방법 ? 큐의 원소를 모두 원쪽으로 이동 ? */
	}
	queue[++*rear] = item;
}

element deleteq(int *front, int rear) {
	//element e;
	if(*front == rear)
	{	printf(" => Queue Empty\\n");
		//exit(); /* return an error key */
	}
	return queue[++*front];
}

element first()
{
	element e = { 0 };
	// ... 코드 작성 필요.
	return e;
}
 int isempty(int front, int rear)
{ if( front == rear ) return(1); else return(0); }
 
int isfull(int front, int rear)
{ if ( rear == (MAX_QUEUE_SIZE-1) ) return(1); 
  else return(0); }

void main(void) /* 큐를 테스트하는 프로그램 */
{
	int rear = -1; 	int front = -1;
	element e1, e2;
	e1.key=100; insertq(&rear, front, e1);
	e1.key=200; insertq(&rear, front, e1);
	e1.key=300; insertq(&rear, front, e1);

	e2=deleteq(&front, rear);
	printf(" => Return Value is %d\\n", e2.key);  
	e2=deleteq(&front, rear);
	printf(" => Return Value is %d\\n", e2.key);
}

원형 큐

• 큐 구현의 문제점
  • 작업 큐에서 max_queue_size만큼 원소가 삽입되면? → 큐는 full이 된다.
  • full의 상태에서 front 값이 변화하지 않는 것이 문제이다. 앞의 큐의 빈칸을 계속 없애기 위한 작업이 필요하다.(귀찮)
  • isempty()와 isfull()이 동시에 참인 경우가 있다(오류)

→ 배열을 원형으로 만들고 원형 배열에 데이터를 저장한다!

    front와 rear의 초기 값을 0으로 만들자

    front 변수는 큐의 처음 값 위치에서 1을 뺀 값이다.

    rear 변수는 큐의 마지막 값 위치를 가리킴

    최대 MAX_~~ -1개를 저장한다.

    큐는 반드시 다 채워지면 안됨

• stack에서는 뒤만 신경쓰면 괜찮은데 큐는 뒤로 밀리는 상황이 생김!

원형 큐 구현시 주의 할 점

• front와 rear의 초기값 : front=0; rear=0;
• insert 연산 후 rear의 값 : rear=(**rear+1)%MAX_QUEUE_SIZE;
• delelte 연산 후 front 값 : front=(**front+1)%MAX_QUEUE_SIZE;

 

원형 큐의 생성

 

add

void add(int front, int *rear, element item){
	*rear = (*rear +!)%MAX_QUEUE_SIZE;
	if(front ==*rear){
		return -1;}
	queue[*rear] =item;}

delete

element delete(int *front, int rear){
	if(*front ==rear) return -1
	*front =(*front +1)%MAX_QUEUE_SIZE;
	return queue[*front];
}

 

좀 더 자세한 사항 : 

https://tame-neptune-1a0.notion.site/4-e8cb82eca8dc4600a3a6411508eb8875

4장 스택과 큐