◆◆ Stack 과 Queue
◆ 1. Stack
㉠ 정의
여러 개의 데이타 항목들이 일정한 순서로 나열된 자료 구조로, 한쪽 끝에서만 새로운 항목을 삽입하거나 기존 항목을 삭제할 수
있는 선형 구조.
㉡ 특징
Last- In-First-Out List (후입 선출) : 먼저 삽입된 것은 나중에 삭제되고, 나중에 삽입된 것이 먼저 삭제.
push : Data 를 넣는 것.
pop : 넣어둔 Data 를 꺼내는 것.
top : Data 를 저장하는 위치
㉢ 연산
S를 스택, x를 데이터 요소(element)라고 하자. 그러면 스택에서는 아래와 같은 중요한 연산이 존재하는 것을 알 수 있다.
S.top(): 스택의 가장 윗 데이터를 넘겨준다.만약에 비었다면 이 연산은 정의불가 상태다.
S.pop(): 스택의 가장 윗 데이터를 지우고 그 값을 넘겨준다.스택이 비었다면 연산 정의불가 상태.
S.push(): 스택의 가장 윗 데이터로 x를 넣는다.
S.empty(): 스택이 비었다면 참을 주고,그렇지 않다면 거짓이 된다.
또한, 스택연산을 목록(list) 연산으로 표현할 수도 있다.
S.top(): S.retrieve(S.first())
S.pop(): S.top(),S.delete(S.first())
S.push():S.insert(x,pNull)
S.empty():S.first()==pNull
◆ 2. Queue
㉠ 정의
여러 개의 데이타 항목들이 일정한 순서로 나열된 자료 구조로 한쪽 끝에서는 삽입만 할 수 있고, 삭제는 반대쪽 끝에서만 할 수 있
도록 되어 있는 선형 구조.
㉡ 특징
First In First Out (선입선출) : 큐에 저장된 데이터 항목들 중에 먼저 삽입된 것은 먼저 삭제되고, 나중에 삽입된 것은 나중에 삭제.
put : Data 를 넣는 것.
get : Data 를 꺼내는 것.
front(head) : Data 를 put 할 수 있는 위치.
rear(tail) : Data 가 있어 get 할 수 있는 위치.
Overflow : Queue 가 꽉 차서 더 이상 Data 를 넣을 수 없는 경우 (put 할 수 없는 경우)
Underflow : Queue 가 비어 있어 Data 를 꺼낼 수 없는 경우 (get 할 수 없는 경우)
㉢ 종류
가. 선형 Queue : 막대 모양으로 된 Queue 이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 Data 를 꺼내거나 Data 를 한
칸씩 옮겨야 한다는 단점이 있다.
나. 환형 Queue : 선형 Queue 의 문제점을 보완한 것이 환형 Queue 이다. front가 Queue 의 끝에 닿으면 Queue 의 맨 앞으로 Data 를 보내어 원형으로 연결 하는 방식.
다. Linked Queue : Linkedlist 를 사용한 것으로써, Queue 의 길이를 쉽게 늘릴 수 있어 Overflow 가 발생하지 않는다.
필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.
◆◆ 3. Simulation (Java)
1. node 클레스 설계
------------------------------------------------------------------------------------------------------------------
public class Node {
public Node(int v){
value = v;
}
public int value;
public Node next; // 자기 참조!!
}
------------------------------------------------------------------------------------------------------------------
2. LinkedList 클레스 설계
------------------------------------------------------------------------------------------------------------------
public class LinkedList {
Node header;
public LinkedList(Node h) {
header = h;
}
public void append(Node node) {
Node last = header;
while (last.next != null) {
last = last.next;
}
last.next = node;
}
public Node getHeader(){
return header;
}
public void remove_back() //링크드 리스트에 뒤에 있는걸 삭제
{
Node last = header;
if (last.next == null) // elements 가 하나만 있는 상황이므로 끊을필요 없다
{
}
else
{
while (last.next.next != null) { // 두번째 연결된 elements 의 next 값이 없을때 까지 루프
last = last.next;
}
last.next = null; // 마지막 에 연결된 elements 의 next 를 null 값을 넣어 끊기
}
}
public void remove_front() //링크드 리스트에 앞에 있는걸 삭제
{
header = header.next; // 헤더 를 다음 값으로 바꾸기
}
}
------------------------------------------------------------------------------------------------------------------
3. Array 로 Stack 구현
------------------------------------------------------------------------------------------------------------------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class IntStack_A {
private int[] data;
private int top; // stack 맨위
private int many_items; // 현재 Stack 에 몇 개의 원소가 있는지를 저장해 놓은 변수
private int stack_size; // Stack 의 전체 크기
private BufferedReader br ;
public IntStack_A(int size) // size : 스텍의 크기
{
data = new int[size];
stack_size = size;
top = -1; // stack 이 비어 있을 때
many_items = 0;
System.out.println("값을 입력하세요 :");
try {
br = new BufferedReader(new InputStreamReader(System.in));
push(Integer.parseInt(br.readLine()));
br = new BufferedReader(new InputStreamReader(System.in));
push(Integer.parseInt(br.readLine()));
br = new BufferedReader(new InputStreamReader(System.in));
push(Integer.parseInt(br.readLine()));
br = new BufferedReader(new InputStreamReader(System.in));
push(Integer.parseInt(br.readLine()));
printf1();
System.out.println("");
System.out.println("1.삭제(POP) 2.삽입(PUSH)");
br = new BufferedReader(new InputStreamReader(System.in));
String sd=br.readLine();
if (sd.equals("1"))
{
pop();
printf1();
}
else if (sd.equals("2"))
{
push(99);
printf1();
}
} catch (NumberFormatException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public void push(int number) // push()는 Stack 의 맨 위에 쌓아놓을 수 있다 >> data 배열에 숫자를 넣음
{
data[++top] = number; //++top 연산을 통해서 top 은 push 함수를 호출할 때마다 하나씩 위로 올라가서 Stack 의 맨 위를 언제나 가리키게 됨
// 배열 이므로 제일 나중에 집어넣은 원소의 Index 를 보유
many_items++; // Stack 에 저장된 원소의 갯수 1 증가
}
public int pop() // 맨 위에서만 빼낼 수 있다
{
many_items--; // Stack 에 저장된 원소의 갯수 1 감소
return data[top--]; // 배열에서 맨위의 값을 반환하고 인덱스 를 1 감소시킴
}
public void printf1() // 배열 출력
{
for(int i=0;i<many_items;i++){
System.out.print(data[i]+",");
}
}
public static void main(String[] args)
{
new IntStack_A(5);
}
}
------------------------------------------------------------------------------------------------------------------
4. Array 로 Queue 구현
------------------------------------------------------------------------------------------------------------------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class IntQueue_A {
private int[] data;
private int rear; // Queue 맨위
private int many_items; // 현재 Queue 에 몇 개의 원소가 있는지를 저장해 놓은 변수
private int Queue_size; // Queue 의 전체 크기
private BufferedReader br ;
public IntQueue_A(int size) // size : Queue 크기
{
data = new int[size];
Queue_size = size;
rear = -1; // Queue 가 비어 있을 때
many_items = 0;
System.out.println("값을 입력하세요 :");
try {
br = new BufferedReader(new InputStreamReader(System.in));
push(Integer.parseInt(br.readLine()));
br = new BufferedReader(new InputStreamReader(System.in));
push(Integer.parseInt(br.readLine()));
br = new BufferedReader(new InputStreamReader(System.in));
push(Integer.parseInt(br.readLine()));
br = new BufferedReader(new InputStreamReader(System.in));
push(Integer.parseInt(br.readLine()));
printf1();
System.out.println("");
System.out.println("1.삭제(POP) 2.삽입(PUSH)");
br = new BufferedReader(new InputStreamReader(System.in));
String sd=br.readLine();
if (sd.equals("1"))
{
pop();
printf1();
}
else if (sd.equals("2"))
{
push(99);
printf1();
}
} catch (NumberFormatException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public void push(int number) // data 배열에 숫자를 넣음
{
data[++rear] = number; //
many_items++; // Queue 에 저장된 원소의 갯수 1 증가
}
public void pop() // 맨 위에서만 빼낼 수 있다
{
for (int i=0;i<many_items;i++)
{
data[i] = data[i+1];
}
many_items--; // Queue 에 저장된 원소의 갯수 1 감소
}
public void printf1() // 배열 출력
{
for(int i=0;i<many_items;i++){
System.out.print(data[i]+",");
}
}
public static void main(String[] args) {
new IntQueue_A(5);
}
}
------------------------------------------------------------------------------------------------------------------
5. LinkedList 로 Stack 구현
------------------------------------------------------------------------------------------------------------------
public class LinkedListStack {
public static void main(String[] args) {
LinkedList list = new LinkedList(new Node(50));
list.append(new Node(20));
list.append(new Node(30));
print(list.getHeader());
list.remove_back();
print(list.getHeader());
list.append(new Node(10));
print(list.getHeader());
list.append(new Node(60));
print(list.getHeader());
list.remove_back();
print(list.getHeader());
list.remove_back();
}
private static void print(Node header) {
Node list = header;
while (list != null) {
System.out.print(list.value + " -> ");
list = list.next;
}
System.out.println();
}
}
------------------------------------------------------------------------------------------------------------------
6. LinkedList 로 Queue 구현
------------------------------------------------------------------------------------------------------------------
public class LinkedListQueue {
public static void main(String[] args) {
LinkedList list = new LinkedList(new Node(50));
list.append(new Node(20));
list.append(new Node(30));
print(list.getHeader());
list.append(new Node(10));
print(list.getHeader());
list.append(new Node(60));
print(list.getHeader());
list.remove_front();
print(list.getHeader());
}
private static void print(Node header) {
Node list = header;
while (list != null) {
System.out.print(list.value + " -> ");
list = list.next;
}
System.out.println();
}
}
'자료구조' 카테고리의 다른 글
| 자료구조(해싱) (0) | 2009.11.06 |
|---|---|
| 자료구조 ( Array와 Linked List)- (0) | 2009.11.06 |