스 택 (배열 및 링크 기반)

스 택 은 개념 적 인 보조 도구 로 한정 적 인 접근 방법 을 제공 하여 프로그램 이 읽 기 쉽 고 오류 가 발생 하지 않도록 합 니 다.시간 복잡 도 는 O (1) 이다.
배열 기반 스 택
package datastructure.c4.stack.stackdef;

public class StackX {
	private int maxSize;
	private long[] stackArray;
	private int top;
	public StackX(int s){
		maxSize=s;
		stackArray=new long[maxSize];
		top=-1;
	}
	public void push(long j){
		stackArray[++top]=j;
	}
	public long pop(){
		return stackArray[top--];
	}
	public long peek(){
		return stackArray[top];
	}
	public boolean isEmpty(){
		return (top==-1);
	}
	public boolean isFull(){
		return (top==maxSize-1);
	}
}
package datastructure.c4.stack.stackdef;

public class StackApp {
	public static void main(String[] args) {
		StackX theStack=new StackX(10);
		theStack.push(20);
		theStack.push(40);
		theStack.push(60);
		theStack.push(80);
		
		while(!theStack.isEmpty()){
			long value=theStack.pop();
			System.out.print(value);
			System.out.print("  ");
		}
		System.out.println("");
	}
}

사례 1: 문자 반전
package datastructure.c4.stack.reverse;

public class StackX {
	private int maxSize;
	private char[] stackArray;
	private int top;
	public StackX(int max){
		maxSize=max;
		stackArray=new char[maxSize];
		top=-1;
	}
	public void push(char j){
		stackArray[++top]=j;
	}
	public char pop(){
		return stackArray[top--];
	}
	public char peek(){
		return stackArray[top];
	}
	public boolean isEmpty(){
		return (top==-1);
	}
	public boolean isFull(){
		return (top==maxSize-1);
	}
}
package datastructure.c4.stack.reverse;

public class Reverser {
	private String input;
	private String output;
	public Reverser(String in){
		input=in;
	}
	public String doRev(){
		int stackSize=input.length();
		StackX theStack=new StackX(stackSize);
		for(int j=0;j
package datastructure.c4.stack.reverse;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ReverseApp {
	public static void main(String[] args) throws IOException {
		String input,output;
		while(true){
			System.out.print("Enter a string:");
			System.out.flush();
			input=getString();
			if("".equals(input)){
				break;
			}
			Reverser theReverser=new Reverser(input);
			output = theReverser.doRev();
			System.out.println("Reversed:"+output);
		}
	}
	public static String getString() throws IOException{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String s = br.readLine();
		return s;
	}
}

사례 2: 괄호 검사
package datastructure.c4.stack.brackets;

public class StackX {
	private int maxSize;
	private char[] stackArray;
	private int top;
	public StackX(int max){
		maxSize=max;
		stackArray=new char[maxSize];
		top=-1;
	}
	public void push(char j){
		stackArray[++top]=j;
	}
	public char pop(){
		return stackArray[top--];
	}
	public char peek(){
		return stackArray[top];
	}
	public boolean isEmpty(){
		return (top==-1);
	}
	public boolean isFull(){
		return (top==maxSize-1);
	}
}
package datastructure.c4.stack.brackets;

public class BracketChecker {
	private String input;
	public BracketChecker(String in){
		input=in;
	}
	public void check(){
		int stackSize=input.length();
		StackX theStack=new StackX(stackSize);
		
		for(int j=0;j
package datastructure.c4.stack.brackets;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BracketsApp {
	public static void main(String[] args) throws IOException {
		String input;
		while(true){
			System.out.println("Enter string containing delimiters:");
			System.out.flush();
			input=getString();
			if("".equals(input)){
				break;
			}
			BracketChecker theChecker=new BracketChecker(input);
			theChecker.check();
		}
	}
	public static String getString() throws IOException{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String s = br.readLine();
		return s;
	}
}

링크 기반 스 택
package datastructure.c5.linklist.linkstack;

public class Link {
	public long dData;
	public Link next;
	public Link(long d){
		dData=d;
	}
	public void displayLink(){
		System.out.print(dData+"  ");
	}
}
package datastructure.c5.linklist.linkstack;

public class LinkList {
	private Link first;
	public LinkList(){
		first=null;
	}
	public boolean isEmpty(){
		return first==null;
	}
	public void insertFirst(long dd){
		Link newLink=new Link(dd);
		newLink.next=first;
		first=newLink;
	}
	public long deleteFirst(){
		Link temp=first;
		first=first.next;
		return temp.dData;
	}
	public void displayList(){
		Link current=first;
		while(current!=null){
			current.displayLink();
			current=current.next;
		}
		System.out.println("");
	}
}
package datastructure.c5.linklist.linkstack;

public class LinkStack {
	private LinkList theList;
	public LinkStack(){
		theList=new LinkList();
	}
	public void push(long j){
		theList.insertFirst(j);
	}
	public long pop(){
		return theList.deleteFirst();
	}
	public boolean isEmpty(){
		return theList.isEmpty();
	}
	public void displayStack(){
		System.out.println("Stack (top-->bottom):");
		theList.displayList();
	}
}
package datastructure.c5.linklist.linkstack;

public class LinkStackApp {
	public static void main(String[] args) {
		LinkStack theStack=new LinkStack();
		theStack.push(20);
		theStack.push(40);
		theStack.displayStack();
		theStack.push(60);
		theStack.push(80);
		theStack.displayStack();
		theStack.pop();
		theStack.pop();
		theStack.displayStack();
	}
}

좋은 웹페이지 즐겨찾기