[CS 자료구조] 스택에 대한 개념

스택

• 후입선출 (LIFO)
• 최근에 들어온 데이터가 가장 먼저 나간다.

 

배열 스택

class ArrayStack {
	private int top;
	private int stackSize;
	private char itemArray[];
	
	public ArrayStack(int stackSize){
		top = -1;
		this.stackSize = stackSize;
		itemArray = new char[this.stackSize];
	}
	
	public boolean isEmpty(){
		return (top == -1);
	}
	
	public boolean isFull(){
		return (top == this.stackSize-1);
	}
	
	public void push(char item){
		if(isFull()){
			System.out.println("Inserting fail! Array Stack is full!!");
		}
		else{ 			
			itemArray[++top] = item;
			System.out.println("Inserted Item : " + item);
		}
	}
	
	public char pop(){
		if(isEmpty()) {
			System.out.println("Deleting fail! Array Stack is empty!!");
			return 0;
		}
		else{
			return itemArray[top--];	
		}				
	}
	
	public void delete(){
		if(isEmpty()){
			System.out.println("Deleting fail! Array Stack is empty!!");			
		}
		else {
			top--;
		}
	}
	
	public char peek(){
		if(isEmpty()){
			System.out.println("Peeking fail! Array Stack is empty!!");
			return 0;
		}
		else 
			return itemArray[top];		
	}
	
	public void printStack(){
		if(isEmpty())
			System.out.println("Array Stack is empty!! %n %n");
		else{
			System.out.printf("Array Stack>> ");
			for(int i=0; i<=top; i++) {
    			System.out.printf("%c ", itemArray[i]);  
			}
			System.out.println();
		}
	}
}

public class Main{
	public static void main(String args[]){
		int stackSize = 5;
		char deletedItem;
		ArrayStack S = new ArrayStack(stackSize);
		
		S.push('A'); // Inserted Item : A
		S.printStack(); // Array Stack>> A 
		
		S.push('B'); // Inserted Item : B
		S.printStack(); // Array Stack>> A B 
		
		S.push('C'); // Inserted Item : C
		S.printStack(); // Array Stack>> A B C 
		
		deletedItem = S.pop();
		if(deletedItem != 0) {
		    System.out.println("deleted Item : " + deletedItem); // deleted Item : C
		}
		S.printStack();	// Array Stack>> A B	
	}
}

 

리스트 스택

interface Stack{
	
	boolean isEmpty();
	void push(char item);
	char pop();
	void delete();
	char peek();
	
}


class StackNode{
	
	char data;
	StackNode link;
	
}


class LinkedStack implements Stack{
	
	private StackNode top;
		
	public boolean isEmpty(){
		return (top == null);
	}
	
	
	public void push(char item){
		StackNode newNode = new StackNode();
		newNode.data = item;
		newNode.link = top;
		top = newNode;
		System.out.println("Inserted Item : " + item);
	}
	
	
	public char pop(){
		
		if(isEmpty()) {
			System.out.println("Deleting fail! Linked Stack is empty!!");
			return 0;
		}
		else{ 
			char item = top.data;
			top = top.link;
			return item;	
		}
		
	}
	
	public void delete(){
		
		if (isEmpty()){
			System.out.println("Deleting fail! Linked Stack is empty!!");			
		}
		else {
			top = top.link;
		}
		
	}
	
	public char peek(){
		
		if (isEmpty()){
			System.out.println("Peeking fail! Linked Stack is empty!!");
			return 0;
		}
		else 
			return top.data;	
		
	}
	
	public void printStack(){
		if(isEmpty())
			System.out.printf("Linked Stack is empty!! %n %n");
		else{
			StackNode temp = top;
			System.out.println("Linked Stack>> ");
			while(temp != null){
				System.out.printf("\t %c \n", temp.data);
				temp = temp.link;
			}
			System.out.println();	
		}
	}
}

public class Main{
	public static void main(String args[]){		
		char deletedItem;
		LinkedStack LS = new LinkedStack();
		
		LS.push('A');
		LS.printStack();
		
		LS.push('B');
		LS.printStack();
		
		LS.push('C');
		LS.printStack();
		
		deletedItem = LS.pop();
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem);
		}
		LS.printStack();
		
		/*
                Inserted Item : A
                Linked Stack>> 
                         A 

                Inserted Item : B
                Linked Stack>> 
                         B 
                         A 

                Inserted Item : C
                Linked Stack>> 
                         C 
                         B 
                         A 

                deleted Item : C
                Linked Stack>> 
                         B 
                         A 
		*/
		
	}
}

 

 

 

출처)

https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95