Stack과 Queue 자료구조 implements (자바(Java) and 파이썬(Python))

Stack(스택)

중요 개념 : LIFO구조로 가장 나중에 들어간 데이터를 가장 먼저 빼내는 구조.

중요 연산 : pop(), push()

 

주요 사용 사례 : 웹 브라우저 방문기록(뒤로가기, 앞으로 가기), 실행 취소, 역순 문자열 만들기, 후위 표기법 계산, 재귀알고리즘

 

장/단점: 데이터저장, 읽기 속도가 빠르다/ 데이터 개수에 영향을 받는다.(스택의 공간)

 

구현 : 파이썬 – list / 자바 – Stack클래스 or List들 or 배열

 

파이썬의 경우 재귀함수는 1000번까지만 호출가능

 

웹 브라우저 방문기록(뒤로가기, 앞으로 가기) prev, next 스택을 가짐

1. 처음 크롬화면으로 들어갔다.
2. 네이버에 들어갔다. 이때 prev에 크롬 첫 화면이 들어간다.
3. 네이버 뉴스에 들어갔다. 이때 prev에 네이버 화면이 들어간다.
4. 뒤로 가기를 누른다면, prev 스택에 저장되어 있던 네이버화면이 현재화면에 보여지고, next스택에 네이버 뉴스화면이 들어간다.
5. 앞으로 가기를 누른다면 prev스택에 네이버화면을 넣는다. 그리고 next스택에서 네이버 뉴스화면을 빼와 현재화면으로 대체한다.

 

 

Python구현

stack=list()

def push(list,data):
    list.append(data)

def pop(list):
    return list.pop()

for i in range(5):
    push(stack,i)
print(pop(stack))
print(pop(stack))
print(pop(stack))
print(pop(stack))
'''
4
3
2
1
'''

'''----------------- 다른 방법 --------------------------'''
stack=list()

def push(list,data):
    list.append(data)

def pop(list):
	data = stack_list[-1]
    del stack_list[-1]
    return data
    
for i in range(5):
    push(stack,i)
print(pop(stack))
print(pop(stack))
print(pop(stack))
print(pop(stack))
'''
4
3
2
1
'''

 

Java - Stack클래스 이용

public class main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>(); //int형 스택 선언
        stack.push(1);     // stack에 값 1 추가
        stack.push(2);     // stack에 값 2 추가
        stack.push(3);     // stack에 값 3 추가

        stack.pop();       // stack에 값 제거

        stack.size();      // stack의 크기 출력 : 3

        stack.peek();     // stack의 가장 상단의 값 출력

        stack.empty();     // stack이 비어있는제 check (비어있다면 true)

        stack.contains(1) // stack에 1이 있는지 check (있다면 true)

        stack.clear();     // stack의 전체 값 제거 (초기화)
    }
}

 

Java - ArrayList 이용

class StackMy<T> {

	private ArrayList<T> arrayStack = new ArrayList<>();
	public void push(T data) {
		arrayStack.add(data);
	}
    
	public T pop() {
		if(arrayStack.size()==0) {
			return null;
		}
		return arrayStack.remove(arrayStack.size()-1);
	}
    
    public T peek(){
    	if(arrayStack.size()==0) {
			return null;
		}
        return arrayStack.get(arrayStack.size()-1);
    }
}

public class StackTest {

	public static void main(String[] args) {
		StackMy<Integer> stack = new StackMy();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		System.out.println(stack.pop());
		System.out.println(stack.peek());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
	}

}

 

 

Java - 배열 이용

class Stack {

    private int[] stack_list;
    private int top = -1;
    private int size = 50;

    //Stack 생성
    public Stack(){
        stack_list = new int[size];
        Arrays.fill(stack_list,0);
    }

    //데이터 삽입
    public void push(int data){
        // 용량이 초과할 경우 크기 확장 후 기존 데이터 migration
        if(top == stack_list.length-1){
            System.out.println("용량 초과하였습니다.");
        }
        System.out.println("데이터 추가 : "+data);
        stack_list[++top] = data;
        System.out.println("elements[top] = " + stack_list[top]);

    }

    //데이터 삭제
    public int pop(){
        if(top < 0) {
            System.out.println("데이터가 존재하지 않습니다.");
            return -1;
        }
        else {
            System.out.println("elements[top] = " + stack_list[top]);
            int num = stack_list[top];
            stack_list[top--] = 0;
            return num;
        }
    }

