선형데이터구조, 스택(Stack) #3 배열과 연결리스트 기반 스택 구현

1. 배열 기반 스택 특징

• 스택의 담을 수 있는 크기가 고정적임
• 최상위를 나타내는 변수(top)를 이용하여 삽입과 제거 연산을 수행함

 

2. 배열 기반 구현

public class StackAsArray {
	static final int MAX = 1000;
	int top;
	int a[] = new int[MAX];
	
	boolean isEmpty()
	{
		return (top<0);
	}
	StackAsArray()
	{
		top = -1;
	}
	
	boolean push(int x)
	{
		if(top>=(MAX-1)) {
			System.out.println("Stack Overflow");
			return false;
		}
		else
		{
			a[++top] = x;
			System.out.println(x + " pushed into stack");
			return true;
		}
	}
	
	int pop()
	{
		if(top<0)
		{
			System.out.println("Stack Underflow");
			return 0;
		}
		else
		{
			int x = a[top--];
			return x;
		}
	}
	
	int peek()
	{
		if(top<0)
		{
			System.out.println("Stack Underflow");
			return 0;
		}
		else
		{
			int x = a[top];
			return x;
		}
	}
}

 

3. 연결리스트 기반 스택 특징

• 스택의 크기가 동적임
• 연결리스트의 head(root) 부분이 스택의 최상층을 나타냄
• 삽입과 삭제가 쉬움

 

4. 연결리스트 기반 스택 구현

public class StackAsLinkedList {
	StackNode root;
	
	static class StackNode{
		int data;
		StackNode next;
		
		StackNode(int data) {
			this.data = data;
		}
	}
	
	public boolean isEmpty()
	{
		if(root==null) 
		{
			return true;
		}
		else 
		{
			return false;
		}
	}
	
	public void push(int data)
	{
		StackNode newNode = new StackNode(data);
		
		if(root==null)
		{
			root = newNode;
		}
		else
		{
			StackNode temp = root;
			root = newNode;
			newNode.next = temp;
		}
		System.out.println(data + " pushed to stack");
	}
	
	public int pop()
	{
		int popped = Integer.MIN_VALUE;
		if(root==null)
		{
			System.out.println("Stack is Empty");
		}
		else
		{
			popped = root.data;
			root = root.next;
		}
		return popped;
	}
	
	public int peek()
	{
		if(root==null)
		{
			System.out.println("Stack is Empty");
			return Integer.MIN_VALUE;
		}
		else
		{
			return root.data;
		}
	}
}

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/Stack/Implement