스택과 큐 자료구조

• 리스트, 스택과 큐 : 스택과 큐는 리스트 자료구조의 특별한 경우이다

• 리스트

  • 순서가 있다.

  • 읽기, 삽입과 삭제를 리스트의 어느곳에서나 행함

    → 순서 유지를 위해 복잡한 상황이 유지됨.

• 스택

  • 순서가 있다
  • 삽입과 삭제를 리스트 한 쪽(top)에서 행함

• 큐

  • 순서가 있다.
  • 삽입은 리스트의 한쪽(rear)에서 하고 삭제는 삽입의 반대쪽(front)에서 행함

• 자료구조와 연산 모델

  • 자료구조= 자료선언+연산
  • 자료 선언 : 프로그램 언어의 타입을 이용하여 선언
  • 연산
    • 자료의 검색과 갱신에 관한 연산으로 이루어진다
    • 검색 : 찾기
    • 갱신 : 삽입, 삭제, 수정

스택

• 삽입은 리스트의 마지막, 삭제도 리스트의 마지막에서 행한다
• Last-In-First-Out(LIFO)의 자료구조
• 스택 자료구조와 연산

  • 생성

    #define MAX_STACK_SIZE 100
    
    char stack[MAX_STACK_SIZE];
    int top = -1;
    /*top의 초기값은 스택이 비어있을 때 -1이다.*/
    

  • 검색

    • top() : 맨 위에 있는 데이터 값을 반환한다. → 읽기에 해당

    • isempty() : 스택에 원소가 없으면 true 있으면 false 값 반환 → 검사에 해당

      int isempty() { if (top <0) return(1); 
      else return(0);
      }
      

    • isfull() : 스택에 원소가 없으면 false 있으면 true 값 반환 → 검사에 해당

      int isfull() { if (top >= MAX_STACK_SIZE - 1) return(1); 
      else return(0);
      }
      

  • 갱신

    • push() : 스택에 데이터를 삽입 → 삽입

      void push(char item) {
      	if (top >= MAX_STACK_SIZE - 1) { printf("stack full()\\n"); return; }
      	stack[++top] = item;
      }
      

    • pop() : 스택에 데이터 삭제 → 삭제

      char pop() {
      	if (top == -1) { printf("stack_empty()\\n"); exit(); }
      	return stack[top--];
      }
      

코드 전문

/* 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);
}

int stack1[MAX_STACK_SIZE];
int top1 = -1;
void push1(int item) {
	if (top1 >= MAX_STACK_SIZE - 1) { printf("stack full()\\n"); return; }
	stack[++top1] = item;
}
int pop1() {
	if (top1 == -1) { printf("stack_empty()\\n"); exit(); }
	return stack1[top--];
}
int isempty1() {
	if (top1 == -1) return(1);
	else return(0);
}
int isfull1() {
	if (top >= MAX_STACK_SIZE - 1) return(1);
	else return(0);
}

int main() {
	int e;
	int j;

	for (int i = 0; i <5 ; ++i) {
		push("a" + i);
		push1( 1 + i);
	}

	while (!isempty()) {
		e = pop();
		j = pop();
		printf("야구선수 = %c, 선수 번호=%d \\n", e,j);
	}

}

/*
struct node {
	int data;
	struct node * link;
};
typedef struct node list_node;
typedef list_node * list_ptr;

int main()
{
	list_node item1, item2, item3;
	item1.data = 'a';
	item2.data = 'b';
	item3.data = 'c';
	item1.link = item2.link = item3.link = NULL;
	item1.link = &item2;
	item2.link = &item3;
	printf(" %c \\n", item1.link->link->data);
}

*/

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

차이가 있느냐?

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

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

큐

• 순서가 있는 리스트