    //스택의 최근에 넣은 데이터 출력
    public int peek(){
        return stack_list[top];
    }
}

public class main {
    public static void main(String[] args) {
        Stack myStack = new Stack();
        myStack.push(10);
        myStack.push(20);
        myStack.push(30);
        myStack.push(40);


        System.out.println(myStack.pop());
        System.out.println(myStack.peek());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
    }
}

/*
데이터 추가 : 10
elements[top] = 10
데이터 추가 : 20
elements[top] = 20
데이터 추가 : 30
elements[top] = 30
데이터 추가 : 40
elements[top] = 40
elements[top] = 40
40
30
elements[top] = 30
30
elements[top] = 20
20
elements[top] = 10
10
*/

---

Queue

중요 개념 : 가장 먼저 넣은 데이터가 가장 먼저 꺼내진다. (FIFO)

중요 연산 : Enqueue, Dequeue

 

주요 사용 사례 : 프린트

 

구현 : 파이썬 - (queue라이브러리 or List)   /  자바 - (Queue클래스 = new LinkedList)

 

---

Java - 직접 Queue클래스를 만들었다. LinkedList방식으로

public class main {
    public static void main(String[] args) {

        Queue q=new Queue();
        int[] arr={1,2,5,7,9,10,15};
        for(int i:arr){
            q.enqueue(i);
        }
        System.out.println("q.peek() = " + q.peek()); // 1 출력
        q.dequeue(); // 1 삭제
        q.dequeue(); // 2 삭제
        System.out.println("q.peek() = " + q.peek()); // 5 출력
    }
}




class QueueNode{
    int value;
    QueueNode next;
    public QueueNode(int data){
        value= data;
        next=null;
    }
}

class Queue{
    QueueNode front;
    QueueNode rear;

    public void enqueue(int data){
        QueueNode new_node=new QueueNode(data);
        if(this.rear==null){
            this.front=new_node;
            this.rear=new_node;
            return;
        }
        this.rear.next=new_node;
        this.rear=new_node;
    }

    public void dequeue(){
        if(this.front==null){
            return;
        }
        this.front=this.front.next;
        if(this.front==null)
            this.rear=null;
    }

    //맨 앞 요소 출력
    public int peek(){
        if(this.front==null) return -1;
        return this.front.value;
    }
}

---

 

Java - Queue인터페이스 사용 - Queue는 인터페이스로 클래스인 LinkedList로 해줘야한다. 

LinkedList로 하는 이유는 큐는 FiFO구조로 만약 ArrayList로 했다고 한다면 삭제에 있어서 앞에 삭제할때 다 움직여야하기 때문이다.

public class main {
    public static void main(String[] args) {

        Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언

        queue.add(1);     // queue에 값 1 추가
        queue.add(2);     // queue에 값 2 추가
        queue.add(3);     // queue에 값 3 추가
        queue.add(4);     // queue에 값 4 추가
        
       	queue.poll();       // queue에 첫번째 값을 반환하고 제거  1
        queue.poll();		// 2
        queue.poll();		// 3
        queue.poll();		// 4	

    }
}

---

파이썬 - queue라이브러리 이용

 

import queue

data_queue = queue.Queue()

data_queue.put("my")
data_queue.put(1)
data_queue.put(2)


data_queue.get()  # my
data_queue.qsize() # 2

 

---

 

파이썬 - List 이용

class Queue:
    def __init__(self):
        self.q_list = list()

    def enqueue(self, data):
        self.q_list.append(data)

    def dequeue(self):
        data = self.q_list[0]
        del self.q_list[0]
        return data

    def peek(self):
        return self.q_list[0]

q =Queue()
for i in range(9):
    q.enqueue(i)

print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.peek())
print(q.dequeue())

'''
0
1
2
3
3
'''

---

파이썬 - 클래스로 구현

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None


class Queue:
    def __init__(self):
        self.front = self.rear=None

    def enqueue(self, data):
        new_node=Node(data)
        if self.rear == None:
            self.front=new_node
            self.rear=new_node
            return
        self.rear.next=new_node
        self.rear=new_node


    def dequeue(self):
        if self.front == None:
            return
        data = self.front.data
        self.front=self.front.next
        if self.front == None:
            self.rear==None
        return data

    def peek(self):
        if self.front==None:
            return
        return self.front.data

q =Queue()
for i in range(9):
    q.enqueue(i)

print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.peek())
print(q.dequeue())